Ground States of Local Hamiltonians and Quantum PCPs

The PI plans to apply the grant money towards a one-year visit to UC-Berkeley, where he intends to closely collaborate with Umesh Vazirani and his colleagues and students on two fundamental issues about ground states of local Hamiltonians - whether they satisfy the quantum analog of the PCP theorem, and whether they satisfy an area law. To gain the needed insight into the ground states of local Hamiltonians, the PI will employ his knowledge of classical PCP theory, a deep theory in computer science that he helped develop, and couple it with the expertise of the colleagues in Berkeley on quantum information theory.

A quantum analog of the PCP theorem would say something profound about quantum systems. Besides its implications in quantum information theory, it would also have more direct implication in physics, such as the realization, that quantum systems retain their exponential complexity at high temperature. In addition, an area law would explain the often localized behavior of wave functions for many-body systems.

If the PI and colleagues are successful in their efforts, this would be a development akin to the invention of classical PCP theory, that should attract a number of computational complexity theorists, and connect them with quantum computing. A deeper understanding of the behavior of ground states of local Hamiltonians should effect disciplines ranging from quantum chemistry to black hole physics.