Title: Quantum Speedup of Classical Mixing Processes
Speaker: Peter Richter, Rutgers University
Date: Wednesday, April 18, 2007 11:00am - 12:00pm
Location: CoRE Bldg, CoRE A, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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 {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 {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 {quantum walks}.
We provide evidence for this possibility using quantum walks that {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.