2026-06-23 · 9 min read · quantum algorithms

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

Tunneling is the supposed ace of adiabatic quantum optimization, but the evidence has lived in a single toy: the Hamming-weight-with-a-spike problem. A new paper by Braida, Bermot and Apers extends that analysis to a much wider family of potentials, anchored on a structural property the ground state turns out to share with convex cases.

Paper: arXiv:2606.23614

arXiv:2606.23614 takes a single observation — that the ground state of the Hamming-weight-with-a-spike Hamiltonian is log-concave — and asks how far that observation actually travels. Braida, Bermot & Apers turn it into a structural property of the ground state of a wide class of one-dimensional Schrödinger operators, and then use it to extend the perturbative tunneling analysis of the original HWS problem (Reichardt, ’04) to potentials that are not exactly solvable.

The upshot is a structural rather than a numerical claim: tunneling beats local search on a family of convex potentials with a single spike, not just on the linear spike toy. The analysis is discrete, one-dimensional, and clean — and it improves the spectral-gap bound of Jarret and Jordan (’14) along the way.

Why a single toy was the wrong unit

The HWS problem is the canonical “this is where AQO wins” example. The Hamiltonian is diagonal in the Hamming-weight basis with a linear ramp plus a single spike at a fixed Hamming weight, and the proof-of-concept story is that AQO crosses the spike faster than any local-search algorithm by tunneling through the Hamming barrier. Reichardt’s perturbative analysis pinned down the scaling.

But the result was load-bearing for a single potential shape. Every time someone wanted to extend it to a different convex-with-spike family, they had to redo the perturbative expansion from scratch. The new paper argues that log-concavity of the ground state is the right unit: it is the property that makes the perturbative expansion tractable, and it survives generalisation from linear ramps to arbitrary convex shapes (and beyond, to a meaningful family of non-convex shapes with local minima).

That is the move from one toy to a class of toys. Once the structural property is identified, the same machinery reaches further.

The structural property: log-concavity

For a discrete, one-dimensional Schrödinger operator on a finite or half-infinite chain, the ground state \(\psi_0\) is log-concave if

\psi_0(i)\,\psi_0(j) \;\geq\; \psi_0(k)^2, \qquad \forall\, i \leq k \leq j.

This is the discrete analogue of \(\psi'' \leq 0\) for a continuous ground state. The continuous analogue is a 1976 Brascamp–Lieb result that proves log-concavity of the ground state for convex potentials. Braida, Bermot & Apers produce a discrete version of that argument and show it covers the convex case plus a meaningful class of potentials with local minima.

Once the ground state is log-concave, the rest of the paper’s two contributions fall out:

Spectral-gap lower bounds. Log-concavity gives a tighter control on the ground-state mass distribution. The new bounds strictly improve over the Jarret–Jordan (’14) convex-potential result.
Perturbative HWS analysis. Reichardt’s expansion transfers to any potential in the log-concave-ground-state family. The concrete instantiation in the paper takes a quadratic potential (which is no longer exactly solvable) and shows the same AQO speedup.

From Hamming-weight-with-a-spike to convex-with-a-spike

The headline new example is the quadratic variant of HWS. The original analysis assumed a linear potential so that the off-spike part of the Hamiltonian was exactly solvable (free-fermion-like). The quadratic variant breaks that solvability, which is exactly the case where the old perturbative toolbox does not work out of the box.

H(s) \;=\; \underbrace{\bigl(1 - s\bigr)\,\Delta_{\text{quad}}\,\sum_{i} i^2\,|i\rangle\!\langle i|}_{\text{quadratic ramp}} \;+\; \underbrace{s\,\gamma\,|k^\star\rangle\!\langle k^\star|}_{\text{spike}}, \qquad s \in [0,1].

The ground state is log-concave by the new theorem. The perturbative expansion goes through and gives an AQO runtime that scales polynomially in the inverse spike height, beating local search by a factor polynomial in the system size. The same scaling Reichardt obtained for the linear case.

The unit of analysis shifts from the toy to the property. Asking “does AQO beat local search on HWS?” was the right question once. The right question now is “for which ground-state-shape properties does AQO beat local search, and what does that buy us in practice?”

What log-concavity actually buys

Log-concavity is not just a label. It is the property that turns a perturbative expansion of the ground-state mass around the spike into a controlled error term. Intuitively: if the ground state is log-concave, then the probability mass around the spike is well-approximated by a one-mode coherent excitation, and the second-order corrections are bounded by the curvature of the log-concave envelope.

Concretely, that means:

The AQO speedup transfers to any potential whose ground state stays log-concave through the adiabatic sweep.
The spectral-gap bound improves because log-concavity rules out the ground-state mass concentrating in two disjoint lumps (which would be the failure mode for the Jarret–Jordan bound).
The class of eligible potentials is larger than convex — it includes some local-minimum potentials, which means the result is not a flat re-derivation of the Brascamp–Lieb continuous result.

The cost is that the structural property is non-trivial to check for a given potential. Log-concavity is not a closed-form condition; you prove it by a careful Schur-test or comparison argument, and the bookkeeping for non-convex potentials is delicate.

Why a structural paper is a useful algorithmic result: Once the structural property is named, every future AQO analysis on a new potential starts with “is the ground state log-concave?” That question takes a fraction of the time of a full perturbative analysis, and a negative answer tells you immediately that the HWS-style speedup is not going to transfer. The structural move converts an open-ended problem into a checkable one.

What I'd keep in mind

Three things to carry forward from this paper:

Log-concavity is the unit. When you see a “AQO beats local search on X” claim, ask whether X has a log-concave ground state through the sweep. That is the testable structural property the new paper puts on the table.
The spectral-gap improvement is strict. For convex potentials, the new bound dominates Jarret–Jordan (’14). Anywhere that bound was the bottleneck for a downstream runtime argument, the new paper buys you an improvement.
The HWS program has a wider scope. Quadratic ramps are the immediate win, but the proof goes through for the entire log-concave-ground-state family. If you have a candidate AQO advantage problem on a non-linear potential, this paper is the place to start.

What I would not over-claim: AQO is now a general-purpose optimizer. The result is structural — it tells you when the HWS-style argument transfers — not universal. Convex-with-a-spike is a class, not all of optimization.

Takeaway

Braida, Bermot and Apers do not propose a new algorithm. They identify the structural property that makes the canonical AQO-tunneling argument work, prove it holds for a wider family than was previously known, and use it to extend Reichardt’s perturbative analysis past the exactly-solvable linear case. The improvement over Jarret–Jordan is the clean numerical headline; the structural move is the durable contribution.

That is the version of an AQO result that ages well: not a single-instance speedup, but a property-named generalisation that lets every future potential be classified by a checkable condition. Once the property is in the literature, the question stops being “does AQO win on my problem?” and becomes “is the ground state of my problem log-concave through the sweep?” — and the latter is a question a paper can answer.

Reference: arXiv:2606.23614 · Braida, Bermot & Apers · Log-concavity and tunneling: adiabatic quantum optimization for convex functions (with a spike)