Product-state Approximations to Quantum Ground States

Abstract

The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. First, we show the existence of a good product-state approximation for the ground-state energy of 2-local Hamiltonians with one or more of the following properties: (1) high degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some partition into small pieces. The approximation based on degree is a surprising difference between quantum Hamiltonians and classical CSPs (constraint satisfaction problems), since in the classical setting, higher degree is usually associated with harder CSPs. The approximation based on low entanglement, in turn, was previously known only in the regime where the entanglement was close to zero. Since the existence of a low-energy product state can be checked in NP, the result implies that any Hamiltonian used for a quantum PCP theorem should have: (1) constant degree, (2) constant expansion, (3) a "volume law" for entanglement with respect to any partition into small parts. Second, we show that in several cases, good product-state approximations not only exist, but can be found in polynomial time: (1) 2-local Hamiltonians on any planar graph, solving an open problem of Bansal, Bravyi, and Terhal, (2) dense k-local Hamiltonians for any constant k, solving an open problem of Gharibian and Kempe, and (3) 2-local Hamiltonians on graphs with low threshold rank, via a quantum generalization of a recent result of Barak, Raghavendra and Steurer. Our work introduces two new tools which may be of independent interest. First, we prove a new quantum version of the de Finetti theorem which does not require the usual assumption of symmetry. Second, we describe a way to analyze the application of the Lasserre/Parrilo SDP hierarchy to local quantum Hamiltonians.

44 pages. v2: proof of thm 6 corrected

References in corpus (4)

• The power of quantum systems on a line
• One-and-a-half quantum de Finetti theorems
• Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
• A simple proof of monogamy of entanglement

Cited by in corpus (18)

• Generic emergence of classical features in quantum Darwinism
• Universal recovery map for approximate Markov chains
• NLTS Hamiltonians from good quantum codes
• The Fidelity of Recovery is Multiplicative
• Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• On the complexity of quantum partition functions
• Optimizing sparse fermionic Hamiltonians
• Towards local testability for quantum coding
• Entropy Constraints for Ground Energy Optimization
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators
• The Need for Structure in Quantum LDPC Codes
• Monogamy of highly symmetric states
• Sample optimal tomography of quantum Markov chains
• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
• Expanding the reach of quantum optimization with fermionic embeddings
• The Interplay between Quantum Contextuality and Wigner Negativity