Quantum algorithms can potentially solve a handful of problems more efficiently than their classical counterparts. In that context, it has been discussed that Markov chains problems could be solved significantly faster using quantum computing. Indeed, previous work suggests that quantum computers could accelerate sampling from the stationary distribution of reversible Markov chains. However, in practice, certain physical processes of interest are nonreversible in the probabilistic sense and reversible Markov chains can sometimes be replaced by more efficient nonreversible chains targeting the same stationary distribution. This study constructs Markov chain reversibilizations and develops quantum algorithmic techniques to accelerate nonreversible processes. Such an up-to-exponential quantum speedup goes beyond the predicted quadratic quantum acceleration for reversible chains and is likely to have a decisive impact on many applications ranging from statistics and machine learning to computational modeling in physics, chemistry, biology and finance.
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
Most approximation algorithms for #
P-complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution $\ensuremath{\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 $\ensuremath{\pi}$ is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of
P, is $O({\ensuremath{\delta}}^{\ensuremath{-}1}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ as shown by Aldous, where $\ensuremath{\delta}$ is the spectral gap of
P and ${\ensuremath{\pi}}_{\ensuremath{\ast}}$ is the minimum value of $\ensuremath{\pi}$. A natural question is whether a speedup of this classical method to $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice
Znd is
O(nd log d), which is indeed $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ and is asymptotically no worse than the diameter of
Znd (the obvious lower bound) up to at most a logarithmic factor.
Sampling from the stationary distribution is one of the fundamental tasks of Markov-chain-based algorithms and has important applications in machine learning, combinatorial optimization, and network science. For the quantum case, quantum sampling from Markov chains corresponds to preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution instead of classical sampling from a stationary distribution. A different quantum sampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks. We build a quantum sampling algorithm that not only accelerates nonregular graphs, but also keeps the speed up of existing quantum algorithms for regular graphs. In nonregular graphs, the invocation of the quantum fast-forwarding algorithm accelerates previous state-of-the-art quantum sampling algorithms for both discrete-time and continuous-time cases, especially on sparse graphs. Compared to existing algorithms, we decrease the runtime by a factor of
logn, where
n is the number of graph vertices. In regular graphs, our results match other quantum algorithms and the reliance on the gap of Markov chains achieves quadratic speedup compared with classical cases. For both cases, we reduce the number of ancilla qubits required compared with the existing results. In some widely used graphs and a series of sparse graphs where stationary distributions are difficult to reach quickly, our algorithm achieves complete quadratic acceleration (without log factor) over the classical case without any limit. In addition, we construct a different reflection around the stationary state with fewer ancilla qubits and believe it may have an independent application.
Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [D. Layden et al., Nature (London) 619, 282 (2023).] proposed a quantum-enhanced Markov-chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.
Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [Layden, D. et al. Nature 619, 282-287 (2023)] proposed a quantum-enhanced Markov chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.