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.
v2: 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 (41)
- 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
- 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
- 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
- Aspects of generic entanglement
- Efficient Representation of Quantum Many-body States with Deep Neural Networks
- A Sharp Fannes-type Inequality for the von Neumann Entropy
- 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
- 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
- Renyi Entropy of Chaotic Eigenstates
- Quantum Entanglement of the Sachdev-Ye-Kitaev Models
- Stochastic Error Cancellation in Analog Quantum Simulation
- Universal eigenstate entanglement of chaotic local Hamiltonians
- Neural network representation of tensor network and chiral states
- 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
- Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
- Computing energy density in one dimension
- Dynamics of Rényi entanglement entropy in diffusive qudit systems
- Dynamics of Renyi entanglement entropy in local quantum circuits with charge conservation
- 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
- A simple efficient algorithm in frustration-free one-dimensional gapped systems
- Area laws and efficient descriptions of quantum many-body states