License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.4
URN: urn:nbn:de:0030-drops-180569
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18056/
Vidick, Thomas
Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk)
Abstract
The study of multiprover interactive proof systems, of locally testable codes, and of property testing are deeply linked, conceptually if not formally, through their role in the proof of the PCP theorem in complexity theory. Recently there has been substantial progress on an analogous research programme in quantum complexity theory. Two years ago we characterized the power of multiprover interactive proof systems with provers sharing entanglement, showing that MIP^* = RE [Ji et al., 2020], a hugely surprising increase in power from the classical result MIP = NEXP of [Babai et al., 1991]. The following year Panteleev and Kalachev gave the first construction of quantum low-density parity-check codes (QLDPC) [Panteleev and Kalachev, 2022], thus marking a major step towards the possible realization of good quantum locally testable codes - the classical analogue of which was only constructed quite recently [Dinur et al., 2022]. And finally, less than a year ago Anshu, Breuckmann and Nirkhe used facts evidenced in the construction of good decoders for the new QLDPC codes to resolve the NLTS conjecture [Anshu et al., 2022], widely viewed as a crucial step on the way to a possible quantum PCP theorem.
In the talk I will survey these results, making an effort to motivate and present them to the non-expert. I will explain the connections between them and point to where, in my opinion, our understanding is currently lacking. Along the way I will highlight a number of open problems whose resolution could lead to further progress on one of the most important research programmes in quantum complexity theory.
BibTeX - Entry
@InProceedings{vidick:LIPIcs.ICALP.2023.4,
author = {Vidick, Thomas},
title = {{Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {4:1--4:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18056},
URN = {urn:nbn:de:0030-drops-180569},
doi = {10.4230/LIPIcs.ICALP.2023.4},
annote = {Keywords: quantum interactive proofs, quantum codes}
}
|
Keywords: |
|
quantum interactive proofs, quantum codes |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
