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

Spectral-gap analysis for efficient tunneling in quantum adiabatic optimization

Lucas T. Brady, Wim van Dam

Published Sep 9, 2016• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.94.032309

Related papers

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

Lucas T. Brady, Wim van Dam

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.

arXiv:1609.09137•Physical Review A•May 30, 2017•2 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

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

Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds

Shane Dooley, Graham Kells, Hosho Katsura +1 more

Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps $L$. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\ensuremath{\gg}1$ is ${min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.

arXiv:1906.05233•Physical Review A•Apr 1, 2020•5 citations

Log-concavity and tunneling: adiabatic quantum optimization for convex functions (with a spike)

Arthur Braida, Elie Bermot, Simon Apers

Quantum tunneling is expected to provide a computational speedup in quantum computing, a phenomenon that Adiabatic Quantum Optimization (AQO) aims to leverage. While some academic proofs of concept have been studied, such as the "Hamming weight with a spike" (HWS) problem, the algorithmic gains of this effect remain underexplored. In this work we extend the analysis underlying HWS to more general potentials. In the first half of the work, we establish (discrete) log-concavity of the ground state as a key structural property in this context. We devise a framework for establishing log-concavity of the ground state for a large family of discrete, 1-dimensional Schrödinger operators. The family includes convex potentials, but also certain potentials with local minima. In the convex case, this provides a discrete version of a continuous result by Brascamp and Lieb ('76). We demonstrate the utility of our result by establishing new spectral gap bounds, going beyond related results by Jarret and Jordan ('14) for convex potentials. In the second half of the work, we use our results on log-concavity to extend the perturbative analysis of HWS by Reichardt ('04) to the larger family of potentials with log-concave ground state. As a concrete instantiation, we use our result to extend the HWS analysis from a linear potential (which is exactly solvable) to a quadratic potential (which is no longer solvable). Our result strongly suggests the broader applicability of tunneling to convex potentials with spikes

quant-pharXiv:2606.23614•Jun 23, 2026•0 citations

Adiabatic optimization without local minima

Michael Jarret, Stephen P. Jordan

Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two "lobes" separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices.

arXiv:1405.7552•May 29, 2014•0 citations
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,1n\ensuremath→Rf:{{0,1}}^{n}\ensuremath{\rightarrow}\mathbb{R}f:0,1n\ensuremath→R, where the ground state must tunnel through a potential barrier of width n\ensuremathα{n}^{\ensuremath{\alpha}}n\ensuremathα and height n\ensuremathβ{n}^{\ensuremath{\beta}}n\ensuremathβ. 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≤\ensuremathα+\ensuremathβ1/2\ensuremath{\le}\ensuremath{\alpha}+\ensuremath{\beta}1/2\ensuremath≤\ensuremathα+\ensuremathβ and \ensuremathα<1/2\ensuremath{\alpha}<1/2\ensuremathα<1/2 and show that the minimum gap scales polynomially as n1/2\ensuremath−\ensuremathα\ensuremath−\ensuremathβ{n}^{1/2\ensuremath{-}\ensuremath{\alpha}\ensuremath{-}\ensuremath{\beta}}n1/2\ensuremath−\ensuremathα\ensuremath−\ensuremathβ when 2\ensuremathα+\ensuremathβ\ensuremath≤12\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{\le}12\ensuremathα+\ensuremathβ\ensuremath≤1 and exponentially as n\ensuremath−\ensuremathβ/2exp(\ensuremath−Cn(2\ensuremathα+\ensuremathβ\ensuremath−1)/2){n}^{\ensuremath{-}\ensuremath{\beta}/2}exp(\ensuremath{-}C{n}^{(2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{-}1)/2})n\ensuremath−\ensuremathβ/2exp(\ensuremath−Cn(2\ensuremathα+\ensuremathβ\ensuremath−1)/2) when 1<2\ensuremathα+\ensuremathβ1<2\ensuremath{\alpha}+\ensuremath{\beta}1<2\ensuremathα+\ensuremathβ. 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 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{\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 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 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.
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.
Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps LLL. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\ensuremath{\gg}1$ is ${min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.
Quantum tunneling is expected to provide a computational speedup in quantum computing, a phenomenon that Adiabatic Quantum Optimization (AQO) aims to leverage. While some academic proofs of concept have been studied, such as the "Hamming weight with a spike" (HWS) problem, the algorithmic gains of this effect remain underexplored. In this work we extend the analysis underlying HWS to more general potentials. In the first half of the work, we establish (discrete) log-concavity of the ground state as a key structural property in this context. We devise a framework for establishing log-concavity of the ground state for a large family of discrete, 1-dimensional Schrödinger operators. The family includes convex potentials, but also certain potentials with local minima. In the convex case, this provides a discrete version of a continuous result by Brascamp and Lieb ('76). We demonstrate the utility of our result by establishing new spectral gap bounds, going beyond related results by Jarret and Jordan ('14) for convex potentials. In the second half of the work, we use our results on log-concavity to extend the perturbative analysis of HWS by Reichardt ('04) to the larger family of potentials with log-concave ground state. As a concrete instantiation, we use our result to extend the HWS analysis from a linear potential (which is exactly solvable) to a quadratic potential (which is no longer solvable). Our result strongly suggests the broader applicability of tunneling to convex potentials with spikes
Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two "lobes" separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices.