The preparation of the stationary distribution of irreducible, time-reversible Markov chains (MCs) is a fundamental building block in many heuristic approaches to algorithmically hard problems. It has been conjectured that quantum analogs of classical mixing processes may offer a generic quadratic speed-up in realizing such stationary distributions. Such a speed-up would also imply a speed-up of a broad family of heuristic algorithms. However, a true quadratic speed up has thus far only been demonstrated for special classes of MCs. These results often presuppose a regular structure of the underlying graph of the MC, and also a regularity in the transition probabilities. In this work, we demonstrate a true quadratic speed-up for a class of MCs where the restriction is only on the form of the stationary distribution, rather than directly on the MC structure itself. In particular, we show efficient mixing can be achieved when it is known beforehand that the distribution is monotonically decreasing relative to a known order on the state space. Following this, we show that our approach extends to a wider class of distributions, where only a fraction of the shape of the distribution is known to be monotonic. Our approach is built on the Szegedy-type quantization of transition operators.
The preparation of the stationary distribution of irreducible, time-reversible Markov chains (MCs) is a fundamental building block in many heuristic approaches to algorithmically hard problems. It has been conjectured that quantum analogs of classical mixing processes may offer a generic quadratic speed-up in realizing such stationary distributions. Such a speed-up would also imply a speed-up of a broad family of heuristic algorithms. However, a true quadratic speed up has thus far only been demonstrated for special classes of MCs. These results often presuppose a regular structure of the underlying graph of the MC, and also a regularity in the transition probabilities. In this work, we demonstrate a true quadratic speed-up for a class of MCs where the restriction is only on the form of the stationary distribution, rather than directly on the MC structure itself. In particular, we show efficient mixing can be achieved when it is known beforehand that the distribution is monotonically decreasing relative to a known order on the state space. Following this, we show that our approach extends to a wider class of distributions, where only a fraction of the shape of the distribution is known to be monotonic. Our approach is built on the Szegedy-type quantization of transition operators.
In this work we consider the problem of preparation of the stationary distribution of irreducible, time-reversible Markov chains, which is a fundamental task in algorithmic Markov chain theory. For the classical setting, this task has a complexity lower bound of Ω(δ−1), where δ is the spectral gap of the Markov chain, and other dependencies contribute only logarithmically. In the quantum case, the conjectured complexity is O(δ−1), with other dependencies contributing only logarithmically. However, this bound has only been achieved for a few special classes of Markov chains. In this work, we provide a method for the sequential preparation of stationary distributions for sequences of time-reversible N-state Markov chains, akin to the setting of simulated annealing methods. The complexity of preparation we achieve is O(δ−14N), neglecting logarithmic factors. While this result falls short of the conjectured optimal time, it provides a quadratic improvement over na\{i}ve approaches. Moreover, for the case when the output distributions are required to be encoded in pure quantum states we identify the settings where our algorithm is strictly optimal. The settings of slowly evolving sequences of Markov chains naturally appear in reinforcement learning, and consequently our results can be readily applied in quantum machine learning as well.
The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that, given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently, we provided an upper bound on the quantum mixing time for Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic, and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain.
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.
Markov chain methods are remarkably successful in computational physics, machine learning, and combinatorial optimization. The cost of such methods often reduces to the mixing time, i.e., the time required to reach the steady state of the Markov chain, which scales as δ−1 , the inverse of the spectral gap. It has long been conjectured that quantum computers offer nearly generic quadratic improvements for mixing problems. However, except in special cases, quantum algorithms achieve a run-time of O(δ−1N) , which introduces a costly dependence on the Markov chain size N, not present in the classical case. Here, we re-address the problem of mixing of Markov chains when these form a slowly evolving sequence. This setting is akin to the simulated annealing setting and is commonly encountered in physics, material sciences and machine learning. We provide a quantum memory-efficient algorithm with a run-time of O(δ−1N4) , neglecting logarithmic terms, which is an important improvement for large state spaces. Moreover, our algorithms output quantum encodings of distributions, which has advantages over classical outputs. Finally, we discuss the run-time bounds of mixing algorithms and show that, under certain assumptions, our algorithms are optimal.
Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.
Szegedy's quantum walk quadratically accelerates reversible classical Markov chains, but extending this mechanism to efficiently implementable quantum Gibbs samplers has remained challenging beyond special classes. We present a walk-free quantum algorithm for preparing purified Gibbs states with a quadratic improvement in spectral-gap dependence for a broad class of quantum Gibbs samplers that satisfy exact Kubo-Martin-Schwinger detailed balance. Our main structural result is an explicit factorization of the corresponding parent Hamiltonian into noncommutative first-order operators. This turns purified Gibbs-state preparation into a singular-value filtering problem and enables a quantum singular value transformation algorithm with quadratically improved gap dependence under standard coherent-access and warm-start assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. Moreover, we construct noncommuting Hamiltonians with efficiently preparable warm starts whose refinement under quantum Gibbs samplers requires exponential time. For these models, our algorithm achieves an end-to-end quantum speedup over the worst-case mixing scale.