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:1509.02562 · Physical Review A

Quantum Monte Carlo simulations of tunneling in quantum adiabatic optimization

Lucas T. Brady, Wim van Dam

Published Mar 4, 2016• 29 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.93.032304

Related papers

Spectral-gap analysis for efficient tunneling in quantum adiabatic optimization

Lucas T. Brady, Wim van Dam

We investigate the efficiency of quantum adiabatic optimization when overcoming potential barriers to get from a local to a global minimum. Specifically we look at $n$ qubit systems with symmetric cost functions $f:{{0,1}}^{n}\ensuremath{\rightarrow}\mathbb{R}$, where the ground state must tunnel through a potential barrier of width ${n}^{\ensuremath{\alpha}}$ and height ${n}^{\ensuremath{\beta}}$. By the quantum adiabatic theorem the time delay sufficient to ensure tunneling grows quadratically with the inverse spectral gap during this tunneling process. We analyze barrier sizes with $1/2\ensuremath{\le}\ensuremath{\alpha}+\ensuremath{\beta}$ and $\ensuremath{\alpha}<1/2$ and show that the minimum gap scales polynomially as ${n}^{1/2\ensuremath{-}\ensuremath{\alpha}\ensuremath{-}\ensuremath{\beta}}$ when $2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{\le}1$ and exponentially as ${n}^{\ensuremath{-}\ensuremath{\beta}/2}exp(\ensuremath{-}C{n}^{(2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{-}1)/2})$ when $1<2\ensuremath{\alpha}+\ensuremath{\beta}$. Our proof uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone from 2002, which used large spin and instanton methods. Parts of our result also refine recent results by Kong and Crosson [arXiv:1511.06991] and Jiang et al. [arXiv:1603.01293] about the exponential gap scaling.

arXiv:1601.01720•Physical Review A•Sep 9, 2016•17 citations

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

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

Quantum path minimization: An efficient method for global optimization

Pu Liu, B. J. Berne

A new unbiased global optimization approach is proposed, based on quantum staging path integral Monte Carlo sampling and local minimization of individual imaginary time slices. This algorithm uses the quantum tunneling effect to speed up the crossing of energy barriers. This method differs in important ways from previous work on quantum annealing and is able to find all the global minima of Lennard-Jones clusters of size up to N=100, except for N=76, 77, and 98. The comparison between this new algorithm and several other classes of algorithms is presented.

The Journal of Chemical Physics•Feb 10, 2003•33 citations

Understanding quantum tunneling using diffusion Monte Carlo simulations

Estelle M. Inack, Giuliano Giudici, Tommaso Parolini +2 more

In simple ferromagnetic quantum Ising models characterized by an effective double-well energy landscape the characteristic tunneling time of path-integral Monte Carlo (PIMC) simulations has been shown to scale as the incoherent quantum-tunneling time, i.e., as $1/{\mathrm{\ensuremath{\Delta}}}^{2}$, where $\mathrm{\ensuremath{\Delta}}$ is the tunneling gap. Since incoherent quantum tunneling is employed by quantum annealers (QAs) to solve optimization problems, this result suggests that there is no quantum advantage in using QAs with respect to quantum Monte Carlo (QMC) simulations. A counterexample is the recently introduced shamrock model (Andriyash and Amin, arXiv:1703.09277), where topological obstructions cause an exponential slowdown of the PIMC tunneling dynamics with respect to incoherent quantum tunneling, leaving open the possibility for potential quantum speedup, even for stoquastic models. In this work we investigate the tunneling time of projective QMC simulations based on the diffusion Monte Carlo (DMC) algorithm without guiding functions, showing that it scales as $1/\mathrm{\ensuremath{\Delta}}$, i.e., even more favorably than the incoherent quantum-tunneling time, both in a simple ferromagnetic system and in the more challenging shamrock model. However, a careful comparison between the DMC ground-state energies and the exact solution available for the transverse-field Ising chain indicates an exponential scaling of the computational cost required to keep a fixed relative error as the system size increases.

