Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
1QuSoft, University of Amsterdam & Quantinuum, Partnership House, Carlisle Place, London
2QuSoft & CWI, Amsterdam, the Netherlands
| Published: | 2025-07-11, volume 9, page 1791 |
| Editor: | Dax Enshan Koh |
| Eprint: | arXiv:2403.04841v3 |
| Doi: | https://doi.org/10.22331/q-2025-07-11-1791 |
| Citation: | Quantum 9, 1791 (2025). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: (i) Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply uniformly at random from a subset of all possible index combinations, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). (ii) If the $q$-local Hamiltonian problem with constant promise gap can be solved in $\mathsf{QCMA}$, then $\mathsf{QPCP}[q] \subseteq \mathsf{QCMA}$ for any $q \in O(1)$. (iii) If $\mathsf{QMA}(k)$ has a quantum PCP for any $k \leq \text{poly}(n)$, then $\mathsf{QMA}(2) = \mathsf{QMA}$, connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exist (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.
Popular summary
Naturally, researchers have asked whether an analogous theorem holds in the quantum setting. In its hardness-of-approximation formulation, the quantum PCP conjecture posits that it is QMA-hard to decide whether a local Hamiltonian has low or high ground state energy, where the gap between the two cases is a constant fraction of the Hamiltonian’s operator norm. While there has been progress offering evidence both for and against the conjecture, its resolution remains elusive.
The proof-checking formulation of the quantum PCP conjecture states that one can solve any promise problem in QMA by using a quantum verifier which only accesses a constant number of qubits from a quantum proof. This formulation has received far less attention, which has left many basic questions unresolved since the conjecture was first proposed. For example: how robust are definitions of quantum PCPs under subtle changes, e.g., does it matter how we decide which part of the proof we are going to check? Does adaptivity add any power? Are there non-equivalent variations of quantum PCPs, similar to the many natural variations of QMA?
In this work, we resolve many of these foundational questions. Our results include both new insights and formal proofs of what we believe to be "folklore knowledge"’. Given the renewed interest in the quantum PCP conjecture, we hope this work provides a useful starting point for further investigation.
► BibTeX data
► References
[1] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, page 151–158, 1971. ISBN 9781450374644.
https://doi.org/10.1145/800157.805047
[2] Leonid A. Levin. Universal sequential search problems. Problemy peredachi informatsii, 9 (3): 115–116, 1973.
[3] Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. Classical and quantum computation. American Mathematical Society, 2002. ISBN 978-0-8218-3229-5.
[4] Sevag Gharibian. Guest Column: The 7 faces of quantum NP. SIGACT News, 54 (4): 54–91, January 2024. ISSN 0163-5700. arXiv: 2310.18010.
https://doi.org/10.1145/3639528.3639535
arXiv:2310.18010
[5] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. Journal of the ACM, 45 (3): 501–555, May 1998. ISSN 0004-5411.
https://doi.org/10.1145/278298.278306
[6] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45 (1): 70–122, January 1998. ISSN 0004-5411.
https://doi.org/10.1145/273865.273901
[7] Irit Dinur. The PCP Theorem by Gap Amplification. Journal of the ACM, 54 (3): 12–es, June 2007. ISSN 0004-5411.
https://doi.org/10.1145/1236457.1236459
[8] Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from Good Quantum Codes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1090–1096, 2023. ISBN 9781450399135. arXiv: 2206.13228.
https://doi.org/10.1145/3564246.3585114
arXiv:2206.13228
[9] Nolan J. Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi. Local Hamiltonians with No Low-Energy Stabilizer States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), volume 266, pages 14:1–14:21, 2023a. ISBN 978-3-95977-283-9. arXiv: 2302.14755.
https://doi.org/10.4230/LIPIcs.TQC.2023.14
arXiv:2302.14755
[10] Eric R. Anschuetz, David Gamarnik, and Bobak Kiani. Combinatorial NLTS From the Overlap Gap Property. Quantum, 8: 1527, November 2024. ISSN 2521-327X. arXiv:2304.00643.
https://doi.org/10.22331/q-2024-11-19-1527
arXiv:2304.00643
[11] Nolan J. Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi. Hamiltonians whose low-energy states require $\Omega (n) $ T gates, 2023b. arXiv: 2310.01347.
arXiv:2310.01347
[12] Yaroslav Herasymenko, Anurag Anshu, Barbara M. Terhal, and Jonas Helsen. Fermionic Hamiltonians without trivial low-energy states. Phys. Rev. A, 109: 052431, May 2024. arXiv: 2307.13730.
https://doi.org/10.1103/PhysRevA.109.052431
arXiv:2307.13730
[13] Nikhil Bansal, Sergey Bravyi, and Barbara M. Terhal. Classical approximation schemes for the ground-state energy of quantum and classical ising spin Hamiltonians on planar graphs. Quantum Information & Computation, 9 (7): 701–720, July 2009. ISSN 1533-7146. arXiv: 0705.1115.
arXiv:0705.1115
https://dl.acm.org/doi/abs/10.5555/2011814.2011826
[14] Fernando G.S.L. Brandao and Aram W. Harrow. Product-state approximations to quantum ground states. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 871–880, 2013a. ISBN 9781450320290. arXiv: 1310.0017.
https://doi.org/10.1145/2488608.2488719
arXiv:1310.0017
[15] Dorit Aharonov and Alex Bredariol Grilo. Stoquastic PCP vs. Randomness. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1000–1023, 2019. arXiv: 1901.05270.
https://doi.org/10.1109/FOCS.2019.00065
arXiv:1901.05270
[16] Sevag Gharibian and François Le Gall. Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 19–32, 2022. ISBN 9781450392648. arXiv: 2111.09079.
https://doi.org/10.1145/3519935.3519991
arXiv:2111.09079
[17] Chris Cade, Marten Folkertsma, and Jordi Weggemans. Complexity of the guided local Hamiltonian problem: improved parameters and extension to excited states, 2022. arXiv: 2207.10097.
arXiv:2207.10097
[18] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. Improved Hardness Results for the Guided Local Hamiltonian Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261, pages 32:1–32:19, 2023. ISBN 978-3-95977-278-5. arXiv: 2207.10250.
https://doi.org/10.4230/LIPIcs.ICALP.2023.32
arXiv:2207.10250
[19] Jordi Weggemans, Marten Folkertsma, and Chris Cade. Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024), volume 310, pages 10:1–10:24, 2024. ISBN 978-3-95977-328-7. arXiv: 2302.11578.
https://doi.org/10.4230/LIPIcs.TQC.2024.10
arXiv:2302.11578
[20] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The detectability lemma and quantum gap amplification. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, page 417–426, 2009. ISBN 9781605585062. arXiv: 0811.3412.
https://doi.org/10.1145/1536414.1536472
arXiv:0811.3412
[21] Alex B. Grilo. Quantum proofs, the local Hamiltonian problem and applications. PhD thesis, Université Sorbonne Paris Cité, April 2018.
[22] Dorit Aharonov and Tomer Naveh. Quantum NP—a survey, October 2002. arXiv: quant-ph/0210077.
arXiv:quant-ph/0210077
[23] Anand Natarajan and Chinmay Nirkhe. The status of the quantum PCP conjecture (games version), 2024. arXiv: 2403.13084.
arXiv:2403.13084
[24] Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, and Quynh T Nguyen. UniqueQMA vs QMA: oracle separation and eigenstate thermalization hypothesis, 2024. arXiv: 2410.23811.
arXiv:2410.23811
[25] Scott Aaronson, DeVon Ingram, and William Kretschmer. The Acrobatics of BQP. In Proceedings of the 37th Computational Complexity Conference (CCC 2022), volume 234 of LIPIcs, pages 20:1–20:17, 2022. 10.4230/LIPIcs.CCC.2022.20. arXiv: 2111.10409.
https://doi.org/10.4230/LIPIcs.CCC.2022.20
arXiv:2111.10409
[26] Aram W. Harrow and Ashley Montanaro. Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization. J. ACM, 60 (1), February 2013. ISSN 0004-5411. arXiv: 1001.0017.
https://doi.org/10.1145/2432622.2432625
arXiv:1001.0017
[27] Yi-Kai Liu, Matthias Christandl, and Frank Verstraete. Quantum Computational Complexity of the $N$-Representability Problem: QMA Complete. Physical review letters, 98: 110503, Mar 2007. arXiv: quant-ph/0609125.
https://doi.org/10.1103/PhysRevLett.98.110503
arXiv:quant-ph/0609125
[28] Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. The power of unentanglement. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 223–236, 2008. arXiv: 0804.0802.
https://doi.org/10.4086/toc.2009.v005a001
arXiv:0804.0802
[29] Salman Beigi. NP vs ${QMA}_{log}(2)$. Quantum Information & Computation, 10 (1): 141–151, 2010. arXiv: 0810.5109.
https://doi.org/10.26421/QIC10.1-2-10
arXiv:0810.5109
[30] Hugue Blier and Alain Tapp. All Languages in NP Have Very Short Quantum Proofs. In 2009 Third International Conference on Quantum, Nano and Micro Technologies, pages 34–37, 2009. arXiv: 0709.0738.
https://doi.org/10.1109/ICQNM.2009.21
arXiv:0709.0738
[31] André Chailloux and Or Sattath. The Complexity of the Separable Hamiltonian Problem. In 2012 IEEE 27th Conference on Computational Complexity, pages 32–41, 2012. arXiv: 1111.5247.
https://doi.org/10.1109/CCC.2012.42
arXiv:1111.5247
[32] Yi-Kai Liu. Consistency of local density matrices is QMA-complete. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, pages 438–449, 2006. arXiv: quant-ph/0604166.
https://doi.org/10.1007/11830924_40
arXiv:quant-ph/0604166
[33] Anne Broadbent and Alex Bredariol Grilo. QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge. SIAM Journal on Computing, 51 (4): 1400–1450, 2022. arXiv: 1911.07782.
https://doi.org/10.1137/21M140729X
arXiv:1911.07782
[34] Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pages 115–128, 2007. arXiv: quant-ph/0604056.
https://doi.org/10.4086/toc.2007.v003a007
arXiv:quant-ph/0604056
[35] Lance Fortnow. The role of relativization in complexity theory. Bulletin of the EATCS, 52: 229–243, 1994.
[36] Sergey Bravyi, David P. DiVincenzo, Daniel Loss, and Barbara M. Terhal. Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions. Physical Review Letters, 101: 070503, August 2008. arXiv: 0803.2686.
https://doi.org/10.1103/PhysRevLett.101.070503
arXiv:0803.2686
[37] Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14 (2): 122–152, 2005. 10.1007/s00037-005-0194-x. arXiv: cs/0506068.
https://doi.org/10.1007/s00037-005-0194-x
arXiv:cs/0506068
[38] Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. SIGACT News, 44 (2): 47–79, June 2013. ISSN 0163-5700. arXiv: 1309.7495.
https://doi.org/10.1145/2491533.2491549
arXiv:1309.7495
[39] Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC '06, page 427–436, 2006. ISBN 1595931341. arXiv: quant-ph/0511096.
https://doi.org/10.1145/1132516.1132579
arXiv:quant-ph/0511096
[40] Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12: 389–434, 2012.
https://doi.org/10.1007/s10208-011-9099-z
[41] Jasper Lee. Lecture 3: Concentration inequalities and mean estimation. Lecture Notes, CSCI 1951-W Sublinear Algorithms for Big Data, Fall 2020, 2020. URL https://cs.brown.edu/courses/csci1951-w/lec/lec%203%20notes.pdf.
https://cs.brown.edu/courses/csci1951-w/lec/lec%203%20notes.pdf
[42] Persi Diaconis and David Freedman. Finite Exchangeable Sequences. The Annals of Probability, pages 745–764, 1980.
https://doi.org/10.1214/aop/1176994663
[43] Renato Renner. Symmetry of large physical systems implies independence of subsystems. Nature Physics, 3 (9): 645–649, 2007. arXiv: quant-ph/0703069.
https://doi.org/10.1038/nphys684
arXiv:quant-ph/0703069
[44] Matthias Christandl, Robert König, Graeme Mitchison, and Renato Renner. One-and-a-half quantum de Finetti theorems. Communications in Mathematical Physics, 273 (2): 473–498, 2007. arXiv: quant-ph/0602130.
https://doi.org/10.1007/s00220-007-0189-3
arXiv:quant-ph/0602130
[45] Fernando GSL Brandao, Matthias Christandl, and Jon Yard. Faithful squashed entanglement. Communications in Mathematical Physics, 306: 805–830, 2011. arXiv: 1010.1750.
https://doi.org/10.1007/s00220-011-1302-1
arXiv:1010.1750
[46] Fernando G.S.L. Brandao and Aram W. Harrow. Quantum de Finetti Theorems under Local Measurements with Applications. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 861–870, 2013b. ISBN 9781450320290. arXiv: 1210.6367.
https://doi.org/10.1145/2488608.2488718
arXiv:1210.6367
[47] Károly Böröczky and Gergely Wintsche. Covering the Sphere by Equal Spherical Balls, pages 235–251. Springer, Berlin, Heidelberg, 2003. ISBN 978-3-642-55566-4.
https://doi.org/10.1007/978-3-642-55566-4_10
[48] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. arXiv: quant-ph/9701001.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001
Cited by
[1] Fernando Granha Jeronimo, Pei Wu, and Itai Leigh, "The QMA(2) UniverseComplexity, Entanglement, and Optimization", ACM SIGACT News 57 1, 64 (2026).
[2] Anand Natarajan and Chinmay Nirkhe, "The status of the quantum PCP conjecture (games version)", arXiv:2403.13084, (2024).
[3] Itai Arad and Miklos Santha, "Quasi-quantum states and the quasi-quantum PCP theorem", arXiv:2410.13549, (2024).
[4] Jordi Weggemans, "Finding quantum partial assignments by search-to-decision reductions", arXiv:2408.03986, (2024).
[5] Kartik Anand, Kabgyun Jeong, and Junseo Lee, "Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy", arXiv:2506.19792, (2025).
[6] Harry Buhrman, François Le Gall, and Jordi Weggemans, "Classical versus quantum queries in quantum PCPs with classical proofs", arXiv:2411.00946, (2024).
[7] Kartik Anand, "Constructing Fermionic Hamiltonians with Non-Gaussianic low-energy states", arXiv:2502.15368, (2025).
[8] Yupan Liu and Pei Wu, "The power of unentanglement without destructive interference", arXiv:2604.27886, (2026).
[9] Baocheng Sun and Thomas Vidick, "Quantum Interactive Oracle Proofs", arXiv:2601.12874, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 13:19:04) and SAO/NASA ADS (last updated successfully 2026-08-09 13:19:05). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.