- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Tutorial - Quantum PCP
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Tutorial - Quantum PCP Vidick, Thomas
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. 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 Metadata
| Title |
Tutorial - Quantum PCP
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2018-08-15T09:09
|
| 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.
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.
|
| Extent |
93.0
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: California Institute of Technology
|
| Series | |
| Date Available |
2019-03-28
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0377633
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International