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/0603137 · Physical Review A

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

Tobias J. Osborne

Published Apr 4, 2007• 18 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.75.042306

Related papers

Simulating adiabatic evolution of gapped spin systems

Tobias J. Osborne

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.

arXiv:quant-ph/0601019•Physical Review A•Mar 14, 2007•91 citations

Efficient algorithm for approximating one-dimensional ground states

Dorit Aharonov, Itai Arad, Sandy Irani

The density-matrix renormalization-group method is very effective at finding ground states of one-dimensional (1D) quantum systems in practice, but it is a heuristic method, and there is no known proof for when it works. In this article we describe an efficient classical algorithm which provably finds a good approximation of the ground state of 1D systems under well-defined conditions. More precisely, our algorithm finds a matrix product state of bond dimension $D$ whose energy approximates the minimal energy such states can achieve. The running time is exponential in $D$, and so the algorithm can be considered tractable even for $D$, which is logarithmic in the size of the chain. The result also implies trivially that the ground state of any local commuting Hamiltonian in 1D can be approximated efficiently; we improve this to an exact algorithm.

arXiv:0910.5055•Physical Review A•Jul 16, 2010•22 citations

Entanglement versus gap for one-dimensional spin systems

Daniel Gottesman, M. B. Hastings

We study the relationship between entanglement and spectral gap for local Hamiltonians in one dimension (1D). The area law for a 1D system states that for the ground state, the entanglement of any interval is upper bounded by a constant independent of the size of the interval. However, the possible dependence of the upper bound on the spectral gap Δ is not known, as the best known general upper bound is asymptotically much larger than the largest possible entropy of any model system previously constructed for small Δ. To help resolve this asymptotic behavior, we construct a family of 1D local systems for which some intervals have entanglement entropy, which is polynomial in 1/Δ, whereas previously studied systems, such as free fermion systems or systems described by conformal field theory, had the entropy of all intervals bounded by a constant time log(1/Δ).

arXiv:0901.1108•New Journal of Physics•Feb 26, 2010•63 citations

Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians

Alexander M. Dalzell, Fernando G. S. L. Brandão

A key feature of ground states of gapped local 1D Hamiltonians is their relatively low entanglement --- they are well approximated by matrix product states (MPS) with bond dimension scaling polynomially in the length N of the chain, while general states require a bond dimension scaling exponentially. We show that the bond dimension of these MPS approximations can be improved to a constant, independent of the chain length, if we relax our notion of approximation to be more local: for all length- k segments of the chain, the reduced density matrices of our approximations are ϵ -close to those of the exact state. If the state is a ground state of a gapped local Hamiltonian, the bond dimension of the approximation scales like (k/ϵ)1+o(1) , and at the expense of worse but still poly (k,1/ϵ) scaling of the bond dimension, we give an alternate construction with the additional features that it can be generated by a constant-depth quantum circuit with nearest-neighbor gates, and that it applies generally for any state with exponentially decaying correlations. For a completely general state, we give an approximation with bond dimension exp⁡(O(k/ϵ)) , which is exponentially worse, but still independent of N . Then, we consider the prospect of designing an algorithm to find a local approximation for ground states of gapped local 1D Hamiltonians. When the Hamiltonian is translationally invariant, we show that the ability to find O(1) -accurate local approximations to the ground state in T(N) time implies the ability to estimate the ground state energy to O(1) precision in O(T(N)log⁡(N)) time.

arXiv:1903.10241•Quantum•Sep 23, 2019•31 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

An efficient algorithm for finding the ground state of 1D gapped local hamiltonians

Zeph A. Landau, Umesh V. Vazirani, Thomas Vidick

Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMA-complete, even for one-dimensional Hamiltonians [1]. This means that we do not even expect that there is a sub-exponential size description of the ground state that allows efficient computation of local observables such as the energy. In sharp contrast, the heuristic density matrix renormalization group (DMRG) algorithm invented two decades ago [5] has been remarkably successful in practice on one-dimensional problems. The situation is reminiscent of the unexplained success of the simplex algorithm before the advent of ellipsoid and interior-point methods. Is there a principled explanation for this, in the form of a large class of one-dimensional Hamiltonians whose ground states can be provably efficiently approximated? Here we give such an algorithm for gapped one-dimensional Hamiltonians: our algorithm outputs an (inverse-polynomial) approximation to the ground state, expressed as a matrix product state (MPS) of polynomial bond dimension. The running time of the algorithm is polynomial in the number of qudits n and the approximation quality δ, for a fixed local dimension d and gap Δ > 0.

