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:1307.4993 · International Journal of Quantum Information

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

Anand Ganti, Rolando D. Somma

Published Oct 1, 2013• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1142/s0219749913500639

Related papers

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

Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds

Shane Dooley, Graham Kells, Hosho Katsura +1 more

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.

arXiv:1906.05233•Physical Review A•Apr 1, 2020•5 citations

Improved bounds for eigenpath traversal

Hao-Tien Lewis Chiang, Guanglei Xu, Rolando D. Somma

We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\ensuremath{\Delta}$. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/{\ensuremath{\Delta}}^{2}$, and a method based on fixed-point search has a maximum cost of order $1/{\ensuremath{\Delta}}^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/{\ensuremath{\Delta}}^{3/2}$ and $1/\ensuremath{\Delta}$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/{\ensuremath{\Delta}}^{3}$.

arXiv:1311.7073•Physical Review A•Jan 15, 2014•17 citations

On optimal methods for adiabatic quantum state transformations

Rolando D. Somma

Many problems in science could be solved by preparing the low-energy quantum state (or any eigenstate) of a Hamiltonian. A common example is the Boolean satisfiability problem, where each clause can be mapped to the energy of an interacting many-body system, and the problem reduces to minimizing the energy. In quantum computing, adiabatic quantum state transformations (ASTs) provide a tool for preparing the quantum state. ASTs are conventionally implemented via slow or adiabatic perturbations to the Hamiltonian, relying on the quantum adiabatic theorem. Nevertheless, more efficient implementations of ASTs exist. In this talk I will review recently developed methods for ASTs that are more efficient and require less assumptions on the Hamiltonians than the conventional implementation [1,2]. Such methods involve measurements of the states along the evolution path and have a best-case implementation cost of L/G, where L is the length of the (evolved) state path and G is a lower bound to the spectral gap of the Hamiltonians. I will show that this cost is optimal [3] and comment on results of the gap amplification problem, where the goal is to reduce the cost by increasing G [4].

Bulletin of the American Physical Society•Mar 18, 2013•0 citations

Analysis and limitations of modified circuit-to-Hamiltonian constructions

Johannes Bausch, Elizabeth Crosson

Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω(T−2) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O(T−2) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω(T−3) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O(T−2) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.

arXiv:1609.08571•Quantum•Sep 19, 2018•18 citations

Analysis and limitations of modified circuit-to-Hamiltonian constructions

Johannes Bausch, Elizabeth Crosson

Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω ( T − 2 ) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O ( T − 2 ) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω ( T − 3 ) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O ( T − 2 ) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.

•Sep 19, 2018•16 citations
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.
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.
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{\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.
We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\ensuremath{\Delta}$. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/{\ensuremath{\Delta}}^{2}$, and a method based on fixed-point search has a maximum cost of order $1/{\ensuremath{\Delta}}^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/{\ensuremath{\Delta}}^{3/2}$ and $1/\ensuremath{\Delta}$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/{\ensuremath{\Delta}}^{3}$.
Many problems in science could be solved by preparing the low-energy quantum state (or any eigenstate) of a Hamiltonian. A common example is the Boolean satisfiability problem, where each clause can be mapped to the energy of an interacting many-body system, and the problem reduces to minimizing the energy. In quantum computing, adiabatic quantum state transformations (ASTs) provide a tool for preparing the quantum state. ASTs are conventionally implemented via slow or adiabatic perturbations to the Hamiltonian, relying on the quantum adiabatic theorem. Nevertheless, more efficient implementations of ASTs exist. In this talk I will review recently developed methods for ASTs that are more efficient and require less assumptions on the Hamiltonians than the conventional implementation [1,2]. Such methods involve measurements of the states along the evolution path and have a best-case implementation cost of L/G, where L is the length of the (evolved) state path and G is a lower bound to the spectral gap of the Hamiltonians. I will show that this cost is optimal [3] and comment on results of the gap amplification problem, where the goal is to reduce the cost by increasing G [4].
Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω(T−2) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O(T−2) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω(T−3) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O(T−2) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.
Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω ( T − 2 ) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O ( T − 2 ) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω ( T − 3 ) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O ( T − 2 ) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.