FellowDaniel Nagaj
Project NameLocal Hamiltonians in Quantum Complexity
Host organisationInstitute of Physics
Duration of the project01.09.2015 - 31.12.2018

What does nature allow us to compute and why are some physics problems computationally more difficult than others? These questions on the boundary of theoretical physics and computer science have their root at the microscopic level. Local interactions in a quantum many-body system give rise to ground states that are interesting from three viewpoints. First, their relationship to optimization problems, second, their non-classical correlations, and third, the possibilities of approximation. In this project, our first and basic goal is the understanding of the computational hardness (or simplicity) of simulation for these systems, developing quantum information theory for Hamiltonian systems. Second, we will utilize and generalize the area law for ground states of gapped local Hamiltonians as a computational tool, aiming at applications in many-body physics numerical methods. Third, we will explore the robustness of these results in presence of noise and various approximations, bringing light to the hottest topic in quantum complexity theory: the quantum PCP conjecture.

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 quantum-mechanical 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 many-body 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 conjec­tu­re (qPCP), a powerful claim about possible approximations for quan­tum 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 QMA-complete Local Hamiltonian problem. Last, but not least, we have opened and closed many research avenues, among others investigating possible in-place amplification for interactive quantum protocols, and looking for degree-reduction gadgets, preparing ground for the following years of the project.