Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Sequential quantum mixing for slowly evolving sequences of Markov chains.

Vedran Dunjko, Hans J. Briegel

Published Mar 4, 2015• 4 citations
OpenAlex

Abstract

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 $\Omega(\delta^{-1})$, where $\delta$ is the spectral gap of the Markov chain, and other dependencies contribute only logarithmically. In the quantum case, the conjectured complexity is $O(\sqrt{\delta^{-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(\sqrt{\delta^{-1}} \sqrt[4]{N})$, 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.

Related papers

Faster quantum mixing for slowly evolving sequences of Markov chains

Davide Orsucci, Hans J. Briegel, Vedran Dunjko

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.

arXiv:1503.01334•Quantum•Nov 9, 2018•20 citations

Quantum mixing of Markov chains for special distributions

Vedran Dunjko, Hans J. Briegel

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.

arXiv:1502.05511•New Journal of Physics•Jul 3, 2015•17 citations

Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions

Aram W. Harrow, Annie Y. Wei

Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule. We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution. In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.

arXiv:1907.09965•Society for Industrial and Applied Mathematics eBooks•Dec 23, 2019•20 citations

Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains

Nicholas Zhao

Preparing quantum samples (QSAMPLES), coherent encodings of stationary distributions of reversible Markov chains, is a fundamental primitive in quantum sampling, particularly for quantum simulated annealing. A central limitation of existing phase-estimation-based frameworks is the ancilla qubit overhead. In this work, we present a new end-to-end framework requiring only one ancilla qubit in the working register. The key technical ingredient is a selective phase compiler circuit using one ancilla qubit, built from a generalized quantum signal processing (GQSP)-based projector onto the 1-eigenspace of the qubitized Szegedy walk. Embedding these selective phase compilers into the fixed-point amplitude amplification (FPAA) procedure and iterating yields a quantum algorithm that, given an initial state, oracle access, lower bounds on the overlaps between adjacent states, and lower bounds on the phase gaps, outputs a QSAMPLE within any desired trace distance and thus total variation distance. The query complexity scales inversely with the square roots of both the minimum overlap and the minimum spectral gap of the Markov chains across the cooling schedule, up to polylogarithmic factors. We also perform simulations to verify how our qubit and query complexity evolve with the trace distance, and how this work compares to the previous framework. These results establish two improvements over the previous framework by Wocjan and Abeyesinghe. First, the working-register ancilla cost is reduced to one. Second, by inserting our GQSP-based selective phase compiler into the FPAA procedure, we improve the QSAMPLE transport overlap dependence from inverse minimum overlap to inverse square-root minimum overlap, relative to their Grover pi-over-three fixed-point method. Finally, as a direct application, we apply the quantum algorithm to prepare a Gibbs QSAMPLE and obtain a rigorous complexity analysis.

quant-pharXiv:2605.23442•May 25, 2026•0 citations

Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions

Harrow, AW, Wei, AY

Copyright © 2020 by SIAM Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule. We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution. In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.

•Jan 1, 2020•26 citations

Faster quantum sampling of Markov chains in nonregular graphs with fewer qubits

Xinying Li, Yun Shang

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.

arXiv:2205.06099•Physical Review A•Feb 27, 2023•2 citations
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)\Omega(\delta^{-1})Ω(δ−1), where δ\deltaδ is the spectral gap of the Markov chain, and other dependencies contribute only logarithmically. In the quantum case, the conjectured complexity is O(δ−1)O(\sqrt{\delta^{-1}})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 NNN-state Markov chains, akin to the setting of simulated annealing methods. The complexity of preparation we achieve is O(δ−1N4)O(\sqrt{\delta^{-1}} \sqrt[4]{N})O(δ−1​4N​), 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.
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.
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.
Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule. We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution. In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.
Preparing quantum samples (QSAMPLES), coherent encodings of stationary distributions of reversible Markov chains, is a fundamental primitive in quantum sampling, particularly for quantum simulated annealing. A central limitation of existing phase-estimation-based frameworks is the ancilla qubit overhead. In this work, we present a new end-to-end framework requiring only one ancilla qubit in the working register. The key technical ingredient is a selective phase compiler circuit using one ancilla qubit, built from a generalized quantum signal processing (GQSP)-based projector onto the 1-eigenspace of the qubitized Szegedy walk. Embedding these selective phase compilers into the fixed-point amplitude amplification (FPAA) procedure and iterating yields a quantum algorithm that, given an initial state, oracle access, lower bounds on the overlaps between adjacent states, and lower bounds on the phase gaps, outputs a QSAMPLE within any desired trace distance and thus total variation distance. The query complexity scales inversely with the square roots of both the minimum overlap and the minimum spectral gap of the Markov chains across the cooling schedule, up to polylogarithmic factors. We also perform simulations to verify how our qubit and query complexity evolve with the trace distance, and how this work compares to the previous framework. These results establish two improvements over the previous framework by Wocjan and Abeyesinghe. First, the working-register ancilla cost is reduced to one. Second, by inserting our GQSP-based selective phase compiler into the FPAA procedure, we improve the QSAMPLE transport overlap dependence from inverse minimum overlap to inverse square-root minimum overlap, relative to their Grover pi-over-three fixed-point method. Finally, as a direct application, we apply the quantum algorithm to prepare a Gibbs QSAMPLE and obtain a rigorous complexity analysis.
Copyright © 2020 by SIAM Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule. We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution. In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.
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 lognlognlogn, where nnn 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.