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:quant-ph/0601019 · Physical Review A

Simulating adiabatic evolution of gapped spin systems

Tobias J. Osborne

Published Mar 14, 2007• 91 citations
arXivHTMLPDF

Abstract

We show that adiabatic evolution of a low-dimensional lattice of quantum spins with a spectral gap can be simulated efficiently. In particular, we show that as long as the spectral gap $\ensuremath{\Delta}E$ between the ground state and the first excited state is any constant independent of $n$, the total number of spins, then the ground-state expectation values of local operators, such as correlation functions, can be computed using polynomial space and time resources. Our results also imply that the local ground-state properties of any two spin models in the same quantum phase can be efficiently obtained from each other. A consequence of these results is that adiabatic quantum algorithms can be simulated efficiently if the spectral gap does not scale with $n$. The simulation method we describe takes place in the Heisenberg picture and does not make use of the finitely correlated state--matrix product state formalism.

DOI
10.1103/physreva.75.032321

Related papers

Quantum Adiabatic Computation with a Constant Gap Is Not Useful in One Dimension

M. B. Hastings

We show that it is possible to use a classical computer to efficiently simulate the adiabatic evolution of a quantum system in one dimension with a constant spectral gap, starting the adiabatic evolution from a known initial product state. The proof relies on a recently proven area law for such systems, implying the existence of a good matrix product representation of the ground state, combined with an appropriate algorithm to update the matrix product state as the Hamiltonian is changed. This implies that adiabatic evolution with such Hamiltonians is not useful for universal quantum computation. Therefore, adiabatic algorithms which are useful for universal quantum computation either require a spectral gap tending to zero or need to be implemented in more than one dimension (we leave open the question of the computational power of adiabatic simulation with a constant gap in more than one dimension).

arXiv:0902.2960•Physical Review Letters•Jul 27, 2009•22 citations

Ground state of a class of noncritical one-dimensional quantum spin systems can be approximated efficiently

Tobias J. Osborne

We study families ${H}_{n}$ of one-dimensional (1D) quantum spin systems, where $n$ is the number of spins, which have a spectral gap $\ensuremath{\Delta}E$ between the ground-state and first-excited state energy that scales, asymptotically, as a constant in $n$. We show that if the ground state $\ensuremath{\mid}{\ensuremath{\Omega}}_{m}⟩$ of the Hamiltonian ${H}_{m}$ on $m$ spins, where $m$ is an $O(1)$ constant, is locally the same as the ground state $\ensuremath{\mid}{\ensuremath{\Omega}}_{n}⟩$, for arbitrarily large $n$, then an arbitrarily good approximation to the ground state of ${H}_{n}$ can be stored efficiently for all $n$. We formulate a conjecture that, if true, would imply our result applies to all noncritical 1D spin systems. We also include an appendix on quasiadiabatic evolutions.

arXiv:quant-ph/0603137•Physical Review A•Apr 4, 2007•18 citations

Efficient quantum algorithm for Heisenberg spin systems

Sergey Bravyi, David Gosset, Yinchen Liu +1 more

We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by $2μ$, where $μ$ is the magnetic field along the $Z$ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.

quant-pharXiv:2607.14401•Jul 17, 2026•0 citations

Quantum Spin Systems

Amanda Young

This work provides an overview of gapped quantum spin systems, including concepts, techniques, properties, and results. The basic framework and objects of interest for quantum spin systems are introduced, and the main ideas behind methods for proving spectral gaps for frustration-free models are outlined. After reviewing recent progress on several spectral gap conjectures, we discuss quasi-locality of the Heisenberg dynamics and its utility in proving properties of gapped quantum spin systems. Lieb-Robinson bounds have played a central role in establishing exponential decay of ground state correlations, an area law for one-dimensional systems, a many-body adiabatic theorem, and spectral gap stability. They also aided in the development of the quasi-adiabatic continuation, which is a useful for investigating gapped ground state phases, both of which are also discussed.

arXiv:2308.07848•Aug 15, 2023•0 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 preparation without quantum phase transitions

Gernot Schaller

Many physically interesting models show a quantum phase transition when a single parameter is varied through a critical point, where the ground state and the first excited state become degenerate. When this parameter appears as a coupling constant, these models can be understood as straight-line interpolations between different Hamiltonians ${H}_{\mathrm{I}}$ and ${H}_{\mathrm{F}}$. For finite-size realizations however, there will usually be a finite energy gap between ground and first excited state. By slowly changing the coupling constant through the point with the minimum energy gap one thereby has an adiabatic algorithm that prepares the ground state of ${H}_{\mathrm{F}}$ from the ground state of ${H}_{\mathrm{I}}$. The adiabatic theorem implies that in order to obtain a good preparation fidelity the runtime $\ensuremath{\tau}$ should scale with the inverse energy gap and thereby also with the system size. In addition, for open quantum systems not only nonadiabatic but also thermal excitations are likely to occur. It is shown that---using only local Hamiltonians---for the one-dimensional quantum Ising model and the cluster model in a transverse field the conventional straight-line path can be replaced by a series of straight-line interpolations, along which the fundamental energy gap is always greater than a constant independent on the system size. The results are of interest for adiabatic quantum computation since strong similarities between adiabatic quantum algorithms and quantum phase transitions exist.

