CaltechAUTHORS
  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) http://resolver.caltech.edu/CaltechAUTHORS:20140130-142058060

[img]
Preview
PDF - Submitted Version
See Usage Policy.

472Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140130-142058060

Abstract

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
http://arxiv.org/abs/1301.1162v1arXivDiscussion Paper
Additional Information:We are grateful to Dorit Aharonov, Fernando Brandao, and Matt Hastings for inspiring discussions about the above and related topics.
Group:IQIM, Institute for Quantum Information and Matter
Record Number:CaltechAUTHORS:20140130-142058060
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20140130-142058060
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:43591
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:30 Jan 2014 22:41
Last Modified:30 Jan 2014 22:41

Repository Staff Only: item control page