Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum PCPs

The local Hamiltonian problem consists in estimating the groundstate energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalisation of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean groundstate energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. In this talk I will present new approximation guarantees for solving the local Hamiltonian problem within constant extensive error.

First I'll show how to obtain in NP a proof of small mean groundstate energy that depends on two parameters:

1. The degree of the constraint graph: Here I'll show that the problem is in NP for Hamiltonians on high degree graphs, with a product state giving an approximation to the groundstate energy of error inverse polynomial in the degree of the graph. In contrast, the PCP theorem holds true with error independent of the degree of the constraint graph of the CSP. This result also gives a rigorous justification to the folklore in condensed matter physics that mean field becomes exact once the dimension of the lattice grows.
2. The average entanglement in the ground state of the Hamiltonian: Here we find that the problem is also in NP for Hamiltonians that satisfy a subvolume law for the entanglement entropy. This gives a new connection between the amount of entanglement in the groundstate of a local Hamiltonian and its computational complexity.

The approximation guarantees obtained give new limitations on which type of Hamiltonians one could expect to base a possible quantum analogue of the PCP theorem.

Second I'll briefly present new polynomial-time algorithms for approximating the mean groundstate energy of three classes of Hamiltonians: (i) 2-local Hamiltonians on any planar graph, solving an open problem of Bansal, Bravyi, and Terhal; (ii) dense k-local Hamiltonians for any constant k, solving an open problem of Gharibian and Kempe; and (iii) Hamiltonians on low-threshold graphs, building on work of Barak, Raghavendra, and Steurer.

The main idea behind the results is an information-theoretic argument inspired by recent work on the convergence of the Lasserre hierarchy for CSPs. Based on joint work with Aram Harrow.