Two-dimensional local Hamiltonian problem with area laws is QMA-complete
arXiv:1411.6614 · doi:10.1109/ISIT44484.2020.9174029 10.1016/j.jcp.2021.110534
Abstract
We show that the two-dimensional (2D) local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete. We also prove similar results in 2D translation-invariant systems and for the 3D Heisenberg and Hubbard models with local magnetic fields. Consequently, unless MA = QMA, not all ground states of 2D local Hamiltonians with area laws have efficient classical representations that support efficient computation of local expectation values. In the future, even if area laws are proved for ground states of 2D gapped systems, the computational complexity of these systems remains unclear.
arXiv commentv2: conference version; v3: journal version with improved presentation (thanks to the reviewers' suggestions). 20-minute video presentation: https://youtu.be/CKwt_pqLOVM
References in corpus (60)
- Entanglement Entropy and Quantum Field Theory
- Area laws for the entanglement entropy - a review
- Entanglement in quantum critical phenomena
- Efficient classical simulation of slightly entangled quantum computations
- From Quantum Chaos and Eigenstate Thermalization to Statistical Mechanics and Thermodynamics
- Solving the Quantum Many-Body Problem with Artificial Neural Networks
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- Geometric and Renormalized Entropy in Conformal Field Theory
- Entanglement entropy and conformal field theory
- Average Entropy of a Subsystem
- Evolution of Entanglement Entropy in One-Dimensional Systems
- Entanglement renormalization
- An Area Law for One Dimensional Quantum Systems
- Unbounded growth of entanglement in models of many-body localization
- Many body localization in Heisenberg XXZ magnet in a random field
- A class of quantum many-body states that can be efficiently simulated
- Matrix product states represent ground states faithfully
- Ballistic spreading of entanglement in a diffusive nonintegrable system
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Entropy scaling and simulability by Matrix Product States
- Quantum Entanglement in Neural Network States
- Renormalization and tensor product states in spin chains and lattices
- Aspects of generic entanglement
- Entanglement entropy of random quantum critical points in one dimension
- Efficient Representation of Quantum Many-body States with Deep Neural Networks
- The computational complexity of PEPS
- A Sharp Fannes-type Inequality for the von Neumann Entropy
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Equivalence of restricted Boltzmann machines and tensor network states
- The power of quantum systems on a line
- Entanglement Entropy of Eigenstates of Quantum Chaotic Hamiltonians
- Hamiltonian complexity
- Subsystem ETH
- Canonical Typicality of Energy Eigenstates of an Isolated Quantum System
- Sub-ballistic growth of Rényi entropies due to diffusion
- Quantum Hamiltonian Complexity
- Quantum NP - A Survey
- Continuity bounds for entanglement
- Renyi Entropy of Chaotic Eigenstates
- Quantum Entanglement of the Sachdev-Ye-Kitaev Models
- Stochastic Error Cancellation in Analog Quantum Simulation
- Neural network representation of tensor network and chiral states
- Universal eigenstate entanglement of chaotic local Hamiltonians
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
- Eigenstate entanglement in the Sachdev-Ye-Kitaev model
- Excited-state entanglement and thermal mutual information in random spin chains
- Contracting projected entangled pair states is average-case hard
- Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians
- The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
- Area law in one dimension: Degenerate ground states and Renyi entanglement entropy
- A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
- Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
- Dynamics of Renyi entanglement entropy in local quantum circuits with charge conservation
- Computing energy density in one dimension
- Dynamics of Rényi entanglement entropy in diffusive qudit systems
- A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
- Entanglement dynamics in critical random quantum Ising chain with perturbations
- Approximating local properties by tensor network states with constant bond dimension
- Area laws and efficient descriptions of quantum many-body states
- A simple efficient algorithm in frustration-free one-dimensional gapped systems