[quantum-info] Colloquium Institute for Quantum Computing Monday, 11 November

[Matthew Fries]

Colloquium

Institute for Quantum Computing

Monday, 11 November 2013 at 2:30PM

QNC 0101

The quantum PCP conjecture

Dorit Aharonov

The Hebrew University of Jerusalem

Perhaps the most important result of the last quarter of a century in theoretical computer science is the celebrated PCP theorem, which states the following remarkable fact: a mathematical proof can be converted into a form which enables checking it by testing only 3 (!) randomly chosen bits. This surprising theorem has had many applications. Its quantum analogue has so far resisted resolution; the problem bares rich connections to a variety of topics such as the nature of multiparticle entanglement, quantum error correcting codes, interactive proofs, robustness of quantum systems, and more. I will describe some of the exciting progress achieved over the past few years, and mainly try to explain a) why it is interesting b) why it is difficult.