We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Tutorial - Quantum PCP

00:00

Formale Metadaten

Titel
Tutorial - Quantum PCP
Serientitel
Anzahl der Teile
17
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
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.