A Polynomial Time Algorithm for the Ground State of 1-D Gapped Local Hamiltonians

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.