A polynomial-time algorithm for ground states of spin trees

Abstract

We prove that the ground states of a local Hamiltonian satisfy an area law and can be computed in polynomial time when the interaction graph is a tree with discrete fractal dimension $\beta <2$. This condition is met for generic trees in the plane and for established models of hyperbranched polymers in 3D. This work is the first to prove an area law and exhibit a provably polynomial-time classical algorithm for local Hamiltonian ground states beyond the case of spin chains. Our algorithm outputs the ground state encoded as a multi-scale tensor network on the META-tree, which we introduce as an analogue of Vidal's MERA. Our results hold for polynomially degenerate and frustrated ground states, matching the state of the art for local Hamiltonians on a line.

arXiv comment53 pages, 5 figures. Added remark on page 6 (v3). Corrected factor D to term log D in theorem 2.1

References in corpus (9)

• An Area Law for One Dimensional Quantum Systems
• A class of quantum many-body states that can be efficiently simulated
• Classical simulation of quantum many-body systems with a tree tensor network
• Solving Gapped Hamiltonians Locally
• Approximating Gibbs states of local Hamiltonians efficiently with PEPS
• Stochastic Error Cancellation in Analog Quantum Simulation
• An improved 1D area law for frustration-free systems
• Connecting global and local energy distributions in quantum spin models on a lattice
• The dimension of loop-erased random walk in 3D

Cited by in corpus (2)

• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Sharp implications of AGSPs for degenerate ground spaces