Source-linked AI summary
An area law and sub-exponential algorithm for 1D systems
Itai Arad, Alexei Kitaev, Zeph Landau, Umesh Vazirani
TL;DR
The paper addresses how to prove strong area laws for general gapped 1D Hamiltonians, including frustrated systems. It constructs a Chebyshev-based AGSP using local Hamiltonian truncation and proves a new entanglement-rank bound. The resulting entropy bound and sublinear MPS approximations support a subexponential algorithm for approximating the ground energy.
Problem
Prior area-law results for 1D systems were limited in scope or had weaker bounds, motivating a proof for general gapped, including frustrated, Hamiltonians.
Method
The paper constructs a Chebyshev-based AGSP directly from a locally truncated Hamiltonian and establishes a random-walk-like entanglement-rank bound for Hamiltonian powers.
Results
O(log^3 d/ϵ) bounds the ground-state entanglement entropy for general 1D Hamiltonians, while the construction also gives exponentially close ground states for the truncated Hamiltonians.
Takeaways & Limitations
The AGSP yields sublinear bond dimension MPS approximations and a subexponential-time algorithm for approximating the ground energy.
Takeaways & Limitations
The analysis includes assumptions such as bounded exterior Hamiltonian norms in the frustration-free case and a unique ground state with a spectral gap.
Abstract
from arXiv · showhide
We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result \cite{ref:Has07}. Specifically, we show that for a chain of d-dimensional spins, governed by a 1D local Hamiltonian with a spectral gap \eps>0, the entanglement entropy of the ground state with respect to any cut in the chain is upper bounded by $O{\frac{\log^3 d}{\eps}}$. Our approach uses the framework Arad et al 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/\eps$ dependence of the bound in Arad et al. 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^\ell} \le (\ell d)^{O(\sqrt{\ell})}. 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=e^{O(\log^{3/4}n/\eps^{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\le \exp(e^{O(\log^{3/4}n/\eps^{1/4})}).
1 Introduction
The paper develops an area-law proof for general gapped 1D Hamiltonians, improving prior bounds and establishing consequences for matrix product state approximation and computation. Its approach combines local truncation, Chebyshev-based AGSPs, and a random-walk-like entanglement-rank bound.
- Motivation and prior work: The area law bounds ground-state entanglement entropy in gapped 1D systems independently of the chain length, with prior work scaling as e^O(log d/ϵ).This result also places approximation of gapped 1D ground states in NP.
- Main contributions: O(log^3 d/ϵ) is the paper’s improved entropy bound for general, including frustrated, 1D Hamiltonians.The gap dependence also improves the previous best bound for frustration-free systems and may be tight up to logarithmic factors.
- Main contributions: Sublinear bond dimension MPS approximations yield a subexponential-time algorithm for finding approximate ground states.The paper presents this as evidence that the task is not NP-hard.
- Main contributions: The paper establishes a random-walk-like bound on the entanglement rank of powers of a 1D Hamiltonian.This property is presented as potentially independently interesting.
- Proof strategy: The method isolates a neighborhood around the cut, replaces the exterior by multiparticle Hamiltonians, and constructs an AGSP using the resulting bounded-norm Hamiltonian.This direct Hamiltonian construction extends the framework beyond frustration-free systems.
- Proof strategy: In the frustrated case, the proof uses a sequence of Hamiltonians whose ground states converge to the original ground state while balancing convergence against entanglement-rank growth.This tradeoff is the basis for deriving the entropy bound.
2 Background: Approximate Ground State Projectors and their consequences
The AGSP framework characterizes operators that suppress excited-state components while controlling entanglement growth. A favorable balance between these effects yields an area-law entropy bound.
- AGSP framework: An AGSP is an operator whose repeated application moves a product state toward the ground state while keeping its entanglement rank controlled.The framework starts from a product state and repeatedly applies such an operator.
- AGSP framework: The parameter D bounds the AGSP’s entanglement rank across a cut and limits the multiplicative entanglement-rank increase on arbitrary states.For a state |φ⟩, the framework gives ER(K|φ⟩) ≤ D · ER(φ).
- AGSP framework: The parameter ∆ captures the rate at which the AGSP suppresses components away from the ground state.Together, D and ∆ quantify the tradeoff between approaching the ground state and incurring entanglement.
- Area-law consequence: A suitable product-state overlap together with an AGSP provides conditions for bounding the ground-state entanglement entropy.The framework combines an overlap condition with an AGSP condition to obtain an area law.
- Area-law consequence: D · ∆ ≤ 1/2 is the stated AGSP condition under which the area-law corollary applies.The corollary then bounds the ground-state entropy.
3 Overview
The overview constructs an AGSP by truncating the Hamiltonian away from a cut, applying a Chebyshev polynomial, and controlling entanglement rank through a random-walk-like power bound. A robustness theorem then extends the approach from frustration-free to frustrated systems, yielding the area-law scaling.
- Hamiltonian truncation: The method truncates the Hamiltonian outside a small neighborhood of the cut, producing a norm-bounded Hamiltonian with isolated middle terms.The truncated Hamiltonian has the form H = HL + H1 + ··· + Hs + HR.
- Chebyshev AGSP: A suitable Chebyshev polynomial of the truncated Hamiltonian serves as the AGSP.The construction uses K = Cℓ(H) to approximate projection onto the ground state.
- Entanglement-rank bound: The entanglement-rank analysis expands powers of H into local-term products and exploits a term occurring at most ℓ/s times across the relevant decomposition.Formal commuting variables reduce the number of operator combinations that must be controlled.
- Frustration-free case: For frustration-free systems, choosing ℓ = O(s^2) and s = ˜O(log^2(d)/ϵ) yields an entanglement entropy bound of ˜O(log^3(d)/ϵ).The bound follows by applying Theorem 2.4 to the constructed AGSP.
- Frustrated case: For frustrated systems, ground states of the truncated Hamiltonians are exponentially close to those of the original Hamiltonian, so a sequence of AGSPs guides convergence to the ground state.The robustness theorem also preserves spectral gaps up to the same order.
4 Approximate Ground State Projector
This section defines the AGSP framework and bounds the entanglement rank of Chebyshev-polynomial operators. The resulting parameter choices establish the area law for frustration-free 1D Hamiltonians.
- Setup: The Hamiltonian is assumed to have a unique ground state, spectral gap ϵ, and spectrum above the ground energy contained in [ϵ1,u].The target entanglement entropy is across the middle cut of the isolated region.
- AGSP construction: The AGSP is defined as K = Cℓ(H), where Cℓ is a degree-ℓ polynomial designed to preserve the ground state and shrink excited-state components.The polynomial is obtained by rescaling a Chebyshev polynomial.
- Entanglement-rank analysis: The entanglement rank of K is bounded by D = (dℓ)^{O(max{ℓ/s, ...})}, using a generating-function decomposition of H^ℓ.Grouping products by local-term multiplicities ensures some middle term appears at most ℓ/s times.
- Frustration-free reduction: For frustration-free Hamiltonians, truncating the left and right ends preserves the ground state and retains a gap at least a constant times ϵ.The truncation parameter is chosen so the truncated Hamiltonian has the same ground state as the original.
- Area-law conclusion: Choosing ℓ = s^2/2 and s = O(log^2(d)/ϵ) makes the AGSP parameters satisfy the contraction condition required by Corollary 2.4.This yields the stated area-law entropy bound.
5 Low bond dimension MPS for frustration free 1D Hamiltonians
The AGSP construction implies that ground states of frustration-free gapped 1D Hamiltonians admit accurate matrix product state approximations with sublinear bond dimension.
- Approximation strategy: It suffices to construct a state with bounded entanglement rank and then apply an AGSP whose shrinking coefficient is 1/poly(n).The AGSP converts a constant-overlap state into the desired approximation.
- Parameter choice: Choosing ℓ = s^2 and s = O(ϵ^-1/3 log^(2/3)n) gives the required shrinking coefficient while producing bond dimension D = exp(O(ϵ^-1/3 log^(2/3)n)).These parameter choices are stated for the AGSP used in the MPS construction.
6 Frustrated Case
The frustrated-case proof replaces the original Hamiltonian by truncated Hamiltonians whose ground states and gaps remain controlled, then uses a sequence of AGSPs to approach the original ground state while bounding entanglement.
- Setup: The construction targets a general gapped local Hamiltonian with unique ground state and spectral gap ϵ, including frustrated systems.The Hamiltonian is decomposed into left, central, and right terms around the cut, with local central interactions and positive outer operators.
- Truncation and robustness: Truncation produces H(t) with bounded norm, but its ground state differs from the original, so a robustness theorem is required.For sufficiently large t, the truncated and original ground states are exponentially close and their spectral gaps have the same order.
- Iterative AGSP construction: A sequence t0,t1,… of truncated Hamiltonians avoids the large entanglement-rank cost of applying one AGSP at a large truncation threshold.The associated AGSPs guide successive approximations toward the original ground state while controlling the rank increase at each step.
- Area law: The resulting area-law bound is O(log^3 d / ϵ) for the ground-state entanglement entropy across the specified cut.The entropy estimate sums contributions of size O(2^-i) weighted by log Ri.
- Iterative AGSP construction: The constructed states have controlled entanglement ranks and converge to the ground state, with approximation error decreasing as 2^-i.The initial rank satisfies log R0 = O(log^3 d / ϵ), while later ranks accumulate bounded AGSP costs.
7 Sub exponential algorithm for finding the ground energy of gapped 1D Hamiltonians
The paper uses its AGSP approximation to represent the ground state by a sublinear-bond-dimension MPS and then applies dynamical programming to obtain a subexponential ground-energy algorithm.
- MPS approximation: For constant d, the ground state is approximated to inverse-polynomial accuracy by an MPS with sublinear bond dimension B = exp̃(O(log^3/4 n / ϵ^1/4)).The approximation is obtained by combining the AGSP construction with a suitable truncation and polynomial degree.
- Ground-energy algorithm: A 1/poly(n) approximation to the ground energy is found in time T ≤ exp(exp̃(O(log^3/4 n / ϵ^1/4))).The runtime follows from known dynamical programming algorithms applied to the MPS representation.
- Ground-energy algorithm: For constant spectral gap, finding a 1/poly(n) approximation to the ground energy is not NP-hard unless 3-SAT has a subexponential-time algorithm.This is stated as the paper’s complexity-theoretic corollary.