Log-concavity and tunneling: adiabatic quantum optimization for convex functions (with a spike)
Arthur Braida, Elie Bermot, Simon Apers · 2026
Read Log-concavity and tunneling: adiabatic quantum optimization for convex functions (with a spike) by Arthur Braida, Elie Bermot, Simon Apers (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-23614.txt.
Introduction
Braida, Bermot, and Apers extend the theory of quantum tunneling speedups to a broad family of cost functions, in a 2026 paper on quantum algorithms. Adiabatic quantum optimization seeks the minimum of a cost function by slowly morphing a simple quantum system into one encoding the problem. Quantum tunneling through barriers is its hoped for advantage over classical search. A famous test case adds a spike to the Hamming weight function, trapping classical methods while tunneling crosses.
The authors identify log concavity of the ground state, a shape property of the quantum state's profile, as the key structure behind the test case. They prove log concavity for many one dimensional Schrödinger operators, including convex potentials and some with local minima, and new spectral gap bounds follow. A perturbation analysis then carries the spike results from a linear potential to a quadratic one, suggesting broad tunneling gains.
Catalog record
| CREATOR | Arthur Braida, Elie Bermot, Simon Apers |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.23614
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Log-concavity and tunneling: adiabatic quantum optimization for convex functions (with a spike) Arthur Braida, Elie Bermot, Simon Apers 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 [ 9 ] . We demonstrate the utility of our result by establishing new spectral gap bounds, going beyond related results by Jarret and Jordan [ 18 ] 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 [ 33 ] 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. 1 Introduction Adiabatic quantum optimization (AQO) was introduced as a method for finding the minima of complicated cost functions V\mathrel{\mathop{\mathchar 58\relax}}\{0,1\}^{n}\to\mathbb{R} on the hypercube, leveraging quantum fluctuations to escape local minima that trap classical algorithms [ 14 , 22 , 12 ] . Its theoretical analysis reduces to understanding the spectral gap of the interpolating Hamiltonian H(s)=-(1-s)\sum_{i=1}^{n}X_{i}+sV (1) for s\in[0,1] , where X_{i} is the Pauli- X operator acting on the i -th qubit, and V is the diagonal operator satisfying V\ket{x}=V(x)\ket{x} for x\in\{0,1\}^{n} . If the gap remains at least inverse-polynomially large in n throughout the annealing path, then the adiabatic theorem guarantees that the target ground state can be prepared efficiently. However, establishing lower bounds on the gap is in general a hard problem, and the cases where it can be done rigorously are relatively few – see e.g. [ 12 , 34 , 1 , 33 , 17 , 15 , 8 , 26 ] for some examples. A large part of the results concerns the restrictive yet still interesting family of cost functions that is called “symmetric”, satisfying V(x)=V(|x|) . A canonical such function is the Hamming weight function V(x)=|x| . Due to the exact solvability of the adiabatic Hamiltonian for this potential, a significant body of work was devoted to the performance of AQO for perturbations of this function [ 13 , 25 , 32 , 33 , 7 , 5 ] . The resulting “Hamming weight with a spike” problem (HWS) concerns potentials of the form V(x)=|x|+h(x) , for some perturbation or “spike” h . While such a spike can create local minima and obstruct classical methods such as simulated annealing, the aforementioned works derive precise conditions on the shape of the spike under which the gap remains open, and hence AQO still succeeds. E.g., Reichardt [ 33 ] uses a perturbative argument based on the overlap between the unperturbed ground state and the spike to establish a spectral gap bound. Subsequent works [ 25 , 32 , 7 ] extended this analysis, some of them using approximation methods such as the spin-coherent path-integral instanton approach [ 32 ] and the discrete WKB method [ 25 ] . These analyses critically hinge on the fact that the unperturbed linear potential V(x)=|x| yields an exactly solvable Hamiltonian, with explicit expressions for the eigenvalues and eigenvectors, and indeed there seems to be no work considering more general convex potentials with a spike. 1 1 1 There are some exceptions in the continuous setting, see e.g. [ 28 ] and references therein. In this work, we go beyond linear potentials and consider a larger family of potentials, including but not limited to the broadly relevant family of convex symmetric potentials. While exact expressions for the corresponding ground states seem elusive, we establish strong structural properties based on “log-concavity” that give us a useful handle on them. As our main proof-of-concept, we extend the HWS analysis from linear to quadratic potentials (for which already we have no closed-form ground state), showing that the tunneling mechanism persists even in this more challenging setting. Quadratic potentials are the textbook workhorse for convex optimization, and we see our work as opening up the study of quantum tunneling in the more general setting of discrete convex optimization with AQO. 1.1 Main contributions In the following we summarize our contributions in more detail. (Ultra-)Log-concavity for a broad class of potentials. A discrete sequence \{p_{k}\}_{k\in[n]} is log-concave if for all k it satisfies p_{k}^{2}\geq p_{k+1}p_{k-1}. A distribution \{p_{k}\} is ultra-log-concave (of order n ) if the sequence \{p_{k}/\binom{n}{k}\}_{k\in[n]} is log-concave. As part of our first contribution, we introduce log-concavity as a critical tool for analyzing (discrete) AQO. In the continuous setting, log-concavity is well-known to be instrumental to proving spectral gap bounds, as is witnessed e.g. by all the recent works on log-concave sampling [ 10 ] . In the discrete setting however, log-concavity seems to have been less explored in this context. As an example, a key result by Brascamp and Lieb [ 9 ] in the continuous setting established that the ground state of a Schrödinger operator with convex potential is (ultra-)log-concave. Turning to the discrete setting, we were unable to find an analog of this key result. As our first main result, we establish discrete log-concavity of the ground state of a rather large family of Hamiltonians, including Schrödinger operators on the discrete line with single-well potential, and the AQO Hamiltonian ( Eq. 1 ) with symmetric potentials that are convex (and even certain multi-well potentials). We prove all of our results for 1-dimensional Hamiltonians of the form H=-A+V , where A is band-diagonal with A_{k,k-1}=A_{k-1,k}=a_{k} for log-concave \{a_{k}\} . This includes path Hamiltonians, but also AQO Hamiltonians (cf. Eq. 1 ) with a symmetric potential, for which there is a well-known symmetry reduction from the hypercube to the path. We establish a condition called “relative monotonicity” (RM) of the potential V with respect to the coefficients \{a_{k}\} that ensures log-concavity of the ground state. The RM-condition constrains ratios of consecutive values of the potential compared to the growth of a_{k+1}/a_{k} . Main Result 1 ( Theorem 2 and Theorem 3 ) . \bullet If a 1-dimensional Hamiltonian H=-A+V satisfies the RM-condition then its ground state is log-concave . \bullet If H is the symmetry-reduced AQO Hamiltonian with symmetric and convex V , then the ground-state is ultra-log-concave . The second bullet yields a discrete version of the continuous result by Brascamp and Lieb [ 9 ] . The first bullet allows us to go beyond convexity. E.g., if the a_{k} ’s are uniform (i.e., H is the