BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Tutorial - Quantum PCP Vidick, Thomas


Two equivalent formulations of the classical PCP theorem, hardness of approximation for constraint satisfaction problem and hardness of approximation for the value of two-player games, lead to two distinct formulations of a quantum PCP conjecture. The first conjecture, the "Hamiltonian QPCP", comes out of condensed-matter physics. The second conjecture, the "games QPCP", is closely tied to questions from foundations of quantum mechanics and has applications to quantum cryptography. In the first part of the tutorial I will motivate and formulate the two conjectures. I will not assume background in quantum information, and keep the technical aspects light while still aiming to say enough to provide concrete intuition. In the second part of the tutorial I will dive deeper into the "games PCP" conjecture, on which there has been more progress recently. I will describe the issues that arise when considering classical techniques such as the Hadamard code or low-degree tests in the quantum settings. Time allowing, these investigations will bring us to a new, group-theoretic perspective on the classical tests. For background reading, see the survey arXiv:1309.7495, the more recent (and shorter) lecture notes, the (even shorter) blog post, or the (longer...) paper arXiv:1801.03821.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International