Quantum speedup of classical mixing processes

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 {\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 }_{\ast })$ as shown by Aldous, where $\delta$ is the spectral gap of $P$ and ${\pi }_{\ast }$ 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 }_{\ast })$, 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 ${\mathbb{Z}}_n^d$ is $O(nd\log d)$, which is indeed $O(\sqrt{{\delta }^{-1}}\log 1/{\pi }_{\ast })$ and is asymptotically no worse than the diameter of ${\mathbb{Z}}_n^d$ (the obvious lower bound) up to at most a logarithmic factor.

13 pages; v2 revised several parts

References in corpus (5)

• Exponential algorithmic speedup by quantum walk
• Continuous-time Quantum Walks on a Cycle Graph
• Almost uniform sampling via quantum walks
• Non-Unitary Quantum Walks on Hyper-Cycles
• Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles

Cited by in corpus (45)

• Quantum speedup of Monte Carlo methods
• Decoherence in quantum walks - a review
• Speed-up via Quantum Sampling
• Quantum-enhanced Markov chain Monte Carlo
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Decoherence vs entanglement in coined quantum walks
• Quantum Computation and Quantum Information
• Hitting time for the continuous quantum walk
• Almost uniform sampling via quantum walks
• Quantum Speed-up for Approximating Partition Functions
• Quantum walk approach to simulating parton showers
• Quantum Walks
• Introduction to Quantum Algorithms for Physics and Chemistry
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Continuous-time quantum walks on one-dimension regular networks
• Simulation of Classical Thermal States on a Quantum Computer: A Transfer Matrix Approach
• Quantum Enhanced Inference in Markov Logic Networks
• How fast do quantum walks mix?
• Collider Events on a Quantum Computer
• The Limiting Distribution of Decoherent Quantum Random Walks
• A Comparison of Quantum Walk Implementations on NISQ Computers
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• Asymptotic evolution of quantum walks on the $N$-cycle subject to decoherence on both the coin and position degrees of freedom
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Quantum random walks on the $N$-cycle subject to decoherence on the coin degree of freedom
• Analog quantum algorithms for the mixing of Markov chains
• Optimal computation with non-unitary quantum walks
• Simulation of Quantum Walks and Fast Mixing with Classical Processes
• Statistical dynamics of a non-Abelian anyonic quantum walk
• Quantum Cloning by Cellular Automata
• Quantum scattering theory on graphs with tails
• Small quantum computers and large classical data sets
• Probing coherence and noise tolerance in discrete-time quantum walks: unveiling self-focusing and breathing dynamics
• Quantum algorithm for estimating volumes of convex bodies
• Bounds for mixing time of quantum walks on finite graphs
• Study of Quantum Walk over a Square Lattice
• Transient temperature and mixing times of quantum walks on cycles
• Limit theorems and localization of three state quantum walks on a line defined by generalized Grover coins
• One-dimensional discrete-time quantum walks on random environments
• Environment-induced mixing processes in quantum walks
• Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
• Quantum walk mixing is faster than classical on periodic lattices
• For every quantum walk there is a (classical) lifted Markov chain with faster mixing time
• On the von Neumann entropy of certain quantum walks subject to decoherence
• Quantum walks advantage on the dihedral group for uniform sampling problem