{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:23:26Z","timestamp":1775024606661,"version":"3.50.1"},"reference-count":48,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T00:00:00Z","timestamp":1752192000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mi><\/mml:math>-local Hamiltonian problem with constant promise gap can be solved in Q<\/mml:mi>C<\/mml:mi>M<\/mml:mi>A<\/mml:mi><\/mml:mrow><\/mml:math>, then Q<\/mml:mi>P<\/mml:mi>C<\/mml:mi>P<\/mml:mi><\/mml:mrow>[<\/mml:mo>q<\/mml:mi>]<\/mml:mo>&#x2286;<\/mml:mo>Q<\/mml:mi>C<\/mml:mi>M<\/mml:mi>A<\/mml:mi><\/mml:mrow><\/mml:math> for any q<\/mml:mi>&#x2208;<\/mml:mo>O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:math>. (iii) If Q<\/mml:mi>M<\/mml:mi>A<\/mml:mi><\/mml:mrow>(<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:math> has a quantum PCP for any k<\/mml:mi>&#x2264;<\/mml:mo>poly<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math>, then Q<\/mml:mi>M<\/mml:mi>A<\/mml:mi><\/mml:mrow>(<\/mml:mo>2<\/mml:mn>)<\/mml:mo>=<\/mml:mo>Q<\/mml:mi>M<\/mml:mi>A<\/mml:mi><\/mml:mrow><\/mml:math>, 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.<\/jats:p>","DOI":"10.22331\/q-2025-07-11-1791","type":"journal-article","created":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T16:03:22Z","timestamp":1752249802000},"page":"1791","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians"],"prefix":"10.22331","volume":"9","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[{"name":"QuSoft, University of Amsterdam & Quantinuum, Partnership House, Carlisle Place, London"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7218-2585","authenticated-orcid":false,"given":"Jonas","family":"Helsen","sequence":"additional","affiliation":[{"name":"QuSoft & CWI, Amsterdam, the Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8469-6900","authenticated-orcid":false,"given":"Jordi","family":"Weggemans","sequence":"additional","affiliation":[{"name":"QuSoft & CWI, Amsterdam, the Netherlands"}]}],"member":"9598","published-online":{"date-parts":[[2025,7,11]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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\u2013158, 1971. ISBN 9781450374644.","DOI":"10.1145\/800157.805047"},{"key":"1","unstructured":"Leonid A. Levin. Universal sequential search problems. Problemy peredachi informatsii, 9 (3): 115\u2013116, 1973."},{"key":"2","doi-asserted-by":"crossref","unstructured":"Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. Classical and quantum computation. American Mathematical Society, 2002. ISBN 978-0-8218-3229-5.","DOI":"10.1090\/gsm\/047"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Sevag Gharibian. Guest Column: The 7 faces of quantum NP. SIGACT News, 54 (4): 54\u201391, January 2024. ISSN 0163-5700. arXiv: 2310.18010.","DOI":"10.1145\/3639528.3639535"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u2013555, May 1998. ISSN 0004-5411.","DOI":"10.1145\/278298.278306"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45 (1): 70\u2013122, January 1998. ISSN 0004-5411.","DOI":"10.1145\/273865.273901"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Irit Dinur. The PCP Theorem by Gap Amplification. Journal of the ACM, 54 (3): 12\u2013es, June 2007. ISSN 0004-5411.","DOI":"10.1145\/1236457.1236459"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u20131096, 2023. ISBN 9781450399135. arXiv: 2206.13228.","DOI":"10.1145\/3564246.3585114"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u201314:21, 2023a. ISBN 978-3-95977-283-9. arXiv: 2302.14755.","DOI":"10.4230\/LIPIcs.TQC.2023.14"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2024-11-19-1527"},{"key":"10","unstructured":"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."},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.109.052431"},{"key":"12","doi-asserted-by":"crossref","unstructured":"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\u2013720, July 2009. ISSN 1533-7146. arXiv: 0705.1115.","DOI":"10.26421\/QIC9.7-8-12"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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\u2013880, 2013a. ISBN 9781450320290. arXiv: 1310.0017.","DOI":"10.1145\/2488608.2488719"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov and Alex Bredariol Grilo. Stoquastic PCP vs. Randomness. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1000\u20131023, 2019. arXiv: 1901.05270.","DOI":"10.1109\/FOCS.2019.00065"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Sevag Gharibian and Fran\u00e7ois 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\u201332, 2022. ISBN 9781450392648. arXiv: 2111.09079.","DOI":"10.1145\/3519935.3519991"},{"key":"16","unstructured":"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."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, Fran\u00e7ois 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\u201332:19, 2023. ISBN 978-3-95977-278-5. arXiv: 2207.10250.","DOI":"10.4230\/LIPIcs.ICALP.2023.32"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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\u201310:24, 2024. ISBN 978-3-95977-328-7. arXiv: 2302.11578.","DOI":"10.4230\/LIPIcs.TQC.2024.10"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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\u2013426, 2009. ISBN 9781605585062. arXiv: 0811.3412.","DOI":"10.1145\/1536414.1536472"},{"key":"20","unstructured":"Alex B. Grilo. Quantum proofs, the local Hamiltonian problem and applications. PhD thesis, Universit\u00e9 Sorbonne Paris Cit\u00e9, April 2018."},{"key":"21","unstructured":"Dorit Aharonov and Tomer Naveh. Quantum NP\u2014a survey, October 2002. arXiv: quant-ph\/0210077."},{"key":"22","unstructured":"Anand Natarajan and Chinmay Nirkhe. The status of the quantum PCP conjecture (games version), 2024. arXiv: 2403.13084."},{"key":"23","unstructured":"Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, and Quynh T Nguyen. UniqueQMA vs QMA: oracle separation and eigenstate thermalization hypothesis, 2024. arXiv: 2410.23811."},{"key":"24","doi-asserted-by":"publisher","unstructured":"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\u201320:17, 2022. 10.4230\/LIPIcs.CCC.2022.20. arXiv: 2111.10409.","DOI":"10.4230\/LIPIcs.CCC.2022.20"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/2432622.2432625"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.98.110503"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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\u2013236, 2008. arXiv: 0804.0802.","DOI":"10.4086\/toc.2009.v005a001"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Salman Beigi. NP vs ${QMA}_{log}(2)$. Quantum Information & Computation, 10 (1): 141\u2013151, 2010. arXiv: 0810.5109.","DOI":"10.26421\/QIC10.1-2-10"},{"key":"29","doi-asserted-by":"publisher","unstructured":"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\u201337, 2009. arXiv: 0709.0738.","DOI":"10.1109\/ICQNM.2009.21"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Andr\u00e9 Chailloux and Or Sattath. The Complexity of the Separable Hamiltonian Problem. In 2012 IEEE 27th Conference on Computational Complexity, pages 32\u201341, 2012. arXiv: 1111.5247.","DOI":"10.1109\/CCC.2012.42"},{"key":"31","doi-asserted-by":"publisher","unstructured":"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\u2013449, 2006. arXiv: quant-ph\/0604166.","DOI":"10.1007\/11830924_40"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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\u20131450, 2022. arXiv: 1911.07782.","DOI":"10.1137\/21M140729X"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pages 115\u2013128, 2007. arXiv: quant-ph\/0604056.","DOI":"10.4086\/toc.2007.v003a007"},{"key":"34","unstructured":"Lance Fortnow. The role of relativization in complexity theory. Bulletin of the EATCS, 52: 229\u2013243, 1994."},{"key":"35","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.101.070503"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14 (2): 122\u2013152, 2005. 10.1007\/s00037-005-0194-x. arXiv: cs\/0506068.","DOI":"10.1007\/s00037-005-0194-x"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. SIGACT News, 44 (2): 47\u201379, June 2013. ISSN 0163-5700. arXiv: 1309.7495.","DOI":"10.1145\/2491533.2491549"},{"key":"38","doi-asserted-by":"publisher","unstructured":"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\u2013436, 2006. ISBN 1595931341. arXiv: quant-ph\/0511096.","DOI":"10.1145\/1132516.1132579"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12: 389\u2013434, 2012.","DOI":"10.1007\/s10208-011-9099-z"},{"key":"40","unstructured":"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."},{"key":"41","doi-asserted-by":"publisher","unstructured":"Persi Diaconis and David Freedman. Finite Exchangeable Sequences. The Annals of Probability, pages 745\u2013764, 1980.","DOI":"10.1214\/aop\/1176994663"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Renato Renner. Symmetry of large physical systems implies independence of subsystems. Nature Physics, 3 (9): 645\u2013649, 2007. arXiv: quant-ph\/0703069.","DOI":"10.1038\/nphys684"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Matthias Christandl, Robert K\u00f6nig, Graeme Mitchison, and Renato Renner. One-and-a-half quantum de Finetti theorems. Communications in Mathematical Physics, 273 (2): 473\u2013498, 2007. arXiv: quant-ph\/0602130.","DOI":"10.1007\/s00220-007-0189-3"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Fernando GSL Brandao, Matthias Christandl, and Jon Yard. Faithful squashed entanglement. Communications in Mathematical Physics, 306: 805\u2013830, 2011. arXiv: 1010.1750.","DOI":"10.1007\/s00220-011-1302-1"},{"key":"45","doi-asserted-by":"publisher","unstructured":"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\u2013870, 2013b. ISBN 9781450320290. arXiv: 1210.6367.","DOI":"10.1145\/2488608.2488718"},{"key":"46","doi-asserted-by":"publisher","unstructured":"K\u00e1roly B\u00f6r\u00f6czky and Gergely Wintsche. Covering the Sphere by Equal Spherical Balls, pages 235\u2013251. Springer, Berlin, Heidelberg, 2003. ISBN 978-3-642-55566-4.","DOI":"10.1007\/978-3-642-55566-4_10"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing, 26 (5): 1510\u20131523, 1997. arXiv: quant-ph\/9701001.","DOI":"10.1137\/S0097539796300933"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-07-11-1791\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T16:03:26Z","timestamp":1752249806000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-07-11-1791\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,11]]},"references-count":48,"URL":"https:\/\/doi.org\/10.22331\/q-2025-07-11-1791","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,11]]},"article-number":"1791"}}