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.

The structure of ground states of local Hamiltonians is one of the fundamental questions in condensed matter physics and quantum complexity theory, and is the quantum analog of constraint satisfaction problems (CSPs). Here we will present a surprising result: a classical polynomial time algorithm for approximating ground states of 1D gapped Hamiltonians. The algorithm builds on concepts introduced in recent proofs of 1D area laws (specifically approximate ground state projectors (AGSPs)) and convex programming. Based on joint work with Umesh Vazirani and Thomas Vidick.

Under a certain set of conditions collectively known as "local topological order", the low energy spectrum of a system is robust to local perturbations. This has the consequence that quantum information encoded in the degenerate ground state of such a system is stable at zero temperature. On the other hand, the existence of a macroscopic energy barrier between ground states imply that information encoded in the ground state is robust against thermal fluctuations. Here, we demonstrate that for local commuting projector codes, local topological order prohibits the existence of an energy barrier, which shows a tradeoff between robustness to quantum and thermal fluctuations. I will also discuss relations to area law and quantum Markov networks.

Relativistic quantum field theory describes all of the fundamental interactions in Nature, with the possible exception of gravity, I will describe and analyze a quantum algorithm for simulating real-time evolution in an interacting massive scalar quantum field theory in four or fewer spacetime dimensions. The run time of the algorithm scales polynomially in the particle number, the energy, and the desired precision. Hence the algorithm achieves an exponential speedup relative to the best existing classical algorithms. This result supports the conjecture that all physical processes in Nature can be simulated efficiently using a universal quantum computer. Based on joint work with Stephen Jordan and Keith Lee.