arXiv:1711.08027•Physical Review A•Mar 8, 2018•18 citations

Quantum Adiabatic Evolution Algorithms versus Simulated Annealing

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

We explain why quantum adiabatic evolution and simulated annealing perform similarly in certain examples of searching for the minimum of a cost function of n bits. In these examples each bit is treated symmetrically so the cost function depends only on the Hamming weight of the n bits. We also give two examples, closely related to these, where the similarity breaks down in that the quantum adiabatic algorithm succeeds in polynomial time whereas simulated annealing requires exponential time.

arXiv:quant-ph/0201031•Jan 8, 2002•83 citations
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.
We investigate the efficiency of quantum adiabatic optimization when overcoming potential barriers to get from a local to a global minimum. Specifically we look at nnn qubit systems with symmetric cost functions $f:{{0,1}}^{n}\ensuremath{\rightarrow}\mathbb{R}$, where the ground state must tunnel through a potential barrier of width ${n}^{\ensuremath{\alpha}}$ and height ${n}^{\ensuremath{\beta}}$. By the quantum adiabatic theorem the time delay sufficient to ensure tunneling grows quadratically with the inverse spectral gap during this tunneling process. We analyze barrier sizes with $1/2\ensuremath{\le}\ensuremath{\alpha}+\ensuremath{\beta}$ and $\ensuremath{\alpha}<1/2$ and show that the minimum gap scales polynomially as ${n}^{1/2\ensuremath{-}\ensuremath{\alpha}\ensuremath{-}\ensuremath{\beta}}$ when $2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{\le}1$ and exponentially as ${n}^{\ensuremath{-}\ensuremath{\beta}/2}exp(\ensuremath{-}C{n}^{(2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{-}1)/2})$ when $1<2\ensuremath{\alpha}+\ensuremath{\beta}$. Our proof uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone from 2002, which used large spin and instanton methods. Parts of our result also refine recent results by Kong and Crosson [arXiv:1511.06991] and Jiang et al. [arXiv:1603.01293] about the exponential gap scaling.
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.
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.
A new unbiased global optimization approach is proposed, based on quantum staging path integral Monte Carlo sampling and local minimization of individual imaginary time slices. This algorithm uses the quantum tunneling effect to speed up the crossing of energy barriers. This method differs in important ways from previous work on quantum annealing and is able to find all the global minima of Lennard-Jones clusters of size up to N=100, except for N=76, 77, and 98. The comparison between this new algorithm and several other classes of algorithms is presented.
In simple ferromagnetic quantum Ising models characterized by an effective double-well energy landscape the characteristic tunneling time of path-integral Monte Carlo (PIMC) simulations has been shown to scale as the incoherent quantum-tunneling time, i.e., as $1/{\mathrm{\ensuremath{\Delta}}}^{2}$, where $\mathrm{\ensuremath{\Delta}}$ is the tunneling gap. Since incoherent quantum tunneling is employed by quantum annealers (QAs) to solve optimization problems, this result suggests that there is no quantum advantage in using QAs with respect to quantum Monte Carlo (QMC) simulations. A counterexample is the recently introduced shamrock model (Andriyash and Amin, arXiv:1703.09277), where topological obstructions cause an exponential slowdown of the PIMC tunneling dynamics with respect to incoherent quantum tunneling, leaving open the possibility for potential quantum speedup, even for stoquastic models. In this work we investigate the tunneling time of projective QMC simulations based on the diffusion Monte Carlo (DMC) algorithm without guiding functions, showing that it scales as $1/\mathrm{\ensuremath{\Delta}}$, i.e., even more favorably than the incoherent quantum-tunneling time, both in a simple ferromagnetic system and in the more challenging shamrock model. However, a careful comparison between the DMC ground-state energies and the exact solution available for the transverse-field Ising chain indicates an exponential scaling of the computational cost required to keep a fixed relative error as the system size increases.