Computer Science/Discrete Mathematics Seminar I

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.