2007.04.11 | Louis Salvail

Quantum speedup of classical mixing processes

Peter Richter, Rutger's University, USA

Abstract:
Most approximation algorithms for #P-complete problems (e.g., evaluating the
permanent of a matrix or the volume of apolytope) work by reduction to the
problem of approximatesampling 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 nearequilibrium.
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.