Theory Seminar
Highdegree graphs cannot be used for a quantum PCP
Aram Harrow
MIT 

Friday, April 12, 2013
10:00am  11:00am 411 West Hall


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.
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. 
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.
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. 
Additional Information
Sponsor: EECS
Open to: Public


