High-degree graphs cannot be used for a quantum PCP

One variant of the quantum PCP conjecture states that it is QMA-complete to estimate the ground-state energy of a Hamiltonian with n qubits up to an error proportional to the total number of interacting pairs of qubits in the system. Since this generalizes classical 2-CSPs, this problem is at least NP-hard. We prove that the ground-state energy of 2-local Hamiltonians on D-regular graphs can be approximated in NP with additive error inverse-polynomial in D. Thus, if a quantum PCP theorem were to be true, it would need to make use of constant-degree graphs. The proof is based on information-theoretic techniques introduced by Raghavendra and Tan in arXiv:1110.1064.

Similar techniques also yields a PTAS for Hamiltonians on dense hypergraphs, planar graphs and highly expanding graphs. This last result in fact makes use of an application of the Lasserre SDP hierarchy to the quantum Hamiltonian problem, which generalizes its application to classical CSPs.

Based on joint work with Fernando Brandao.
Aram Harrow grew up in E. Lansing, MI, before attending MIT for his undergraduate (math and physics) and graduate (physics) degrees. He then served as a lecturer in the math and CS departments of the University of Bristol for five years, and as a research assistant professor in the University of Washington CS department for two years. In 2013, he joined the MIT physics department as an assistant professor.

His research focuses on quantum information theory, quantum algorithms and quantum complexity, and often seeks to make connections to other areas of math, physics and theoretical computer science.