Rigorous RG algorithms and area laws for low energy eigenstates in 1D
arXiv:1602.08828 · doi:10.1007/s00220-017-2973-z
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() dimensional), or for the poly() 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() degenerate ground spaces and an algorithm for the poly() 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 , where is the time required to multiply two matrices.
arXiv commentMultiple improvements in presentation; results unchanged. To appear in Comm. Math. Phys
References in corpus (20)
- The density-matrix renormalization group in the age of matrix product states
- Area laws for the entanglement entropy - a review
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- Eternal Black Holes in AdS
- An Area Law for One Dimensional Quantum 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
- Topological quantum order: stability under local perturbations
- Solving Gapped Hamiltonians Locally
- Approximating Gibbs states of local Hamiltonians efficiently with PEPS
- Locality of temperature
- Tensor network renormalization yields the multi-scale entanglement renormalization ansatz
- An area law for the entropy of low-energy states
- Spectra and eigenstates of spin chain Hamiltonians
- An improved 1D area law for frustration-free systems
- Connecting global and local energy distributions in quantum spin models on a lattice
- A simple proof of the detectability lemma and spectral gap amplification
- Ground states of unfrustrated spin Hamiltonians satisfy an area law
- Implementation of rigorous renormalization group method for ground space and low-energy states of local Hamiltonians
Cited by in corpus (55)
- 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
- Topological phase transition and index for quantum spin chains
- Efficient Machine Learning Representations of Surface Code with Boundaries, Defects, Domain Walls and Twists
- 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
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- 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
- Undecidability of the Spectral Gap (full version)
- Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
- Gaplessness is not generic for translation-invariant spin chains
- Infinite randomness with continuously varying critical exponents in the random XYZ spin chain
- Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
- Generalized Thouless Pumps in 1+1-dimensional Interacting Fermionic Systems
- Quantitatively improved finite-size criteria for spectral gaps
- Thermal Area Law in Long-Range Interacting Systems
- Random translation-invariant Hamiltonians and their spectral gaps
- Two-dimensional local Hamiltonian problem with area laws is QMA-complete
- Performance of the rigorous renormalization group for first order phase transitions and topological phases
- Universal noise-precision relations in variational quantum algorithms
- Thermal Area Law for Lattice Bosons
- Bounded entanglement entropy in the quantum Ising model
- Clustering of conditional mutual information and quantum Markov structure at arbitrary temperatures
- The Kibble Zurek Mechanism of Topological Defect Formation in Quantum Field Theory with Matrix Product States
- Entanglement subvolume law for 2D frustration-free spin systems
- Probing holography in -adic CFT
- Lower Bounds for Unitary Property Testing with Proofs and Advice
- Adiabatic ground state preparation in an expanding lattice
- On Hastings factorization for quantum many-body systems in the infinite volume setting
- 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
- 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 local spin Hamiltonians