CSDM - The Detectability Lemma and Quantum Gap Amplification

The Detectability Lemma and Quantum Gap Amplification - Itai Arad

Itai Arad
Hebrew University of Jerusalem
October 5, 2009

Constraint Satisfaction Problems appear everywhere. The study of their quantum analogues (in which the constraints no longer commute), has become a lively area of study, and various recent results provide interesting insights into quantum physics and quantum information. Quantum correlations make quantum analogies of classical results non-trivial, and sometimes simply wrong. One of the main open questions in the area is whether or not there is a quantum PCP theorem. An answer to this question will most likely have interesting implications regardless of whether it is negative or positive.

Following a gentle introduction to this subfield, I will slowly focus on our recent result [Aharonov, Arad, Landau, Vazirani, STOC 2009] in which a crucial ingredient of Dinur's PCP proof, the gap amplification lemma, is generalized to the quantum world. The main part of the proof is a new general lemma called "the detectability lemma". Its proof reveals some intrinsic structure of the vector space of n qubits governed by local constraints, which is captured in an "exponential decay" to the commuting case. All this is formalized using a novel decomposition of the vector space called the XY decomposition. If time permits, I will talk about other applications of the detectability lemma, including a quantum version of Impagliazzo-Zuckerman RP amplification, and more.