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 http://users.cms.caltech.edu/~vidick/notes/ucsd/ucsd_mip.pdf, the (even shorter) blog post https://mycqstate.wordpress.com/2014/10/31/quantum-pcp-conjectures/, or the (longer...) paper arXiv:1801.03821.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International