Date: Friday, April 12, 2013
Location: 411 West Hall (10:00 AM to 11:00 AM)
Title: High-degree graphs cannot be used for a quantum PCP
Abstract: 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.
Speaker: Aram Harrow
Institution: MIT
Event Organizer: Yaoyun Shi shiyy
|
