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

arXiv:1607.03389 · Physical Review A

Adiabatic optimization versus diffusion Monte Carlo methods

Michael Jarret, Stephen P. Jordan, Brad Lackey

Published Oct 13, 2016• 36 citations
arXivHTMLPDF

Abstract

Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between ${L}_{1}$ and ${L}_{2}$ normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-$k$-SAT at $k=2,3,4$.

DOI
10.1103/physreva.94.042318

Related papers

Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians

Jacob Bringewatt, W. Dorland, Stephen P. Jordan +1 more

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path-integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-$k$-SAT problems, use $k$-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved $n$-body interactions. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

arXiv:1709.03971•Physical Review A•Feb 15, 2018•12 citations

Substochastic Monte Carlo Algorithms

Michael Jarret, Brad Lackey

In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, "Go-With-The-Winners" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics. Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-$k$-SAT.

arXiv:1704.09014•Apr 28, 2017•5 citations

Multiqubit Tunneling and Evolution in Quantum Annealing

Lucas T. Brady

Quantum computing seeks to use the powers of quantum mechanics to accomplish tasks that classical computers cannot easily accomplish. Adiabatic quantum computing is one flavor of quantum computing that slowly changes a system with time in such a way that the state remains close to the ground state for the entire evolution. An easy way to implement and study adiabatic computing is using stoquastic Hamiltonians with no-sign problem. These Hamiltonians can be readily simulated on classical computers using quantum Monte Carlo schemes; though, it is unknown whether such simulation captures the speed and power of the quantum computation.In this work, I study stoquastic Hamiltonians, focusing on quantum mechanical tunneling through classically inaccessible regions and barriers. I study multi-qubit tunneling problems to determine what properties of the barrier make this problem quantum mechanically or classically hard or inefficient. I compare quantum adiabatic computing with a path-integral Quantum Monte Carlo algorithm, which is a classical algorithm designed to simulate the quantum mechanical dynamics of the adiabatic evolution. Limited numerical data shows strong correlation between adiabatic and Monte Carlo runtimes, but due to computational limits, only small system sizes could be sampled.Additionally, I study the properties of the quantum adiabatic algorithm in both the asymptotic limit of a large number of qubits and long runtimes and more realistic finite system sizes and non-adiabatic conditions. I develop a modification of the existing Villain transformation that allows it to find the asymptotic running time of the quantum evolution for different barrier sizes. Furthermore, I compare this to finite system sizes and discover the extremely large numbers of qubits are needed for these asymptotics to be useful.When the quantum dynamics are run faster than adiabatically, new behavior arises that could potentially lead to enhancements in the quantum runtimes. I explore these enhancements, discovering when they do and do not occur. I also develop a broad framework for determining the nature of the near-adiabatic behavior of any quantum evolution, using only information about the energy gap between the ground state and the first excited state.

•Jan 1, 2018•0 citations

First- and quasi-second-order optimization algorithms in variational Monte Carlo

Ruojing Peng, Garnet Kin‐Lic Chan

Many quantum many-body wavefunctions, such as Jastrow-Slater, tensor network, and neural quantum states, are studied with the variational Monte Carlo technique, where stochastic optimization is usually performed to obtain a faithful approximation to the ground state of a given Hamiltonian. While first-order gradient descent methods are commonly used for such optimizations, quasi-second-order optimization formulations offer the potential of faster convergence under certain theoretical conditions, but with a similar cost per sample to first-order methods. However, the relative performance of first- and second-order optimizers is influenced in practice by many factors, including the sampling requirements for a faithful optimization step, the influence of wavefunction quality, as well as the wavefunction parametrization and expressivity. Here, we analyze these performance characteristics of first- and quasi-second-order optimization methods for a variety of Hamiltonians, with the additional context of understanding the scaling of these methods (for good performance) as a function of system size. Our findings help clarify the role of first- and quasi-second-order methods in variational Monte Carlo calculations and the conditions under which they should respectively be used. In particular, we find that unlike in deterministic optimization, where closeness to the variational minimum determines the suitability of second-order methods, in stochastic optimization the main factor is the overall expressivity of the wavefunction: Quasi-second-order methods lead to an overall reduction in cost relative to first-order methods when the wavefunction is sufficiently expressive to represent the ground state, even when starting far away from the ground state. This makes quasi-second-order methods an important technique when used with wavefunctions with arbitrarily improvable accuracy.

arXiv:2502.19576•Physical Review Research•Dec 7, 2025•1 citation

RANDOM WALKS NEAR ROKHSAR–KIVELSON POINTS

Olav F. Syljuåsen

There is a class of quantum Hamiltonians known as Rokhsar–Kivelson (RK)–Hamiltonians for which static ground state properties can be obtained by evaluating thermal expectation values for classical models. The ground state of an RK–Hamiltonian is known explicitly, and its dynamical properties can be obtained by performing a classical Monte Carlo simulation. We discuss the details of a Diffusion Monte Carlo method that is a good tool for studying statics and dynamics of perturbed RK–Hamiltonians without time discretization errors. As a general result we point out that the relation between the quantum dynamics and classical Monte Carlo simulations for RK–Hamiltonians follows from the known fact that the imaginary-time evolution operator describing optimal importance sampling, where the exact ground state is used as guiding function, is Markovian. Thus quantum dynamics can be studied by classical Monte Carlo for any Hamiltonian provided its ground state is known explicitly and that there is no sign problem.

arXiv:cond-mat/0504195•International Journal of Modern Physics B•May 10, 2005•11 citations

Quantum Monte Carlo simulations of tunneling in quantum adiabatic optimization

Lucas T. Brady, Wim van Dam

