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

Bounds on adiabatic path geometry from the width class of the gap profile

Mancheon Han, Sangkook Choi

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 1, 2026 (v2)
v1 · Sep 30, 2026v2 · Oct 1, 2026
arXivHTMLPDF

Abstract

In an adiabatic evolution, the wave function follows the path of ground states $|Φ_0(s)\rangle$ of a Hamiltonian $H(s)$ as $s$ is tuned from $0$ to $1$. The geometry of this adiabatic path is described by quantities such as its length $L=\int_0^1 \|\partial_s |Φ_0(s)\rangle\|\,ds$ and its total curvature $K$. This geometry affects the evolution time $T$. For instance, $T$ is at least of order $L/Δ_*$, where $Δ_*$ is the minimum energy gap over $s\in[0,1]$. The traditional approach gives $L=O(Δ_*^{-1/2})$ and $K=O(Δ_*^{-1})$, which are loose in many cases. We improve these bounds by using $μ_<(γ)$, the width of the region in $s$ on which the gap is below $γ$. The gap profile is in width class $p$ when $μ_<(γ)$ falls at least as fast as $γ^{1/p}$. A typical avoided crossing is in width class $p=1$, which gives $L=O(\sqrt{\log Δ_*^{-1}})$ and $K=O(\log Δ_*^{-1})$. A profile in width class $p>1$ gives power laws with exponents $(p-1)/(2p)$ for $L$ and $(p-1)/p$ for $K$. The width class also bounds the evolution time. At $p=1$ we have $T=O(Δ_*^{-2})$ with a schedule that advances $s$ at a constant rate, and $T=O(Δ_*^{-1})$ up to a polylogarithmic correction with a schedule that traverses the path at a constant geometric speed. The bounds on $L$ hold for any twice continuously differentiable $H(s)$, and the bounds on $K$ for affine $H(s)$. We also prove the tightness of scaling of $L$ in $Δ_*$ for every integer $p\ge1$, and the scaling of $K$ at $p=1$. We demonstrate the bounds on the adiabatic Grover search, the XXZ spin chain, and molecular electronic Hamiltonians.

AI Summary

The paper asks how the width of a small-gap region constrains adiabatic ground-state path geometry, beyond bounds using only the minimum gap $\Delta_*$. It defines width class $p\ge1$ through $\mu_<(\gamma)\le C_W(\gamma/\Gamma)^{1/p}$, where $\mu_<$ measures the parameter interval with gap below $\gamma$. Scaling statements require uniform width and Hamiltonian-derivative bounds across a family. For the spectral subspace of the lowest $g$ levels, allowing internal crossings, it bounds path length by $L_P\le[C_L\int_0^1ds/\Delta(s)]^{1/2}$ and, for affine Hamiltonians, total curvature by $K_P\le2\Omega\int_0^1ds/\Delta(s)$, where $\Omega$ is the spectral width of $H'$. A layer-cake identity converts width information into $L_P=O(\sqrt{\log\Delta_*^{-1}})$ and $K_P=O(\log\Delta_*^{-1})$ at $p=1$, which includes linearly opening avoided crossings. For $p>1$, the respective exponents of $\Delta_*^{-1}$ are $(p-1)/(2p)$ and $(p-1)/p$. Explicit affine constructions establish tightness for length at every integer $p\ge1$ and curvature at $p=1$. At fixed target error, runtime guarantees are $T=O(\Delta_*^{-(3-1/p)})$ for a linear schedule and, for affine nondegenerate ground states at constant geometric speed, $T=O(\Delta_*^{-1}\sqrt{\log\Delta_*^{-1}})$ at $p=1$. Examples cover Grover search, a ten-spin XXZ chain, and molecular Hamiltonians. Length bounds extend to twice-differentiable non-affine paths with bounded derivative budgets; a counterexample excludes an analogous curvature extension. Curvature tightness for $p>1$ and broader conditions ensuring gap-independent bounded geometry remain open.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
19 pages, 3 figures

Related papers

Constant geometric speed schedule for adiabatic state preparation

Miao Han, Hyowon Park, Sangkook Choi

