The computational complexity of calculating ground state energies to very high precision
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.
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!