Rigorous RG algorithms and area laws for low energy eigenstates in 1D

Abstract

One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance of Landau et al. gave a polynomial time algorithm to actually compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unresolved, including whether there exist rigorous efficient algorithms when the ground space is degenerate (and poly($n$) dimensional), or for the poly($n$) lowest energy states for 1D systems, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm for finding low energy states for 1D systems, based on a rigorously justified RG type transformation. In the process we resolve some of the aforementioned open questions, including giving a polynomial time algorithm for poly($n$) degenerate ground spaces and an $n^{O(\log n)}$ algorithm for the poly($n$) lowest energy states for 1D systems (under a mild density condition). We note that for these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustration-free Hamiltonians the running time is $\tilde{O}(nM(n))$, where $M(n)$ is the time required to multiply two $n\times n$ matrices.

Multiple improvements in presentation; results unchanged. To appear in Comm. Math. Phys

References in corpus (9)

• The density-matrix renormalization group in the age of matrix product states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• A class of quantum many-body states that can be efficiently simulated
• Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Approximating Gibbs states of local Hamiltonians efficiently with PEPS
• Tensor network renormalization yields the multi-scale entanglement renormalization ansatz
• A simple proof of the detectability lemma and spectral gap amplification
• Implementation of rigorous renormalization group method for ground space and low-energy states of local Hamiltonians

Cited by in corpus (53)

• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Provably efficient machine learning for quantum many-body problems
• Quantum Neural Network States: A Brief Review of Methods and Applications
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Isometric Tensor Network representation of string-net liquids
• Area law of non-critical ground states in 1D long-range interacting systems
• Contracting projected entangled pair states is average-case hard
• An area law for 2D frustration-free spin systems
• Spectral gaps of frustration-free spin systems with boundary
• Faster Quantum Algorithm to simulate Fermionic Quantum Field Theory
• A generalization of the injectivity condition for Projected Entangled Pair States
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Efficient description of many-body systems with Matrix Product Density Operators
• Quantum many-body systems in thermal equilibrium
• Efficient Machine Learning Representations of Surface Code with Boundaries, Defects, Domain Walls and Twists
• Topological phase transition and ${\mathbb{Z}}_2$ index for $S=1$ quantum spin chains
• How much entanglement is needed to reduce the energy variance?
• Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians
• Matrix product state algorithms for Gaussian fermionic states
• Projected Entangled Pair States: Fundamental analytical and numerical limitations
• Importance of the spectral gap in estimating ground-state energies
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Local minima in quantum systems
• Optimization at the boundary of the tensor network variety
• Locality at the boundary implies gap in the bulk for 2D PEPS
• Implementation of rigorous renormalization group method for ground space and low-energy states of local Hamiltonians
• Gaplessness is not generic for translation-invariant spin chains
• Undecidability of the Spectral Gap (full version)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Infinite randomness with continuously varying critical exponents in the random XYZ spin chain
• Generalized Thouless Pumps in 1+1-dimensional Interacting Fermionic Systems
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Quantitatively improved finite-size criteria for spectral gaps
• Thermal Area Law in Long-Range Interacting Systems
• Random translation-invariant Hamiltonians and their spectral gaps
• Performance of the rigorous renormalization group for first order phase transitions and topological phases
• The Kibble Zurek Mechanism of Topological Defect Formation in Quantum Field Theory with Matrix Product States
• Clustering of conditional mutual information and quantum Markov structure at arbitrary temperatures
• Universal noise-precision relations in variational quantum algorithms
• Bounded entanglement entropy in the quantum Ising model
• Thermal Area Law for Lattice Bosons
• Entanglement subvolume law for 2D frustration-free spin systems
• Probing holography in $p$-adic CFT
• Lower Bounds for Unitary Property Testing with Proofs and Advice
• Provably Efficient Simulation of 1D Long-Range Interacting Systems at Any Temperature
• Positive bias makes tensor-network contraction tractable
• Area laws and tensor networks for maximally mixed ground states
• On Hastings factorization for quantum many-body systems in the infinite volume setting
• Adiabatic ground state preparation in an expanding lattice
• Sample complexity of matrix product states at finite temperature
• Entanglement area law and Lieb-Schultz-Mattis theorem in long-range interacting systems, and symmetry-enforced long-range entanglement
• Energy Spectra of Compressed Quantum States
• Spectral statistics and energy-gap scaling in $k-$local spin Hamiltonians