COMPUTER SCIENCE/DISCRETE MATH I | |

Topic: | The Detectability Lemma and Quantum Gap Amplification |

Speaker: | Itai Arad |

Affiliation: | Hebrew University of Jerusalem |

Date: | Monday, October 5 |

Time/Room: | 11:15am - 12:15pm/S-101 |

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.