Suppose given the description of a physical system that is made of a very large number of constitutents (such as photons, or atoms), and such that the physical interaction between these constitutents are *local*. Such a system will eventually, if perfectly isolated from its environment and cooled down to zero temperature, reach its* ground state*, which is the most stable state of its constituents -- the one with the lowest energy. Using language from computer science, the ground state is the joint state of all constituents of the system which satisfies the most constraints, among all physically possible states. This analogy creates a bridge between condensed-matter physics, which studies properties of ground states, and complexity theory, which studies constraint satisfaction problems. The bridge allows computer scientists, including myself, to bring insights from their discipline on physical questions: What is the complexity of predicting simple properties of the ground state, such as its energy? How does the locality of the physical constraints (forces) affect entanglement in the ground state? Do ground states have more efficient classical representations than general quantum states? These questions form the basis for the field of *Hamiltonian complexity*.

My research in this area is motivated by the *quantum PCP conjecture*, about which I wrote a research survey (see also this blog post). This conjecture was formulated more than two decades ago in analogy with the famous (classical) PCP theorem. The PCP theorem states that local constraint satisfaction problems such as 3SAT or MAXCUT exhibit hardness of approximation: not only is the optimization problem (e.g. find an assignment satisfying the largest number of contraints) NP-hard, but so is its approximation variant (e.g. find an assignment that satisfies at least 90% of the maximum number of constraints simultaneously satisfiable).

The quantum PCP conjecture applies to "quantum constraint satisfaction problems" that model the physical scenario described abobe. Formally, the problem is as follows: given a description of a local Hamiltonian H (physically, a description of forces acting on an n-particle system; mathematically, a weighted sum of local projectors each of which projects out an “invalid subspace,” on, say, a subset of 5 out of n qubits), return an approximation to the smallest eigenvalue (the minimal energy) of H. Kitaev showed that returning an inverse-polynomial approximation is a QMA-complete problem, a result sometimes qualified of “quantum Cook-Levin theorem.” The quantum PCP conjecture is the statement that constant-factor approximations remain QMA-hard.

My work in Hamiltonian complexity applies to a physically motivated restriction on the problem: what if the Hamiltonian is promised to have a spectral gap between its smallest and second-smallest eigenvalues? This restriction holds for any classical Hamiltonian (the gap is 1), as well

as of many physical systems of interest. In a sequence of papers we devekoped a classical algorithm for efficiently finding a succinct classical representation of the ground state of a gapped

Hamiltonian in one dimension (the particles are arranged on a line, and constraints are nearest-neighbor; classically, this corresponds to the case of 2SAT, which is efficiently solvable by dynamic programming).

### Further reading

For a general introduction to Hamiltonian complexity, I recommend the survey by Gharibian et al. With Aharonov and Arad we wrote a more focused survey around the quantum PCP conjecture. In a first paper wih Landau and Vazirani we gave a polynomial-time algorithm for frustration-free systems, which we later extended to frustrated and degenerate case later; the latter work includes the proof of new area laws. Together with Roberts and Motrunich we gave a numerical implementation of this algorithm and demonstrated good performance compared to RRG. Subsequent works support our initial findings and I believe that there remains a lot of potential for extending, refining and using this algorith.