High-degree graphs cannot be used for a quantum PCP
Friday, April 12, 2013|
10:00am - 11:00am
411 West Hall
Add to Google Calendar
About the Event
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.
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.
Open to: Public