Published:
[Erscheinungsort nicht ermittelbar]: Banff International Research Station (BIRS) for Mathematical Innovation and Discovery, 2018
Published in:Analytic techniques in Theoretical Computer Science (18w5197) ; (Jan. 2018)
Extent:
1 Online-Ressource (636 MB, 01:33:42:03)
Language:
English
DOI:
10.5446/59352
Identifier:
Origination:
Footnote:
Audiovisuelles Material
Description:
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