Quantum computing · Theory (AI-assisted)
Vanilla Adiabatic Quantum Optimization Can Have Subexponential Advantage
arXiv:2611.24035v1 ↗PDF ↗Submitted 18 November 2026
- Question
- Adiabatic quantum optimisation in its original form interpolates linearly from a transverse field to a diagonal objective, \(H(s)=-(1-s)\sum_iX_i+s\sum_xf(x)\ket x\bra x\). It gives a quadratic speedup for unstructured search, and whether it can ever do better was open for two decades, even with black-box access to \(f\). Leng et al. (arXiv:2504.14841) recently found an objective with a subexponential speedup, but only by replacing the transverse field with a transverse-field Ising mixer. Does the textbook path, with the plain transverse field used in Farhi et al.'s proposal and most experiments, admit a superquadratic speedup?
- Result
- Yes. There is a family of objectives on \(N\) qubits, given as a black box with values bounded by \(\mathrm{poly}(N)\), for which the textbook path with a linear schedule has spectral gap at least \(1/\mathrm{poly}(N)\) and ends in the unique minimiser. Adiabatic evolution therefore finds it in polynomial time. Any classical algorithm needs \(\exp(N^{\Omega(1)})\) queries to find it, or even a value within \(1/\mathrm{poly}(N)\) of the minimum. The construction adds a clock register of \(k=\mathrm{poly}(n)\) qubits to the hard instance of Leng et al. The same mixer drives the clock through the product ground state \(\ket{\psi(s)}^{\otimes k}\), whose magnetisation per qubit is \(m(s)=s/\sqrt{s^2+4(1-s)^2}\). The objective couples the problem register to that magnetisation so that the problem register effectively follows \((1-s)\) times Leng et al.'s hard path.
The paper in detail
Adiabatic optimisation prepares the ground state of a transverse field, the uniform superposition, and slowly turns the field off while turning on a diagonal Hamiltonian that encodes the objective. If the gap above the ground state stays at least inverse-polynomial, a polynomial run time suffices and the final measurement returns the minimiser. The starting point is a hard path of Leng et al., \(K(t)=-\sum_iX_i+D(t)\) with diagonal \(D(t)\), an inverse-polynomial gap and a final term \(-3n\ket u\bra u\). Measuring its final ground state reveals \(u\), which is exponentially hard to find classically from queries to \(D\). The path has two defects for the textbook form: its mixer is never switched off, and \(D(t)\) depends on time non-linearly, while the textbook path must be linear in \(s\) and end with a purely diagonal Hamiltonian.
The fix makes time an observable. A register of \(k\) clock qubits with diagonal term \(W\), the number of ones, evolves under \(-(1-s)\sum X+sW\), a sum of independent single-qubit Hamiltonians. Its ground state is a product of identical qubit states turning from \(\ket+\) to \(\ket0\), and its gap never drops below \(2/\sqrt5\). Measuring the clock gives a string whose magnetisation \(t(c)=1-2|c|/k\) has mean \(m(s)\) and variance at most \(1/k\), so a large clock reads the time accurately. The objective is \(F(c,x)=|c|+G(t(c))(x)\), with problem term \(G(t)=\lambda(t)D(t)\) and \(\lambda(t)=\sqrt{1-t^2}/(2t)\). Because \(s\lambda(m(s))=1-s\), the problem register sees \(-(1-s)\sum X+(1-s)D(m(s))=(1-s)K(m(s))\): the hard path, scaled and reparametrised.
Three problems remain: \(\lambda\) diverges at \(t=0\), it vanishes at \(t=1\) and would close the gap at the end, and a large problem term would disturb the clock. All three are solved by running the whole hard path inside a narrow window \([t_0,t_1]=[1-\epsilon,1-\epsilon/2]\) of clock readings near 1. Below the window the problem term is zero, inside it \(D\) is traversed at speed \(2/\epsilon\), and above it the final term \(\lambda(t_1)D(1)\) is frozen. Since \(\lambda\le\sqrt{2\epsilon}\) there, the problem term has norm at most \(1/10\), small against the clock gap. The proof then bounds the gap through two idealisations: pinning the clock to its ground state, and replacing the fluctuating reading by its mean.
The minimiser is \((0^k,u)\): a clock string with any ones costs at least \(1-1/10\), while the all-zero clock string reads \(t=1\) and rewards \(x=u\). A classical algorithm that finds the minimiser of \(F\) therefore finds \(u\), and each query to \(F\) costs one query to \(D\), so the classical lower bound carries over. The result is a statement about the textbook path, not about natural problems. Whether a similar separation exists for objectives without oracle structure, or with polynomials small enough to matter, is left open.
Transferable methods
A product-state clock driven by the mixer itself
A linear interpolation offers no way to make a diagonal term change non-linearly in time, unless something inside the system keeps time. Non-interacting qubits under the same field-to-diagonal interpolation have an exactly solvable, gapped, product ground state whose magnetisation is a known increasing function of \(s\). Letting the objective depend on the clock's magnetisation turns the fixed diagonal term into an effective time-dependent one.
Each clock qubit has \(A(s)=-(1-s)X+s\ket1\bra1\), with eigenvalues \(\tfrac12\bigl(s\pm\Delta(s)\bigr)\) and \[\Delta(s)=\sqrt{s^2+4(1-s)^2}=\sqrt{5\bigl(s-\tfrac45\bigr)^2+\tfrac45}\ge\frac2{\sqrt5}.\] The ground state has \(\langle Z\rangle=m(s)=s/\Delta(s)\), rising from 0 to 1. The \(k\)-qubit clock is a Kronecker sum, so its spectrum is a Minkowski sum: the ground state is \(\ket{\psi(s)}^{\otimes k}\) and the gap is \(\Delta(s)\), independent of \(k\). Measured bits are independent, so \(t(c)\) has mean \(m(s)\) and variance \((1-m^2)/k\le1/k\).
Editorial step: from \(m=s/\Delta\) one gets \(1-m^2=4(1-s)^2/\Delta^2\), hence \[\lambda(m(s))=\frac{\sqrt{1-m^2}}{2m}=\frac{2(1-s)/\Delta}{2s/\Delta}=\frac{1-s}{s}.\] So \(sG(m(s))=(1-s)D(m(s))\), and the problem register's effective Hamiltonian is \(-(1-s)\sum X+(1-s)D=(1-s)K\). Its gap is \((1-s)\) times the gap of \(K\), which is why the window must stay away from \(s=1\). With \(t_1=1-\epsilon/2\), one has \(1-s\ge\sqrt{\epsilon}/5\) throughout the window, giving the effective gap \(\delta^\star=\sqrt\epsilon/(5\kappa)\).
Editorial check: \(\lambda(m(s))\) and \((1-s)/s\) agree to \(10^{-13}\) on 2,001 points, and the minimum of \(\Delta\) is \(0.894427=2/\sqrt5\) at \(s=0.800\). Above the window the effective Hamiltonian is \(-(1-s)\sum X-3ns\lambda(t_1)\ket u\bra u\). Its gap is at least \(3n(1-s_1)-2n(1-s_1)=n(1-s_1)\), using \(s\lambda(t_1)\ge s_1\lambda(t_1)=1-s_1\), so the frozen final term keeps the gap open to the end.
How to reuse it
Any device that needs a non-linear schedule but can only apply a linear interpolation, such as analogue annealers with fixed annealing functions, can embed a clock of non-interacting qubits whose magnetisation reparametrises time. The same trick turns a Lipschitz path with a transverse-field mixer into a linear one, so other adiabatic separations stated for curved paths can be transferred to the textbook form.
Transferring the gap through a block decomposition
The idealised picture, a clock frozen in its ground state with a sharp reading, must be shown to hold for the real Hamiltonian, whose clock is entangled with the problem register and whose reading fluctuates. Splitting the Hilbert space into the clock ground state and its complement isolates the only term that couples the two, and that term is small because the clock reading concentrates.
Let \(P=\ket{\psi_C(s)}\bra{\psi_C(s)}\otimes I\) and \(Q=I-P\). The clock Hamiltonian and the problem register's field are block diagonal, so the only off-diagonal block is \(R=sQ\bigl(\widehat G-I\otimes G(m(s))\bigr)P\), where \(\widehat G=\sum_c\ket c\bra c\otimes G(t(c))\) is the full diagonal coupling. Since \(\widehat G\) is block diagonal in clock strings, \[\bigl\|(\widehat G-I\otimes G(m))(\ket{\psi_C}\otimes\ket v)\bigr\|^2=\mathbb E_c\bigl\|(G(t(c))-G(m))\ket v\bigr\|^2\le\frac{L_G^2}{k}\|v\|^2,\] so \(\|R\|\le L_G/\sqrt k\). The \(P\)-block is the effective Hamiltonian, and the \(Q\)-block lies at least \(2/\sqrt5-2M_G\ge\tfrac23\) higher.
A Weyl-inequality lemma then gives \(\delta_H\ge\min\{\delta_A,\gamma\}-2\|R\|\), where \(\delta_A\) is the gap of the \(P\)-block and \(\gamma\) the separation of the two blocks. Replacing the averaged term \(\mathbb E_cG(t(c))\) by \(G(m(s))\) costs at most \(L_G/\sqrt k\) (Cauchy–Schwarz). With \(L_G\le4(L_D+M_D)/\sqrt\epsilon\) and \(k\) chosen so that \(2L_G/\sqrt k\le\delta^\star/4\), the full gap is at least \(\delta^\star/2=\sqrt\epsilon/(10\kappa)\). Editorial arithmetic: with \(\epsilon=1/(200\kappa^2)\) the paper's choice \(k=\lceil(64\kappa/(\sqrt\epsilon\delta^\star))^2\rceil\) equals \((64{,}000\,\kappa^4)^2\approx4.1\times10^9\kappa^8\), polynomial but large.
Editorial check: a toy with two problem qubits, \(D(t)=-6t\ket{11}\bra{11}\) and window \([0.9,0.95]\) was diagonalised in the clock's permutation-symmetric sector, where the clock's ground state lies. The full Hamiltonian's minimum gap over \(s\) is 0.355 for \(k=400\) and 0.353 for \(k=4000\), against 0.358 for the idealised effective Hamiltonian, and the diagonal minimum is at clock string \(0^k\) with \(x=11\). The toy's coupling norm (1.45) violates the proof's assumption \(M_G\le1/10\), so the clock picture seems robust beyond the proven regime; the toy has no hardness and checks only the mechanism.
How to reuse it
Splitting into a fast, gapped subsystem's ground space and its complement, and bounding the single off-diagonal block by a concentration estimate, is a clean alternative to perturbation theory for gadgets, clock constructions and Born–Oppenheimer-type reductions. It gives explicit gap bounds without expansion to second order.
Context & limitations
Why it matters. This settles, in the black-box model, whether the simplest form of adiabatic optimisation can beat classical algorithms by more than a square root: it can, subexponentially. Earlier subexponential speedups needed diabatic transitions, detours through intermediate Hamiltonians or a non-standard mixer. The clock idea is reusable: a non-interacting register driven by the same transverse field acts as a smooth, gapped timer, which lets any Lipschitz path with a transverse-field mixer be compiled into the linear textbook form.
Limitations. The separation is an oracle result for a highly artificial objective that inherits the welded-tree style hardness of Gilyén–Hastings–Vazirani through Leng et al.; it says nothing about natural optimisation problems such as MaxCut or spin glasses. The speedup is subexponential, not exponential, and the polynomials are very large: with \(\kappa=\mathrm{poly}(n)\) bounding the hard path, the clock needs about \(4\times10^9\,\kappa^8\) qubits and the gap is only \(\sqrt\epsilon/(10\kappa)\) with \(\epsilon=1/(200\kappa^2)\). Finite-precision encoding of the real-valued objective is omitted. The paper's AI table says that AI was used to devise the approach, develop the proof, check for bugs and copy-edit, but not to pose the question or write the exposition. GPT-6 Luna suggested the main strategy, and GPT-6 Astra, GPT-6.1 Sol and Claude Opus 5.5 were also used; the author reports checking the AI-assisted arguments.