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:2606.23614

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

Arthur Braida, Elie Bermot, Simon Apers

quant-phcs.DSmath-phSubmitted Jun 22, 2026• Announced Jun 23, 2026• 0 citations
arXivHTMLPDF

Abstract

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

Related papers

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•15 citations

Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions

Dylan Herman, Guneykan Ozgul, Anuj Apte +4 more

We present new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, expanding the scope of quantum advantage beyond traditional tunneling-based explanations. As our main building-block, we demonstrate a rigorous correspondence between the spectral properties of Schrödinger operators and the mixing times of classical Langevin diffusion. This correspondence motivates a mechanism for separation on functions with unique global minimum: while quantum algorithms operate on the original potential, classical diffusions correspond to a Schrödinger operators with a WKB potential having nearly degenerate global minima. We formalize these ideas by proving that a real-space adiabatic quantum algorithm (RsAA) achieves provably polynomial-time optimization for broad families of nonconvex functions. First, for block-separable functions, we show that RsAA maintains polynomial runtime while known off-the-shelf algorithms require exponential time and structure-aware algorithms exhibit arbitrarily large polynomial runtimes. These results leverage novel non-asymptotic results in semiclassical analysis. Second, we use recent advances in the theory of intrinsic hypercontractivity to demonstrate polynomial runtimes for RsAA on appropriately perturbed strongly convex functions that lack global structure, while off-the-shelf algorithms remain exponentially bottlenecked. In contrast to prior works based on quantum tunneling, these separations do not depend on the geometry of barriers between local minima. Our theoretical claims about classical algorithm runtimes are supported by rigorous analysis and comprehensive numerical benchmarking. These findings establish a rigorous theoretical foundation for quantum advantage in continuous optimization and open new research directions connecting quantum algorithms, stochastic processes, and semiclassical analysis.

arXiv:2510.03385•Oct 3, 2025•8 citations

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•15 citations

When Diabatic Trumps Adiabatic in Quantum Optimization

Siddharth Muthukrishnan, Tameem Albash, Daniel A. Lidar

We provide and analyze examples that counter the widely made claim that tunneling is needed for a quantum speedup in optimization problems. The examples belong to the class of perturbed Hamming-weight optimization problems. In one case, featuring a plateau in the cost function in Hamming weight space, we find that the adiabatic dynamics that make tunneling possible, while superior to simulated annealing, result in a slowdown compared to a diabatic cascade of avoided level-crossings. This, in turn, inspires a classical spin vector dynamics algorithm that is at least as efficient for the plateau problem as the diabatic quantum algorithm. In a second case whose cost function is convex in Hamming weight space, the diabatic cascade results in a speedup relative to both tunneling and classical spin vector dynamics.

arXiv:1505.01249•May 6, 2015•16 citations

A quantum analogue of convex optimization

Eunou Lee

Convex optimization is the powerhouse behind the theory and practice of optimization. We introduce a quantum analogue of unconstrained convex optimization: computing the minimum eigenvalue of a Schrödinger operator $h = -Δ+ V $ with convex potential $V:\mathbb R^n \rightarrow \mathbb R_{\ge 0}$ such that $V(x)\rightarrow\infty $ as $\|x\|\rightarrow\infty$. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of $h$ up to error $ε$ in polynomial time in $n$, $1/ε$, and parameters that depend on $V$. Adiabatic evolution of the ground state is used as a key subroutine, which we analyze with novel techniques that allow us to focus on the low-energy space. We apply the FGA to give the first known polynomial-time algorithm for finding the lowest frequency of an $n$-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an $n$-dimensional region that is defined by $m$ linear constraints in polynomial time in $n$, $m$, $1/ε$ and the radius $R$ of a ball encompassing the region.

arXiv:2510.02151•Oct 2, 2025•1 citation

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•9 citations
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
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.
We present new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, expanding the scope of quantum advantage beyond traditional tunneling-based explanations. As our main building-block, we demonstrate a rigorous correspondence between the spectral properties of Schrödinger operators and the mixing times of classical Langevin diffusion. This correspondence motivates a mechanism for separation on functions with unique global minimum: while quantum algorithms operate on the original potential, classical diffusions correspond to a Schrödinger operators with a WKB potential having nearly degenerate global minima. We formalize these ideas by proving that a real-space adiabatic quantum algorithm (RsAA) achieves provably polynomial-time optimization for broad families of nonconvex functions. First, for block-separable functions, we show that RsAA maintains polynomial runtime while known off-the-shelf algorithms require exponential time and structure-aware algorithms exhibit arbitrarily large polynomial runtimes. These results leverage novel non-asymptotic results in semiclassical analysis. Second, we use recent advances in the theory of intrinsic hypercontractivity to demonstrate polynomial runtimes for RsAA on appropriately perturbed strongly convex functions that lack global structure, while off-the-shelf algorithms remain exponentially bottlenecked. In contrast to prior works based on quantum tunneling, these separations do not depend on the geometry of barriers between local minima. Our theoretical claims about classical algorithm runtimes are supported by rigorous analysis and comprehensive numerical benchmarking. These findings establish a rigorous theoretical foundation for quantum advantage in continuous optimization and open new research directions connecting quantum algorithms, stochastic processes, and semiclassical analysis.
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 provide and analyze examples that counter the widely made claim that tunneling is needed for a quantum speedup in optimization problems. The examples belong to the class of perturbed Hamming-weight optimization problems. In one case, featuring a plateau in the cost function in Hamming weight space, we find that the adiabatic dynamics that make tunneling possible, while superior to simulated annealing, result in a slowdown compared to a diabatic cascade of avoided level-crossings. This, in turn, inspires a classical spin vector dynamics algorithm that is at least as efficient for the plateau problem as the diabatic quantum algorithm. In a second case whose cost function is convex in Hamming weight space, the diabatic cascade results in a speedup relative to both tunneling and classical spin vector dynamics.
Convex optimization is the powerhouse behind the theory and practice of optimization. We introduce a quantum analogue of unconstrained convex optimization: computing the minimum eigenvalue of a Schrödinger operator $h = -Δ+ V $ with convex potential V:Rn→R≥0V:\mathbb R^n \rightarrow \mathbb R_{\ge 0}V:Rn→R≥0​ such that $V(x)\rightarrow\infty $ as ∥x∥→∞\|x\|\rightarrow\infty∥x∥→∞. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of hhh up to error εεε in polynomial time in nnn, 1/ε1/ε1/ε, and parameters that depend on VVV. Adiabatic evolution of the ground state is used as a key subroutine, which we analyze with novel techniques that allow us to focus on the low-energy space. We apply the FGA to give the first known polynomial-time algorithm for finding the lowest frequency of an nnn-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an nnn-dimensional region that is defined by mmm linear constraints in polynomial time in nnn, mmm, 1/ε1/ε1/ε and the radius RRR of a ball encompassing the region.
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.