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

Discrepancies between asymptotic and exact spectral-gap analyses of quantum adiabatic barrier tunneling

Lucas T. Brady, Wim van Dam

Published May 30, 2017• 2 citations
arXivHTMLPDF

Abstract

We study the asymptotic behavior of the spectral gap of simple barrier tunneling problems, which are related to using quantum annealing to find the global optimum of cost functions defined over $n$ bits. Specifically we look at the problem of having an $n$ qubit system tunnel through a barrier of width and height proportional to ${n}^{\ensuremath{\alpha}}$. We show that with these quantum annealing problems, the asymptotic, $n\ensuremath{\rightarrow}\ensuremath{\infty}$, behavior of the spectral gap does not accurately describe the behavior of the gap at finite $n$ until extremely large values of $n$ ($n>{10}^{12}$). We prove that this deficiency of the asymptotic expression is a feature of simple one-dimensional tunneling problems themselves, casting doubt on whether asymptotic analysis is an appropriate tool for studying tunneling problems in quantum annealing for reasonably sized systems.

DOI
10.1103/physreva.95.052350

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

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

Bounding first-order quantum phase transitions in adiabatic quantum computing

Matthias Werner, Artur García-Sáez, Marta P. Estarellas

In the context of adiabatic quantum computation (AQC), it has been argued that first-order quantum phase transitions (QPTs) due to localization phenomena cause AQC to fail by exponentially decreasing the minimal spectral gap of the Hamiltonian along the annealing path as a function of the qubit number. The vanishing of the spectral gap is often linked to the localization of the ground state in a local minimum, requiring the system to tunnel into the global minimum at a later stage of the annealing. Recent methods have been proposed to avoid this phenomenon by carefully designing the involved Hamiltonians. However, it remains a challenge to formulate a comprehensive theory of the effect of the various parameters and the conditions under which QPTs make the AQC algorithm fail. Equipped with concepts from graph theory, in this work we link graph quantities associated with the Hamiltonians along the annealing path with the occurrence of QPTs. These links allow us to derive bounds on the location of the minimal spectral gap along the annealing path, augmenting the toolbox for the analysis of strategies to improve the runtime of AQC algorithms.

arXiv:2301.13861•Physical Review Research•Dec 13, 2023•7 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

The performance of the quantum adiabatic algorithm on spike Hamiltonians

Linghang Kong, Elizabeth Crosson

Spike Hamiltonians arise from optimization instances for which the adiabatic algorithm provably out performs classical simulated annealing. In this work, we study the efficiency of the adiabatic algorithm for solving the “the Hamming weight with a spike” problem by analyzing the scaling of the spectral gap at the critical point for various sizes of the barrier. Our main result is a rigorous lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier, which is based on a comparison argument and an improved variational ansatz for the ground state. We also adapt the discrete WKB method for the case of abruptly changing potentials and compare it with the predictions of the spin coherent instanton method which was previously used by Farhi, Goldstone and Gutmann. Finally, our improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited energy states of the thin spike Hamiltonian, and we use a recursion relation to understand the ordering of some of these avoided crossings as a step towards analyzing the previously observed diabatic cascade phenomenon.

arXiv:1511.06991•International Journal of Quantum Information•Feb 7, 2017•17 citations

Avoided level crossings with exponentially closing gaps in quantum annealing

Arthur Braida, Simon Martiel, Ioan Todinca

This paper explores the phenomenon of avoided level crossings in quantum annealing, a promising framework for quantum computing that may provide a quantum advantage for certain tasks. Quantum annealing (QA) involves letting a quantum system evolve according to the Schr\"odinger equation, with the goal of obtaining the optimal solution to an optimization problem through measurements of the final state. However, the continuous nature of quantum annealing makes analytical analysis challenging, particularly with regard to the instantaneous eigenenergies. The adiabatic theorem provides a theoretical result for the annealing time required to obtain the optimal solution with high probability, which is inversely proportional to the square of the minimum spectral gap. Avoided level crossings can create exponentially closing gaps, which can lead to exponentially long running times for optimization problems. In this paper, we use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process. We then apply this condition to the MaxCut problem on bipartite graphs. We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case. On the other hand, we show that irregularities in the vertex degrees can lead to the satisfaction of the avoided level crossing occurrence condition. We provide numerical evidence to support this theoretical development, and discuss the relation between the presence of exponentially closing gaps and the failure of quantum annealing.

