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
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=\mathcal{O}(Δ_*^{-1/2})$ and $K=\mathcal{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=\mathcal{O}(\sqrt{\log Δ_*^{-1}})$ and $K=\mathcal{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=\mathcal{O}(Δ_*^{-2})$ with a schedule that advances $s$ at a constant rate, and $T=\mathcal{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.

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

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•8 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•0 citations

On Models of Nonlinear Evolution Paths in Adiabatic Quantum Algorithms

Jie Sun, Songfeng Lu, Samuel L. Braunstein

In this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.

arXiv:1301.1115•Communications in Theoretical Physics•Jan 1, 2013•8 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.

•Jan 1, 2006•215 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=\mathcal{O}(Δ_*^{-1/2})L=O(Δ∗−1/2​) and K=O(Δ∗−1)K=\mathcal{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=\mathcal{O}(\sqrt{\log Δ_*^{-1}})L=O(logΔ∗−1​​) and K=O(log⁡Δ∗−1)K=\mathcal{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=\mathcal{O}(Δ_*^{-2})T=O(Δ∗−2​) with a schedule that advances sss at a constant rate, and T=O(Δ∗−1)T=\mathcal{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 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 this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.