The efficiency of adiabatic quantum evolution is governed by the evolution time T , which typically scales as O ( Δ − 2 ) with the minimum energy gap Δ . However, the rigorous lower bound is O ( L Δ − 1 ) , where L is the adiabatic path length. Although L is formally upper bounded by O ( Δ − 1 ) , such a bound is often too loose in practice, and L can be bounded independently of Δ . This indicates the potential for a quadratic speedup through adiabatic schedule construction. Here, we introduce the constant geometric speed (CGS) schedule, which traverses the adiabatic path at a uniform rate. We show that this approach reduces the scaling of the evolution time by a factor of Δ − 1 , provided L remains bounded independently of Δ . We propose a segmented CGS protocol where path segment lengths are computed from eigenstate overlaps on the fly, reducing the prior spectral-knowledge requirement from the full gap function Δ ( s ) to just a global lower bound on the energy gap. Numerical tests on adiabatic unstructured search, N 2 , and a [2Fe-2S] cluster demonstrate the optimal Δ − 1 scaling, confirming a quadratic speedup over the standard linear schedule.

arXiv:2510.01923•Physical Review Research•May 9, 2026•1 citation

On the General Class of Models of Adiabatic Evolution

Jie Sun, Songfeng Lu, Fang Liu

The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.

Open Systems & Information Dynamics•Sep 1, 2016•3 citations

Quantum adiabatic optimization without heuristics

Michael Jarret, Brad Lackey, Aike Liu +1 more

Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian $H(s)$ with spectral gap $γ(s)$. Assuming the existence of an oracle $Γ$ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that $\|dH/ds\| \approx γ(s)$ and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle $Γ$ for the problem of finding the minimum point $m = \mathrm{argmin}_u W(u)$ of the cost function $W:\mathcal{V}\longrightarrow [0,1]$, restricting ourselves to computational basis measurements and driving Hamiltonian $H(0)=I - |\mathcal{V}|^{-1}\sum_{u,v \in \mathcal{V}}\vert{u}\rangle\langle{v}\vert$. Requiring only that $W$ have a constant lower bound on its spectral gap and upper bound $κ$ on its spectral ratio, our QAO algorithm returns $m$ with probability $(1-ε)(1-e^{-1/ε})$ in time $\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])$. This achieves a quantum advantage for all $κ$, and recovers Grover scaling up to logarithmic factors when $κ\approx 1$. We implement the algorithm as a subroutine in an optimization procedure that produces $m$ with exponentially small failure probability and expected runtime $\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])$ even when $κ$ is not known beforehand.

arXiv:1810.04686•Oct 10, 2018•15 citations

Numerical study of computational cost of maintaining adiabaticity for long paths

Thomas D. Cohen, Hyunwoo Oh, Veronica Wang

Abstract Recent work [1] argued that the scaling of a dimensionless quantity $$Q_D$$ Q D with path length is a better proxy for quantifying the scaling of the computational cost of maintaining adiabaticity than the timescale. It also conjectured that generically the scaling will be superlinear (although special cases exist in which it is linear). The quantity $$Q_D$$ Q D depends only on the properties of ground states along the Hamiltonian path and the rate at which the path is followed. In this paper, we demonstrate that this conjecture holds for simple Hamiltonian systems that can be studied numerically. In particular, the systems studied exhibit the behavior that $$Q_D$$ Q D grows approximately as $$L \log L$$ L log L where L is the path length when the threshold error is fixed.

arXiv:2412.08626•The European Physical Journal A•Jun 23, 2026•2 citations

Bounds for the adiabatic approximation with applications to quantum computation

Sabine Jansen, Mary Beth Ruskai, Ruedi Seiler

We present straightforward proofs of estimates used in the adiabatic approximation. The gap dependence is analyzed explicitly. We apply the result to interpolating Hamiltonians of interest in quantum computing.

•Mar 20, 2006•228 citations

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri +4 more

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

