A Caltech Library Service

An area law and sub-exponential algorithm for 1D systems

Arad, Itai and Kitaev, Alexei and Landau, Zeph and Vazirani, Umesh (2013) An area law and sub-exponential algorithm for 1D systems. . (Submitted)

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result [1]. Specifically, we show that for a chain of d-dimensional spins, governed by a 1D local Hamiltonian with a spectral gap ε > 0, the entanglement entropy of the ground state with respect to any cut in the chain is upper bounded by O(log^3 d/ε ). Our approach uses the framework of Refs. [2, 3] to construct a Chebyshev-based AGSP (Approximate Ground Space Projection) with favorable factors. However, our construction uses the Hamiltonian directly, instead of using the Detectability lemma, which allows us to work with general (frustrated) Hamiltonians, as well as slightly improving the 1/ε dependence of the bound in Ref. [3]. To achieve that, we establish a new, “random-walk like”, bound on the entanglement rank of an arbitrary power of a 1D Hamiltonian, which might be of independent interest: ER(H^ℓ) ≤ (ℓd)O(√ℓ). Finally, treating d as a constant, our AGSP shows that the ground state is well approximated by a matrix product state with a sublinear bond dimension B = ε ^O(log^(3/4) n/ε^(1/4)). Using this in conjunction with known dynamical programing algorithms, yields an algorithm for a 1=poly(n) approximation of the ground energy with a subexponential running time T ≤ exp (εO(log^(3/4) n/ε^(1/4))).

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Additional Information:We are grateful to Dorit Aharonov, Fernando Brandao, and Matt Hastings for inspiring discussions about the above and related topics.
Group:UNSPECIFIED, Institute for Quantum Information and Matter
Record Number:CaltechAUTHORS:20140130-142058060
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:43591
Deposited By: Tony Diaz
Deposited On:30 Jan 2014 22:41
Last Modified:04 Jun 2020 10:14

Repository Staff Only: item control page