RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

The computational complexity of calculating ground state energies to very high precision

April 1, 2016 - 12:10pm
Dr. Cedric Lin

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.

PSC 2136
College Park, MD 20742