Conference on Innovations in Theoretical Computer Science•Jan 12, 2014•5 citations
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ΔE\ensuremath{\Delta}E\ensuremathΔ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∣\ensuremathΩm⟩\ensuremath{\mid}{\ensuremath{\Omega}}_{m}⟩\ensuremath∣\ensuremathΩ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∣\ensuremathΩn⟩\ensuremath{\mid}{\ensuremath{\Omega}}_{n}⟩\ensuremath∣\ensuremathΩ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 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 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.
The density-matrix renormalization-group method is very effective at finding ground states of one-dimensional (1D) quantum systems in practice, but it is a heuristic method, and there is no known proof for when it works. In this article we describe an efficient classical algorithm which provably finds a good approximation of the ground state of 1D systems under well-defined conditions. More precisely, our algorithm finds a matrix product state of bond dimension DDD whose energy approximates the minimal energy such states can achieve. The running time is exponential in DDD, and so the algorithm can be considered tractable even for DDD, which is logarithmic in the size of the chain. The result also implies trivially that the ground state of any local commuting Hamiltonian in 1D can be approximated efficiently; we improve this to an exact algorithm.
We study the relationship between entanglement and spectral gap for local Hamiltonians in one dimension (1D). The area law for a 1D system states that for the ground state, the entanglement of any interval is upper bounded by a constant independent of the size of the interval. However, the possible dependence of the upper bound on the spectral gap Δ is not known, as the best known general upper bound is asymptotically much larger than the largest possible entropy of any model system previously constructed for small Δ. To help resolve this asymptotic behavior, we construct a family of 1D local systems for which some intervals have entanglement entropy, which is polynomial in 1/Δ, whereas previously studied systems, such as free fermion systems or systems described by conformal field theory, had the entropy of all intervals bounded by a constant time log(1/Δ).
A key feature of ground states of gapped local 1D Hamiltonians is their relatively low entanglement --- they are well approximated by matrix product states (MPS) with bond dimension scaling polynomially in the length N of the chain, while general states require a bond dimension scaling exponentially. We show that the bond dimension of these MPS approximations can be improved to a constant, independent of the chain length, if we relax our notion of approximation to be more local: for all length- k segments of the chain, the reduced density matrices of our approximations are ϵ -close to those of the exact state. If the state is a ground state of a gapped local Hamiltonian, the bond dimension of the approximation scales like (k/ϵ)1+o(1) , and at the expense of worse but still poly (k,1/ϵ) scaling of the bond dimension, we give an alternate construction with the additional features that it can be generated by a constant-depth quantum circuit with nearest-neighbor gates, and that it applies generally for any state with exponentially decaying correlations. For a completely general state, we give an approximation with bond dimension exp⁡(O(k/ϵ)) , which is exponentially worse, but still independent of N . Then, we consider the prospect of designing an algorithm to find a local approximation for ground states of gapped local 1D Hamiltonians. When the Hamiltonian is translationally invariant, we show that the ability to find O(1) -accurate local approximations to the ground state in T(N) time implies the ability to estimate the ground state energy to O(1) precision in O(T(N)log⁡(N)) time.
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.
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMA-complete, even for one-dimensional Hamiltonians [1]. This means that we do not even expect that there is a sub-exponential size description of the ground state that allows efficient computation of local observables such as the energy. In sharp contrast, the heuristic density matrix renormalization group (DMRG) algorithm invented two decades ago [5] has been remarkably successful in practice on one-dimensional problems. The situation is reminiscent of the unexplained success of the simplex algorithm before the advent of ellipsoid and interior-point methods. Is there a principled explanation for this, in the form of a large class of one-dimensional Hamiltonians whose ground states can be provably efficiently approximated? Here we give such an algorithm for gapped one-dimensional Hamiltonians: our algorithm outputs an (inverse-polynomial) approximation to the ground state, expressed as a matrix product state (MPS) of polynomial bond dimension. The running time of the algorithm is polynomial in the number of qudits n and the approximation quality δ, for a fixed local dimension d and gap Δ > 0.