Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1309.7495

The Quantum PCP Conjecture

Dorit Aharonov, Itai Arad, Thomas Vidick

Published Sep 28, 2013• 66 citations
arXivHTMLPDF

Abstract

The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics, the global nature of entanglement and its topological properties, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.

DOI
10.48550/arxiv.1309.7495

Related papers

Guest column: the quantum PCP conjecture

Dorit Aharonov, Itai Arad, Thomas Vidick

The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics and multipartite entanglement, topology and the so-called phenomenon of topological order, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.

ACM SIGACT News•Jun 3, 2013•137 citations

The status of the quantum PCP conjecture (games version)

Anand Natarajan, Chinmay Nirkhe

In classical complexity theory, the two definitions of probabilistically checkable proofs -- the constraint satisfaction and the nonlocal games version -- are computationally equal in power. In the quantum setting, the situation is far less clear. The result MIP* = RE of Ji et. al. (arXiv:2001.04383) and refinements by Natarajan and Zhang (arXiv:2302.04322) show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE, including undecidable problems like the halting problem. These results show that any connection between the "constraint satisfaction" or "Hamiltonian" quantum PCP conjecture and nonlocal games must involve restricting the players in the game to be computationally efficient. This note contains two main results: (1) we give a "quantum games PCP for AM" in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick (arXiv:1710.03062) which invalidates their claim to have constructed a quantum games PCP for a QMA-complete problem. In surveying the obstacles remaining towards a quantum games PCP for QMA, we highlight the importance and challenge of understanding gap amplification for Hamiltonians even when locality is replaced by much weaker constraints, such as bounds on the "Pauli spectrum" of the Hamiltonian. We hope these questions will motivate progress towards new "baby versions" of Hamiltonian quantum PCP conjecture.

arXiv:2403.13084•Mar 19, 2024•12 citations

Quantum Proofs for Classical Theorems

Andrew Drucker, Ronald de Wolf

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in diverse classical (non-quantum) areas, such as coding theory, communication complexity, and polynomial approximations. In this paper we survey these results and the quantum toolbox they use.

arXiv:0910.3376•Theory of Computing•Jan 1, 2011•49 citations

Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk)

Thomas Vidick

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.

Leibniz international proceedings in informatics•Jan 1, 2023•1 citation

Mathematical etudes on quantum computation

Alexei Bocharov

Recent expansion in the field of quantum computing has been so dramatic that even a cursory review of the field easily spans over dozens of pages. Rather than attempting an overview of quantum computing the purpose of this paper is to attract interest of professional mathematicians through a handful of succinct etudes each focusing on a particular mathematically rich aspect of quantum. By focusing on such aspects, we strive to highlight research challenges that are likely to require full power of modern mathematics for their resolution.

Contemporary mathematics - American Mathematical Society•Jan 1, 2023•0 citations

Quantum complexity theory tools, goals and challenges

Jozef Gruska

Analysis of methods and results of quantum complexity theory and their contribution for better understanding of main theoretical and practical problems in quantum information processing.

•Jan 1, 2005•0 citations
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics, the global nature of entanglement and its topological properties, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics and multipartite entanglement, topology and the so-called phenomenon of topological order, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.
In classical complexity theory, the two definitions of probabilistically checkable proofs -- the constraint satisfaction and the nonlocal games version -- are computationally equal in power. In the quantum setting, the situation is far less clear. The result MIP* = RE of Ji et. al. (arXiv:2001.04383) and refinements by Natarajan and Zhang (arXiv:2302.04322) show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE, including undecidable problems like the halting problem. These results show that any connection between the "constraint satisfaction" or "Hamiltonian" quantum PCP conjecture and nonlocal games must involve restricting the players in the game to be computationally efficient. This note contains two main results: (1) we give a "quantum games PCP for AM" in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick (arXiv:1710.03062) which invalidates their claim to have constructed a quantum games PCP for a QMA-complete problem. In surveying the obstacles remaining towards a quantum games PCP for QMA, we highlight the importance and challenge of understanding gap amplification for Hamiltonians even when locality is replaced by much weaker constraints, such as bounds on the "Pauli spectrum" of the Hamiltonian. We hope these questions will motivate progress towards new "baby versions" of Hamiltonian quantum PCP conjecture.
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.
Recent expansion in the field of quantum computing has been so dramatic that even a cursory review of the field easily spans over dozens of pages. Rather than attempting an overview of quantum computing the purpose of this paper is to attract interest of professional mathematicians through a handful of succinct etudes each focusing on a particular mathematically rich aspect of quantum. By focusing on such aspects, we strive to highlight research challenges that are likely to require full power of modern mathematics for their resolution.