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

Bulletin of the American Physical Society

Locally accurate matrix product state approximations with constant bond dimension for ground states of gapped 1D models

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

Published Mar 5, 2019• 0 citations
OpenAlex

Related papers

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

Matrix Product State and 1D Gapped Phases

Bei Zeng, Xie Chen, D. L. Zhou +1 more

Quantum science and technology•Jan 1, 2019•0 citations

Exact ground states of one-dimensional quantum systems: matrix product approach

Gang Su

arXiv:cond-mat/9606012•Physics Letters A•Apr 1, 1996•10 citations

1D area law with ground-state degeneracy

Yichen Huang

An area law is proved for the Renyi entanglement entropy of possibly degenerate ground states in one-dimensional gapped quantum systems. Suppose in a chain of $n$ spins the ground states of a local Hamiltonian with energy gap $\epsilon$ are constant-fold degenerate. Then, the Renyi entanglement entropy $R_\alpha(0<\alpha<1)$ of any ground state across any cut is upper bounded by $\tilde O(\alpha^{-3}/\epsilon)$, and any ground state can be well approximated by a matrix product state of subpolynomial bond dimension $2^{\tilde O(\epsilon^{-1/4}\log^{3/4}n)}$.

•Mar 3, 2014•1 citation

Locally accurate matrix product approximation to thermal states

Yichen Huang

arXiv:2106.03854•中国科学通报：英文版•Aug 19, 2021•5 citations

A polynomial-time algorithm for 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. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.

arXiv:1307.5143•Jul 19, 2013•25 citations
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.
An area law is proved for the Renyi entanglement entropy of possibly degenerate ground states in one-dimensional gapped quantum systems. Suppose in a chain of nnn spins the ground states of a local Hamiltonian with energy gap ϵ\epsilonϵ are constant-fold degenerate. Then, the Renyi entanglement entropy Rα(0<α<1)R_\alpha(0<\alpha<1)Rα​(0<α<1) of any ground state across any cut is upper bounded by O~(α−3/ϵ)\tilde O(\alpha^{-3}/\epsilon)O~(α−3/ϵ), and any ground state can be well approximated by a matrix product state of subpolynomial bond dimension 2O~(ϵ−1/4log⁡3/4n)2^{\tilde O(\epsilon^{-1/4}\log^{3/4}n)}2O~(ϵ−1/4log3/4n).
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.