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:1906.05233 · Physical Review A

Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds

Shane Dooley, Graham Kells, Hosho Katsura, T. C. Dorlas

Published Apr 1, 2020• 5 citations
arXivHTMLPDF

Abstract

Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps $L$. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for $L\ensuremath{\gg}1$ is ${min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]$, an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.

DOI
10.1103/physreva.101.042302

Related papers

ON THE GAP OF HAMILTONIANS FOR THE ADIABATIC SIMULATION OF QUANTUM CIRCUITS

Anand Ganti, Rolando D. Somma

The time or cost of simulating a quantum circuit by adiabatic evolution is determined by the spectral gap of the Hamiltonians involved in the simulation. In "standard" constructions based on Feynman's Hamiltonian, such a gap decreases polynomially with the number of gates in the circuit, L. Because a larger gap implies a smaller cost, we study the limits of spectral gap amplification in this context. We show that, under some assumptions on the ground states and the cost of evolving with the Hamiltonians (which apply to the standard constructions), an upper bound on the gap of the order 1/L follows. In addition, if the Hamiltonians satisfy a frustration-free property, the upper bound is of the order 1/L2. Our proofs use recent results on adiabatic state transformations, spectral gap amplification, and the simulation of continuous-time quantum query algorithms. They also consider a reduction from the unstructured search problem, whose lower bound in the oracle cost translates into the upper bounds in the gaps. The impact of our results is that improving the gap beyond that of standard constructions (i.e. 1/L2), if possible, is challenging.

arXiv:1307.4993•International Journal of Quantum Information•Oct 1, 2013•5 citations

Adiabatic Quantum Computation

Friederike Anna Dziemba

The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the $L$ computation steps and influencing the scaling of the necessary evolution time by its spectral gap of $\mathcal{O}\left(\frac{1}{L^2}\right)$. Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap $\mathcal{O}\left(\frac{1}{L^k}\right)$, $k<2$, turn out to contradict very likely, graphs with $k<1$ even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.

arXiv:1610.04708•Oct 15, 2016•1 citation

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.

SIAM Review•Jan 1, 2008•395 citations

Spectral Gap Amplification

R. D. Somma, S. Boixo

Many problems can be solved by preparing a specific eigenstate of some Hamiltonian $H$. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of $H$ for that eigenstate and the cost of evolving with $H$ for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian $H'$ with the same eigenstate as $H$ but a bigger spectral gap, requiring that constant-time evolutions with $H'$ and $H$ are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when $H$ satisfies a frustration-free property and give $H'$ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.

arXiv:1110.2494•SIAM Journal on Computing•Jan 1, 2013•50 citations

Spectral-gap analysis for efficient tunneling in quantum adiabatic optimization

Lucas T. Brady, Wim van Dam

We investigate the efficiency of quantum adiabatic optimization when overcoming potential barriers to get from a local to a global minimum. Specifically we look at $n$ qubit systems with symmetric cost functions $f:{{0,1}}^{n}\ensuremath{\rightarrow}\mathbb{R}$, where the ground state must tunnel through a potential barrier of width ${n}^{\ensuremath{\alpha}}$ and height ${n}^{\ensuremath{\beta}}$. By the quantum adiabatic theorem the time delay sufficient to ensure tunneling grows quadratically with the inverse spectral gap during this tunneling process. We analyze barrier sizes with $1/2\ensuremath{\le}\ensuremath{\alpha}+\ensuremath{\beta}$ and $\ensuremath{\alpha}<1/2$ and show that the minimum gap scales polynomially as ${n}^{1/2\ensuremath{-}\ensuremath{\alpha}\ensuremath{-}\ensuremath{\beta}}$ when $2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{\le}1$ and exponentially as ${n}^{\ensuremath{-}\ensuremath{\beta}/2}exp(\ensuremath{-}C{n}^{(2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{-}1)/2})$ when $1<2\ensuremath{\alpha}+\ensuremath{\beta}$. Our proof uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone from 2002, which used large spin and instanton methods. Parts of our result also refine recent results by Kong and Crosson [arXiv:1511.06991] and Jiang et al. [arXiv:1603.01293] about the exponential gap scaling.

arXiv:1601.01720•Physical Review A•Sep 9, 2016•17 citations

Bounding first-order quantum phase transitions in adiabatic quantum computing

Matthias Werner, Artur García-Sáez, Marta P. Estarellas

In the context of adiabatic quantum computation (AQC), it has been argued that first-order quantum phase transitions (QPTs) due to localization phenomena cause AQC to fail by exponentially decreasing the minimal spectral gap of the Hamiltonian along the annealing path as a function of the qubit number. The vanishing of the spectral gap is often linked to the localization of the ground state in a local minimum, requiring the system to tunnel into the global minimum at a later stage of the annealing. Recent methods have been proposed to avoid this phenomenon by carefully designing the involved Hamiltonians. However, it remains a challenge to formulate a comprehensive theory of the effect of the various parameters and the conditions under which QPTs make the AQC algorithm fail. Equipped with concepts from graph theory, in this work we link graph quantities associated with the Hamiltonians along the annealing path with the occurrence of QPTs. These links allow us to derive bounds on the location of the minimal spectral gap along the annealing path, augmenting the toolbox for the analysis of strategies to improve the runtime of AQC algorithms.