arXiv:2411.05736•Quantum•Jul 11, 2025•10 citations
In an adiabatic evolution, the wave function follows the path of ground states ∣Φ0(s)⟩|Φ_0(s)\rangle∣Φ0​(s)⟩ of a Hamiltonian H(s)H(s)H(s) as sss is tuned from 000 to 111. The geometry of this adiabatic path is described by quantities such as its length L=∫01∥∂s∣Φ0(s)⟩∥ dsL=\int_0^1 \|\partial_s |Φ_0(s)\rangle\|\,dsL=∫01​∥∂s​∣Φ0​(s)⟩∥ds and its total curvature KKK. This geometry affects the evolution time TTT. For instance, TTT is at least of order L/Δ∗L/Δ_*L/Δ∗​, where Δ∗Δ_*Δ∗​ is the minimum energy gap over s∈[0,1]s\in[0,1]s∈[0,1]. The traditional approach gives L=O(Δ∗−1/2)L=O(Δ_*^{-1/2})L=O(Δ∗−1/2​) and K=O(Δ∗−1)K=O(Δ_*^{-1})K=O(Δ∗−1​), which are loose in many cases. We improve these bounds by using μ<(γ)μ_<(γ)μ<​(γ), the width of the region in sss on which the gap is below γγγ. The gap profile is in width class ppp when μ<(γ)μ_<(γ)μ<​(γ) falls at least as fast as γ1/pγ^{1/p}γ1/p. A typical avoided crossing is in width class p=1p=1p=1, which gives L=O(log⁡Δ∗−1)L=O(\sqrt{\log Δ_*^{-1}})L=O(logΔ∗−1​​) and K=O(log⁡Δ∗−1)K=O(\log Δ_*^{-1})K=O(logΔ∗−1​). A profile in width class p>1p>1p>1 gives power laws with exponents (p−1)/(2p)(p-1)/(2p)(p−1)/(2p) for LLL and (p−1)/p(p-1)/p(p−1)/p for KKK. The width class also bounds the evolution time. At p=1p=1p=1 we have T=O(Δ∗−2)T=O(Δ_*^{-2})T=O(Δ∗−2​) with a schedule that advances sss at a constant rate, and T=O(Δ∗−1)T=O(Δ_*^{-1})T=O(Δ∗−1​) up to a polylogarithmic correction with a schedule that traverses the path at a constant geometric speed. The bounds on LLL hold for any twice continuously differentiable H(s)H(s)H(s), and the bounds on KKK for affine H(s)H(s)H(s). We also prove the tightness of scaling of LLL in Δ∗Δ_*Δ∗​ for every integer p≥1p\ge1p≥1, and the scaling of KKK at p=1p=1p=1. We demonstrate the bounds on the adiabatic Grover search, the XXZ spin chain, and molecular electronic Hamiltonians.
The paper asks how the width of a small-gap region constrains adiabatic ground-state path geometry, beyond bounds using only the minimum gap Δ∗\Delta_*Δ∗​. It defines width class p≥1p\ge1p≥1 through μ<(γ)≤CW(γ/Γ)1/p\mu_<(\gamma)\le C_W(\gamma/\Gamma)^{1/p}μ<​(γ)≤CW​(γ/Γ)1/p, where μ<\mu_<μ<​ measures the parameter interval with gap below γ\gammaγ. Scaling statements require uniform width and Hamiltonian-derivative bounds across a family.
For the spectral subspace of the lowest ggg levels, allowing internal crossings, it bounds path length by LP≤[CL∫01ds/Δ(s)]1/2L_P\le[C_L\int_0^1ds/\Delta(s)]^{1/2}LP​≤[CL​∫01​ds/Δ(s)]1/2 and, for affine Hamiltonians, total curvature by KP≤2Ω∫01ds/Δ(s)K_P\le2\Omega\int_0^1ds/\Delta(s)KP​≤2Ω∫01​ds/Δ(s), where Ω\OmegaΩ is the spectral width of H′H'H′. A layer-cake identity converts width information into LP=O(log⁡Δ∗−1)L_P=O(\sqrt{\log\Delta_*^{-1}})LP​=O(logΔ∗−1​​) and KP=O(log⁡Δ∗−1)K_P=O(\log\Delta_*^{-1})KP​=O(logΔ∗−1​) at p=1p=1p=1, which includes linearly opening avoided crossings. For p>1p>1p>1, the respective exponents of Δ∗−1\Delta_*^{-1}Δ∗−1​ are (p−1)/(2p)(p-1)/(2p)(p−1)/(2p) and (p−1)/p(p-1)/p(p−1)/p. Explicit affine constructions establish tightness for length at every integer p≥1p\ge1p≥1 and curvature at p=1p=1p=1.
At fixed target error, runtime guarantees are T=O(Δ∗−(3−1/p))T=O(\Delta_*^{-(3-1/p)})T=O(Δ∗−(3−1/p)​) for a linear schedule and, for affine nondegenerate ground states at constant geometric speed, T=O(Δ∗−1log⁡Δ∗−1)T=O(\Delta_*^{-1}\sqrt{\log\Delta_*^{-1}})T=O(Δ∗−1​logΔ∗−1​​) at p=1p=1p=1. Examples cover Grover search, a ten-spin XXZ chain, and molecular Hamiltonians. Length bounds extend to twice-differentiable non-affine paths with bounded derivative budgets; a counterexample excludes an analogous curvature extension. Curvature tightness for p>1p>1p>1 and broader conditions ensuring gap-independent bounded geometry remain open.
The efficiency of adiabatic quantum evolution is governed by the evolution time T , which typically scales as O ( Δ − 2 ) with the minimum energy gap Δ . However, the rigorous lower bound is O ( L Δ − 1 ) , where L is the adiabatic path length. Although L is formally upper bounded by O ( Δ − 1 ) , such a bound is often too loose in practice, and L can be bounded independently of Δ . This indicates the potential for a quadratic speedup through adiabatic schedule construction. Here, we introduce the constant geometric speed (CGS) schedule, which traverses the adiabatic path at a uniform rate. We show that this approach reduces the scaling of the evolution time by a factor of Δ − 1 , provided L remains bounded independently of Δ . We propose a segmented CGS protocol where path segment lengths are computed from eigenstate overlaps on the fly, reducing the prior spectral-knowledge requirement from the full gap function Δ ( s ) to just a global lower bound on the energy gap. Numerical tests on adiabatic unstructured search, N 2 , and a [2Fe-2S] cluster demonstrate the optimal Δ − 1 scaling, confirming a quadratic speedup over the standard linear schedule.
The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s)H(s)H(s) with spectral gap γ(s)γ(s)γ(s). Assuming the existence of an oracle ΓΓΓ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that ∥dH/ds∥≈γ(s)\|dH/ds\| \approx γ(s)∥dH/ds∥≈γ(s) and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle ΓΓΓ for the problem of finding the minimum point m=argminuW(u)m = \mathrm{argmin}_u W(u)m=argminu​W(u) of the cost function W:V⟶[0,1]W:\mathcal{V}\longrightarrow [0,1]W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I−∣V∣−1∑u,v∈V∣u⟩⟨v∣H(0)=I - |\mathcal{V}|^{-1}\sum_{u,v \in \mathcal{V}}\vert{u}\rangle\langle{v}\vertH(0)=I−∣V∣−1∑u,v∈V​∣u⟩⟨v∣. Requiring only that WWW have a constant lower bound on its spectral gap and upper bound κκκ on its spectral ratio, our QAO algorithm returns mmm with probability (1−ε)(1−e−1/ε)(1-ε)(1-e^{-1/ε})(1−ε)(1−e−1/ε) in time O~(ε−1[∣V∣+(κ−1)2/3∣V∣2/3])\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])O(ε−1[∣V∣​+(κ−1)2/3∣V∣2/3]). This achieves a quantum advantage for all κκκ, and recovers Grover scaling up to logarithmic factors when κ≈1κ\approx 1κ≈1. We implement the algorithm as a subroutine in an optimization procedure that produces mmm with exponentially small failure probability and expected runtime O~(ε−1[∣V∣+(κ−1)2/3∣V∣2/3])\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])O(ε−1[∣V∣​+(κ−1)2/3∣V∣2/3]) even when κκκ is not known beforehand.
Abstract Recent work [1] argued that the scaling of a dimensionless quantity QDQ_DQD​ Q D with path length is a better proxy for quantifying the scaling of the computational cost of maintaining adiabaticity than the timescale. It also conjectured that generically the scaling will be superlinear (although special cases exist in which it is linear). The quantity QDQ_DQD​ Q D depends only on the properties of ground states along the Hamiltonian path and the rate at which the path is followed. In this paper, we demonstrate that this conjecture holds for simple Hamiltonian systems that can be studied numerically. In particular, the systems studied exhibit the behavior that QDQ_DQD​ Q D grows approximately as Llog⁡LL \log LLlogL L log L where L is the path length when the threshold error is fixed.
In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.