arXiv:0807.2516•Physical Review A•Sep 23, 2008•28 citations
We show that adiabatic evolution of a low-dimensional lattice of quantum spins with a spectral gap can be simulated efficiently. In particular, we show that as long as the spectral gap \ensuremathΔE\ensuremath{\Delta}E\ensuremathΔE between the ground state and the first excited state is any constant independent of nnn, the total number of spins, then the ground-state expectation values of local operators, such as correlation functions, can be computed using polynomial space and time resources. Our results also imply that the local ground-state properties of any two spin models in the same quantum phase can be efficiently obtained from each other. A consequence of these results is that adiabatic quantum algorithms can be simulated efficiently if the spectral gap does not scale with nnn. The simulation method we describe takes place in the Heisenberg picture and does not make use of the finitely correlated state--matrix product state formalism.
We show that it is possible to use a classical computer to efficiently simulate the adiabatic evolution of a quantum system in one dimension with a constant spectral gap, starting the adiabatic evolution from a known initial product state. The proof relies on a recently proven area law for such systems, implying the existence of a good matrix product representation of the ground state, combined with an appropriate algorithm to update the matrix product state as the Hamiltonian is changed. This implies that adiabatic evolution with such Hamiltonians is not useful for universal quantum computation. Therefore, adiabatic algorithms which are useful for universal quantum computation either require a spectral gap tending to zero or need to be implemented in more than one dimension (we leave open the question of the computational power of adiabatic simulation with a constant gap in more than one dimension).
We study families Hn{H}_{n}Hn​ of one-dimensional (1D) quantum spin systems, where nnn is the number of spins, which have a spectral gap $\ensuremath{\Delta}E$ between the ground-state and first-excited state energy that scales, asymptotically, as a constant in nnn. We show that if the ground state $\ensuremath{\mid}{\ensuremath{\Omega}}_{m}⟩$ of the Hamiltonian Hm{H}_{m}Hm​ on mmm spins, where mmm is an O(1)O(1)O(1) constant, is locally the same as the ground state $\ensuremath{\mid}{\ensuremath{\Omega}}_{n}⟩$, for arbitrarily large nnn, then an arbitrarily good approximation to the ground state of Hn{H}_{n}Hn​ can be stored efficiently for all nnn. We formulate a conjecture that, if true, would imply our result applies to all noncritical 1D spin systems. We also include an appendix on quasiadiabatic evolutions.
We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by 2μ2μ2μ, where μμμ is the magnetic field along the ZZZ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.
This work provides an overview of gapped quantum spin systems, including concepts, techniques, properties, and results. The basic framework and objects of interest for quantum spin systems are introduced, and the main ideas behind methods for proving spectral gaps for frustration-free models are outlined. After reviewing recent progress on several spectral gap conjectures, we discuss quasi-locality of the Heisenberg dynamics and its utility in proving properties of gapped quantum spin systems. Lieb-Robinson bounds have played a central role in establishing exponential decay of ground state correlations, an area law for one-dimensional systems, a many-body adiabatic theorem, and spectral gap stability. They also aided in the development of the quasi-adiabatic continuation, which is a useful for investigating gapped ground state phases, both of which are also discussed.
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.
Many physically interesting models show a quantum phase transition when a single parameter is varied through a critical point, where the ground state and the first excited state become degenerate. When this parameter appears as a coupling constant, these models can be understood as straight-line interpolations between different Hamiltonians HI{H}_{\mathrm{I}}HI​ and HF{H}_{\mathrm{F}}HF​. For finite-size realizations however, there will usually be a finite energy gap between ground and first excited state. By slowly changing the coupling constant through the point with the minimum energy gap one thereby has an adiabatic algorithm that prepares the ground state of HF{H}_{\mathrm{F}}HF​ from the ground state of HI{H}_{\mathrm{I}}HI​. The adiabatic theorem implies that in order to obtain a good preparation fidelity the runtime $\ensuremath{\tau}$ should scale with the inverse energy gap and thereby also with the system size. In addition, for open quantum systems not only nonadiabatic but also thermal excitations are likely to occur. It is shown that---using only local Hamiltonians---for the one-dimensional quantum Ising model and the cluster model in a transverse field the conventional straight-line path can be replaced by a series of straight-line interpolations, along which the fundamental energy gap is always greater than a constant independent on the system size. The results are of interest for adiabatic quantum computation since strong similarities between adiabatic quantum algorithms and quantum phase transitions exist.