Theory SeminarHighdegree graphs cannot be used for a quantum PCPAram HarrowMIT 
Friday, April 12, 2013 10:00am  11:00am 411 West Hall Add to Google Calendar 
About the EventOne variant of the quantum PCP conjecture states that it is QMAcomplete to estimate the groundstate 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 2CSPs, this problem is at least NPhard. We prove that the groundstate energy of 2local Hamiltonians on Dregular graphs can be approximated in NP with additive error inversepolynomial in D. Thus, if a quantum PCP theorem were to be true, it would need to make use of constantdegree graphs. The proof is based on informationtheoretic techniques introduced by Raghavendra and Tan in arXiv:1110.1064.

BiographyAram 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.

Additional InformationSponsor: EECS Open to: Public 