arXiv:2301.13861•Physical Review Research•Dec 13, 2023•7 citations
Adiabatic quantum computing is a framework for quantum computing that is superficially very different to the standard circuit model. However, it can be shown that the two models are computationally equivalent. The key to the proof is a mapping of a quantum circuit to an adiabatic evolution, and then showing that the minimum spectral gap of the adiabatic Hamiltonian is at least inverse polynomial in the number of computational steps LLL. In this paper we provide two simplified proofs that the gap is inverse polynomial. Both proofs result in the same lower bound for the minimum gap, which for L\ensuremath≫1L\ensuremath{\gg}1L\ensuremath≫1 is mins\ensuremathΔ0\ensuremath≳\ensuremathπ2/[8(L+1)2]{min}_{s}{\mathrm{\ensuremath{\Delta}}}_{0}\ensuremath{\gtrsim}{\ensuremath{\pi}}^{2}/[8{(L+1)}^{2}]mins​\ensuremathΔ0​\ensuremath≳\ensuremathπ2/[8(L+1)2], an improvement over previous bounds. Our first method is a direct approach based on an eigenstate ansatz, while the second uses Weyl's theorem to leverage known exact results into a bound for the gap. Our results suggest that it may be possible to use these methods to find bounds for spectral gaps of Hamiltonians in other scenarios.
The time or cost of simulating a quantum circuit by adiabatic evolution is determined by the spectral gap of the Hamiltonians involved in the simulation. In "standard" constructions based on Feynman's Hamiltonian, such a gap decreases polynomially with the number of gates in the circuit, L. Because a larger gap implies a smaller cost, we study the limits of spectral gap amplification in this context. We show that, under some assumptions on the ground states and the cost of evolving with the Hamiltonians (which apply to the standard constructions), an upper bound on the gap of the order 1/L follows. In addition, if the Hamiltonians satisfy a frustration-free property, the upper bound is of the order 1/L2. Our proofs use recent results on adiabatic state transformations, spectral gap amplification, and the simulation of continuous-time quantum query algorithms. They also consider a reduction from the unstructured search problem, whose lower bound in the oracle cost translates into the upper bounds in the gaps. The impact of our results is that improving the gap beyond that of standard constructions (i.e. 1/L2), if possible, is challenging.
The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the LLL computation steps and influencing the scaling of the necessary evolution time by its spectral gap of O(1L2)\mathcal{O}\left(\frac{1}{L^2}\right)O(L21​). Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap O(1Lk)\mathcal{O}\left(\frac{1}{L^k}\right)O(Lk1​), k<2k<2k<2, turn out to contradict very likely, graphs with k<1k<1k<1 even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.
The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.
Many problems can be solved by preparing a specific eigenstate of some Hamiltonian HHH. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of HHH for that eigenstate and the cost of evolving with HHH for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian H′H'H′ with the same eigenstate as HHH but a bigger spectral gap, requiring that constant-time evolutions with H′H'H′ and HHH are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when HHH satisfies a frustration-free property and give H′H'H′ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.
We investigate the efficiency of quantum adiabatic optimization when overcoming potential barriers to get from a local to a global minimum. Specifically we look at nnn qubit systems with symmetric cost functions $f:{{0,1}}^{n}\ensuremath{\rightarrow}\mathbb{R}$, where the ground state must tunnel through a potential barrier of width ${n}^{\ensuremath{\alpha}}$ and height ${n}^{\ensuremath{\beta}}$. By the quantum adiabatic theorem the time delay sufficient to ensure tunneling grows quadratically with the inverse spectral gap during this tunneling process. We analyze barrier sizes with $1/2\ensuremath{\le}\ensuremath{\alpha}+\ensuremath{\beta}$ and $\ensuremath{\alpha}<1/2$ and show that the minimum gap scales polynomially as ${n}^{1/2\ensuremath{-}\ensuremath{\alpha}\ensuremath{-}\ensuremath{\beta}}$ when $2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{\le}1$ and exponentially as ${n}^{\ensuremath{-}\ensuremath{\beta}/2}exp(\ensuremath{-}C{n}^{(2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{-}1)/2})$ when $1<2\ensuremath{\alpha}+\ensuremath{\beta}$. Our proof uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone from 2002, which used large spin and instanton methods. Parts of our result also refine recent results by Kong and Crosson [arXiv:1511.06991] and Jiang et al. [arXiv:1603.01293] about the exponential gap scaling.
In the context of adiabatic quantum computation (AQC), it has been argued that first-order quantum phase transitions (QPTs) due to localization phenomena cause AQC to fail by exponentially decreasing the minimal spectral gap of the Hamiltonian along the annealing path as a function of the qubit number. The vanishing of the spectral gap is often linked to the localization of the ground state in a local minimum, requiring the system to tunnel into the global minimum at a later stage of the annealing. Recent methods have been proposed to avoid this phenomenon by carefully designing the involved Hamiltonians. However, it remains a challenge to formulate a comprehensive theory of the effect of the various parameters and the conditions under which QPTs make the AQC algorithm fail. Equipped with concepts from graph theory, in this work we link graph quantities associated with the Hamiltonians along the annealing path with the occurrence of QPTs. These links allow us to derive bounds on the location of the minimal spectral gap along the annealing path, augmenting the toolbox for the analysis of strategies to improve the runtime of AQC algorithms.