arXiv:2304.12872•Physical Review A•Feb 12, 2024•2 citations
We study the asymptotic behavior of the spectral gap of simple barrier tunneling problems, which are related to using quantum annealing to find the global optimum of cost functions defined over nnn bits. Specifically we look at the problem of having an nnn qubit system tunnel through a barrier of width and height proportional to n\ensuremathα{n}^{\ensuremath{\alpha}}n\ensuremathα. We show that with these quantum annealing problems, the asymptotic, n\ensuremath→\ensuremath∞n\ensuremath{\rightarrow}\ensuremath{\infty}n\ensuremath→\ensuremath∞, behavior of the spectral gap does not accurately describe the behavior of the gap at finite nnn until extremely large values of nnn (n>1012n>{10}^{12}n>1012). We prove that this deficiency of the asymptotic expression is a feature of simple one-dimensional tunneling problems themselves, casting doubt on whether asymptotic analysis is an appropriate tool for studying tunneling problems in quantum annealing for reasonably sized systems.
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.
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.
In the context of adiabatic quantum computation (AQC), it has been argued that first-order quantum phase transitions (QPTs) due to localization phenomena cause AQC to fail by exponentially decreasing the minimal spectral gap of the Hamiltonian along the annealing path as a function of the qubit number. The vanishing of the spectral gap is often linked to the localization of the ground state in a local minimum, requiring the system to tunnel into the global minimum at a later stage of the annealing. Recent methods have been proposed to avoid this phenomenon by carefully designing the involved Hamiltonians. However, it remains a challenge to formulate a comprehensive theory of the effect of the various parameters and the conditions under which QPTs make the AQC algorithm fail. Equipped with concepts from graph theory, in this work we link graph quantities associated with the Hamiltonians along the annealing path with the occurrence of QPTs. These links allow us to derive bounds on the location of the minimal spectral gap along the annealing path, augmenting the toolbox for the analysis of strategies to improve the runtime of AQC algorithms.
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.
Spike Hamiltonians arise from optimization instances for which the adiabatic algorithm provably out performs classical simulated annealing. In this work, we study the efficiency of the adiabatic algorithm for solving the “the Hamming weight with a spike” problem by analyzing the scaling of the spectral gap at the critical point for various sizes of the barrier. Our main result is a rigorous lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier, which is based on a comparison argument and an improved variational ansatz for the ground state. We also adapt the discrete WKB method for the case of abruptly changing potentials and compare it with the predictions of the spin coherent instanton method which was previously used by Farhi, Goldstone and Gutmann. Finally, our improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited energy states of the thin spike Hamiltonian, and we use a recursion relation to understand the ordering of some of these avoided crossings as a step towards analyzing the previously observed diabatic cascade phenomenon.
This paper explores the phenomenon of avoided level crossings in quantum annealing, a promising framework for quantum computing that may provide a quantum advantage for certain tasks. Quantum annealing (QA) involves letting a quantum system evolve according to the Schr\"odinger equation, with the goal of obtaining the optimal solution to an optimization problem through measurements of the final state. However, the continuous nature of quantum annealing makes analytical analysis challenging, particularly with regard to the instantaneous eigenenergies. The adiabatic theorem provides a theoretical result for the annealing time required to obtain the optimal solution with high probability, which is inversely proportional to the square of the minimum spectral gap. Avoided level crossings can create exponentially closing gaps, which can lead to exponentially long running times for optimization problems. In this paper, we use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process. We then apply this condition to the MaxCut problem on bipartite graphs. We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case. On the other hand, we show that irregularities in the vertex degrees can lead to the satisfaction of the avoided level crossing occurrence condition. We provide numerical evidence to support this theoretical development, and discuss the relation between the presence of exponentially closing gaps and the failure of quantum annealing.