Almost uniform sampling via quantum walks
| dc.creator | Richter, Peter C. | |
| dc.date | 2006-06-24 | |
| dc.date | 2006-09-18 | |
| dc.date.accessioned | 2026-07-07T07:55:16Z | |
| dc.date.available | 2026-07-07T07:55:16Z | |
| dc.description | Many classical randomized algorithms (e.g., approximation algorithms for #P-complete problems) utilize the following random walk algorithm for {\em almost uniform sampling} from a state space $S$ of cardinality $N$: run a symmetric ergodic Markov chain $P$ on $S$ for long enough to obtain a random state from within $ε$ total variation distance of the uniform distribution over $S$. The running time of this algorithm, the so-called {\em mixing time} of $P$, is $O(δ^{-1} (\log N + \log ε^{-1}))$, where $δ$ is the spectral gap of $P$. We present a natural quantum version of this algorithm based on repeated measurements of the {\em quantum walk} $U_t = e^{-iPt}$. We show that it samples almost uniformly from $S$ with logarithmic dependence on $ε^{-1}$ just as the classical walk $P$ does; previously, no such quantum walk algorithm was known. We then outline a framework for analyzing its running time and formulate two plausible conjectures which together would imply that it runs in time $O(δ^{-1/2} \log N \log ε^{-1})$ when $P$ is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs. | |
| dc.description | 13 pages; v2 added NSF grant info; v3 incorporated feedback | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0606202 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0606202 | |
| dc.identifier | New J. Phys. 9 (2007) 72 | |
| dc.identifier | doi:10.1088/1367-2630/9/3/072 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/126906 | |
| dc.subject | Quantum Physics | |
| dc.title | Almost uniform sampling via quantum walks | |
| dc.type | text |