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

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to