
Abstract
Project Summary with Interim Results
What does nature allow us to compute and why are some physics problems computationally difficult? Precise control over scalable fully quantummechanical computers would let us deal with some problems that are conventionally inaccessible. On the other hand, insights from physics allowed us to discover deep results about complexity in theoretical computer science as well as resulted in practical algorithms (e.g. annealing). Our project brings together questions from physics and computer science, aiming to discover and understand new physics of local Hamiltonian systems and their complexity. We divide our research efforts to develop mathematical descriptions, groundbreaking conjectures, and effective tools into three areas: ground states/optimization, area laws, and approximations.
Local models: their ground states and dynamics. Our first focus are the ground states and dynamics of quantum manybody systems with local interactions. We will investigate the true nature and structure of quantum states appearing in these quantum models. The goal is to discover and understand the computational hardness, or to demonstrate simplicity of simulation for these systems.
Area laws: simplified descriptions of reality. The second approach explores the area law for ground states of gapped, local Hamiltonians, where the amount of entanglement grows like the boundary of a subsystem, not like the enclosed volume. This motivates ansatzes that enable new numerical approaches, as well as gives us a better understanding of the evolution of excitations and the distribution of correlations in such systems. Our aim is to develop an area law for general geometries, and then to utilize it as a computational tool.
Powerful approximations: towards quantum PCP. Our third task is to build or tear down the evidence for the quantum PCP conjecture (qPCP), a powerful claim about possible approximations for quantum many body systems. We will investigate whether local approximations destroy the rich structure of our models. The focus is on unraveling the complex behavior of entanglement in the presence of noise, and on possible local tests of quantumly checkable proofs (ground states) in quantum complexity.
In the first year of the project, we made contributions to all three of the proposal areas. First, we have discovered and analyzed a family of translationally invariant spin chains with suprising entanglement properties. These models are related to classical computational models, and open a new way of looking at the area law. Second, we formulated new questions about the translationally invariant reduced density matrix consistency problem. Third, developing the theory of quantum clocks for computation and using an analysis of certain quantum walks, we have polynomially improved a precision requirement for the QMAcomplete Local Hamiltonian problem. Last, but not least, we have opened and closed many research avenues, among others investigating possible inplace amplification for interactive quantum protocols, and looking for degreereduction gadgets, preparing ground for the following years of the project.