Physics – Quantum Physics
Scientific paper
2006-09-26
Phys. Rev. A 76, 042306 (2007)
Physics
Quantum Physics
13 pages; v2 revised several parts
Scientific paper
10.1103/PhysRevA.76.042306
Most approximation algorithms for #P-complete problems (e.g., evaluating the permanent of a matrix or the volume of a polytope) work by reduction to the problem of approximate sampling from a distribution $\pi$ over a large set $\S$. This problem is solved using the {\em Markov chain Monte Carlo} method: a sparse, reversible Markov chain $P$ on $\S$ with stationary distribution $\pi$ is run to near equilibrium. The running time of this random walk algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} \log 1/\pi_*)$ as shown by Aldous, where $\delta$ is the spectral gap of $P$ and $\pi_*$ is the minimum value of $\pi$. A natural question is whether a speedup of this classical method to $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$, the diameter of the graph underlying $P$, is possible using {\em quantum walks}. We provide evidence for this possibility using quantum walks that {\em decohere} under repeated randomized measurements. We show: (a) decoherent quantum walks always mix, just like their classical counterparts, (b) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (c) the mixing time of the decoherent quantum walk on a periodic lattice $\Z_n^d$ is $O(n d \log d)$, which is indeed $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$ and is asymptotically no worse than the diameter of $\Z_n^d$ (the obvious lower bound) up to at most a logarithmic factor.
No associations
LandOfFree
Quantum speedup of classical mixing processes 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 Quantum speedup of classical mixing processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum speedup of classical mixing processes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-167647