We explore to what extent path-integral quantum Monte Carlo methods can efficiently simulate quantum adiabatic optimization algorithms during a quantum tunneling process. Specifically we look at symmetric cost functions defined over $n$ bits with a single potential barrier that a successful quantum adiabatic optimization algorithm will have to tunnel through. The height and width of this barrier depend on $n$, and by tuning these dependencies, we can make the optimization algorithm succeed or fail in polynomial time. In this article we compare the strength of quantum adiabatic tunneling with that of path-integral quantum Monte Carlo methods. We find numerical evidence that quantum Monte Carlo algorithms will succeed in the same regimes where quantum adiabatic optimization succeeds.

arXiv:1509.02562•Physical Review A•Mar 4, 2016•29 citations
Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1{L}_{1}L1​ and L2{L}_{2}L2​ normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-kkk-SAT at k=2,3,4k=2,3,4k=2,3,4.
Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path-integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-kkk-SAT problems, use kkk-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved nnn-body interactions. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.
In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, "Go-With-The-Winners" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics. Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-kkk-SAT.
Quantum computing seeks to use the powers of quantum mechanics to accomplish tasks that classical computers cannot easily accomplish. Adiabatic quantum computing is one flavor of quantum computing that slowly changes a system with time in such a way that the state remains close to the ground state for the entire evolution. An easy way to implement and study adiabatic computing is using stoquastic Hamiltonians with no-sign problem. These Hamiltonians can be readily simulated on classical computers using quantum Monte Carlo schemes; though, it is unknown whether such simulation captures the speed and power of the quantum computation.In this work, I study stoquastic Hamiltonians, focusing on quantum mechanical tunneling through classically inaccessible regions and barriers. I study multi-qubit tunneling problems to determine what properties of the barrier make this problem quantum mechanically or classically hard or inefficient. I compare quantum adiabatic computing with a path-integral Quantum Monte Carlo algorithm, which is a classical algorithm designed to simulate the quantum mechanical dynamics of the adiabatic evolution. Limited numerical data shows strong correlation between adiabatic and Monte Carlo runtimes, but due to computational limits, only small system sizes could be sampled.Additionally, I study the properties of the quantum adiabatic algorithm in both the asymptotic limit of a large number of qubits and long runtimes and more realistic finite system sizes and non-adiabatic conditions. I develop a modification of the existing Villain transformation that allows it to find the asymptotic running time of the quantum evolution for different barrier sizes. Furthermore, I compare this to finite system sizes and discover the extremely large numbers of qubits are needed for these asymptotics to be useful.When the quantum dynamics are run faster than adiabatically, new behavior arises that could potentially lead to enhancements in the quantum runtimes. I explore these enhancements, discovering when they do and do not occur. I also develop a broad framework for determining the nature of the near-adiabatic behavior of any quantum evolution, using only information about the energy gap between the ground state and the first excited state.
Many quantum many-body wavefunctions, such as Jastrow-Slater, tensor network, and neural quantum states, are studied with the variational Monte Carlo technique, where stochastic optimization is usually performed to obtain a faithful approximation to the ground state of a given Hamiltonian. While first-order gradient descent methods are commonly used for such optimizations, quasi-second-order optimization formulations offer the potential of faster convergence under certain theoretical conditions, but with a similar cost per sample to first-order methods. However, the relative performance of first- and second-order optimizers is influenced in practice by many factors, including the sampling requirements for a faithful optimization step, the influence of wavefunction quality, as well as the wavefunction parametrization and expressivity. Here, we analyze these performance characteristics of first- and quasi-second-order optimization methods for a variety of Hamiltonians, with the additional context of understanding the scaling of these methods (for good performance) as a function of system size. Our findings help clarify the role of first- and quasi-second-order methods in variational Monte Carlo calculations and the conditions under which they should respectively be used. In particular, we find that unlike in deterministic optimization, where closeness to the variational minimum determines the suitability of second-order methods, in stochastic optimization the main factor is the overall expressivity of the wavefunction: Quasi-second-order methods lead to an overall reduction in cost relative to first-order methods when the wavefunction is sufficiently expressive to represent the ground state, even when starting far away from the ground state. This makes quasi-second-order methods an important technique when used with wavefunctions with arbitrarily improvable accuracy.
There is a class of quantum Hamiltonians known as Rokhsar–Kivelson (RK)–Hamiltonians for which static ground state properties can be obtained by evaluating thermal expectation values for classical models. The ground state of an RK–Hamiltonian is known explicitly, and its dynamical properties can be obtained by performing a classical Monte Carlo simulation. We discuss the details of a Diffusion Monte Carlo method that is a good tool for studying statics and dynamics of perturbed RK–Hamiltonians without time discretization errors. As a general result we point out that the relation between the quantum dynamics and classical Monte Carlo simulations for RK–Hamiltonians follows from the known fact that the imaginary-time evolution operator describing optimal importance sampling, where the exact ground state is used as guiding function, is Markovian. Thus quantum dynamics can be studied by classical Monte Carlo for any Hamiltonian provided its ground state is known explicitly and that there is no sign problem.
We explore to what extent path-integral quantum Monte Carlo methods can efficiently simulate quantum adiabatic optimization algorithms during a quantum tunneling process. Specifically we look at symmetric cost functions defined over nnn bits with a single potential barrier that a successful quantum adiabatic optimization algorithm will have to tunnel through. The height and width of this barrier depend on nnn, and by tuning these dependencies, we can make the optimization algorithm succeed or fail in polynomial time. In this article we compare the strength of quantum adiabatic tunneling with that of path-integral quantum Monte Carlo methods. We find numerical evidence that quantum Monte Carlo algorithms will succeed in the same regimes where quantum adiabatic optimization succeeds.