Physics – Quantum Physics
Scientific paper
2006-06-24
New J. Phys. 9 (2007) 72
Physics
Quantum Physics
13 pages; v2 added NSF grant info; v3 incorporated feedback
Scientific paper
10.1088/1367-2630/9/3/072
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 $\epsilon$ 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(\delta^{-1} (\log N + \log \epsilon^{-1}))$, where $\delta$ 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 $\epsilon^{-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(\delta^{-1/2} \log N \log \epsilon^{-1})$ when $P$ is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.
No associations
LandOfFree
Almost uniform sampling via quantum walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Almost uniform sampling via quantum walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost uniform sampling via quantum walks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-282894