Free lunch served at 12:00
Computational complexity theory studies the classification of computational problems according to the resources required to solve them. An important problem in quantum complexity theory is the local Hamiltonian problem - given a Hamiltonian composed of local terms, determine its ground state energy up to polynomial precision.
We characterize the complexity of a variant local Hamiltonian problem where exponential precision, instead of polynomial precision, is required. In particular, this problem exactly captures the difficulty of problems solvable in a reasonable amount of memory (but with no other constraints). Our result gives some evidence that projected entangled pair states (PEPS) are less computationally useful than general ground states.
No knowledge of complexity theory will be assumed. Based on joint work with Bill Fefferman.
