Local Hamiltonians Whose Ground States are Hard to Approximate

Abstract

Ground states of local Hamiltonians can be generally highly entangled: any quantum circuit that generates them (even approximately) must be sufficiently deep to allow coupling (entanglement) between any pair of qubits. Until now this property was not known to be "robust" - the marginals of such states to a subset of the qubits containing all but a small constant fraction of them may be only locally entangled, and hence approximable by shallow quantum circuits. In this work we construct a family of 16-local Hamiltonians for which any 1-10^{-9} fraction of qubits of any ground state must be highly entangled. This provides evidence that quantum entanglement is not very fragile, and perhaps our intuition about its instability is an artifact of considering local Hamiltonians which are not only local but spatially local. Formally, it provides positive evidence for two wide-open conjectures in condensed-matter physics and quantum complexity theory which are the qLDPC conjecture, positing the existence of "good" quantum LDPC codes, and the NLTS conjecture due to Freedman and Hastings positing the existence of local Hamiltonians in which any low-energy state is highly-entangled. Our Hamiltonian is based on applying the hypergraph product by Tillich and Zemor to a classical locally testable code. A key tool in our proof is a new lower bound on the vertex expansion of the output of low-depth quantum circuits, which may be of independent interest.

v3: 41 pages. Main result changed from NLTS to a different theorem which we call NLETS, due to a bug in the corresponding theorem of the previous version. The construction and techniques are the same, with some additions

References in corpus (12)

• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Stochastic Error Cancellation in Analog Quantum Simulation
• Quantum Expander Codes
• Locality in Quantum Systems
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Commutative version of the k-local Hamiltonian problem and common eigenspace problem
• Quantum Codes from High-Dimensional Manifolds
• On the informational completeness of local observables
• Homological connectivity of random k-dimensional complexes
• The Detectability Lemma and Quantum Gap Amplification
• Local Hamiltonians with Approximation-Robust Entanglement

Cited by in corpus (32)

• Quantum advantage with shallow circuits
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Quantum advantage with noisy shallow circuits in 3D
• The Quantum Wasserstein Distance of Order 1
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Classical algorithms for quantum mean values
• Single-copy entanglement detection
• Local Hamiltonians Whose Ground States are Hard to Approximate
• NLTS Hamiltonians from good quantum codes
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Quantum verification and estimation with few copies
• Improved local spectral gap thresholds for lattices of finite dimension
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Variational wavefunctions for Sachdev-Ye-Kitaev models
• Towards local testability for quantum coding
• Quantum memory at nonzero temperature in a thermodynamically trivial system
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• The Wasserstein distance of order 1 for quantum spin systems on infinite lattices
• The Need for Structure in Quantum LDPC Codes
• Order $p$ quantum Wasserstein distances from couplings
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• Combinatorial NLTS From the Overlap Gap Property
• Approximate Quantum Codes From Long Wormholes
• Approximate low-weight check codes and circuit lower bounds for noisy ground states
• A Quantum inspired proof of $P^{\#P}\subseteq IP$
• Quantum Locally Testable Code with Constant Soundness
• Limits of Short-Time Evolution of Local Hamiltonians
• Effective Distance of Higher Dimensional HGPs and Weight-Reduced Quantum LDPC Codes