analiza aiqbench
This research establishes a fundamental theoretical boundary for black-box amplification within the QMA complexity class, proving that doubly exponential completeness is the optimal limit achievable by polynomial-resource verification procedures. By quantifying the separation between QMA and QMA₁ using complex approximation theory, the study clarifies the intrinsic constraints on boosting proof reliability in quantum interactive proofs. These findings are critical for theorists working on the foundational limits of quantum verification protocols and complexity class hierarchies.
Limits to black-box amplification in QMA
Quantum 10, 2227 (2026). https://doi.org/10.22331/q-2026-10-06-2227 We study the limitations of black-box amplification in the quantum complexity class ${\sf QMA}$. Amplification is known to boost any inverse-polynomial gap between completeness and soundness to exponentially small error, and a recent result (Jeffery and Witteveen, 2025) shows that completeness can in fact be amplified to be doubly exponentially close to 1. We prove that this is optimal for black-box procedures: we provide a quantum oracle relative to which no ${\sf QMA}$ verification procedure using polynomial resources can achieve completeness closer to 1 than doubly exponential, or a soundness which is super-exponentially small. This is proven by making the oracle separation from (Aaronson, 2009) between ${\sf QMA}$ and ${\sf QMA}_1$ quantitative, using techniques from complex approximation theory.
We study the limitations of black-box amplification in the quantum complexity class ${\sf QMA}$. Amplification is known to boost any inverse-polynomial gap between completeness and soundness to exponentially small error, and a recent result (Jeffery and Witteveen, 2025) shows that completeness can in fact be amplified to be doubly exponentially close to 1. We prove that this is optimal for black-box procedures: we provide a quantum oracle relative to which no ${\sf QMA}$ verification procedure using polynomial resources can achieve completeness closer to 1 than doubly exponential, or a soundness which is super-exponentially small. This is proven by making the oracle separation from (Aaronson, 2009) between ${\sf QMA}$ and ${\sf QMA}_1$ quantitative, using techniques from complex approximation theory.
[1] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. ``Classical and quantum computation''. Number 47 in Graduate Studies in Mathematics. American Mathematical Society. (2002).
[2] Chris Marriott and John Watrous. ``Quantum Arthur–Merlin games''. Computational Complexity 14, 122–152 (2005). arXiv:cs/0506068. https://doi.org/10.1007/s00037-005-0194-x arXiv:cs/0506068
[3] Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. ``Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems''. Quantum Information and Computation 12, 461–471 (2012). arXiv:1111.5306. https://doi.org/10.26421/QIC12.5-6-7 arXiv:1111.5306
[4] Bill Fefferman and Cedric Yen-Yu Lin. ``A complete characterization of unitary quantum space''. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Pages 4–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2018). arXiv:1604.01384. arXiv:1604.01384
[5] Scott Aaronson. ``On perfect completeness for QMA''. Quantum Information and Computation 9, 81–89 (2009). arXiv:0806.0450. https://doi.org/10.26421/QIC9.1-2-5 arXiv:0806.0450
[6] Stacey Jeffery and Freek Witteveen. ``Quantum-merlin-arthur problems have perfect completeness with an infinite counter''. Physical Review Letters 136, 180601 (2026). arXiv:2506.15551. https://doi.org/10.1103/pwdd-htbf arXiv:2506.15551
[7] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. ``Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur?''. In International Symposium on Algorithms and Computation. Pages 189–198. Springer (2003). arXiv:quant-ph/0306051. https://doi.org/10.1007/978-3-540-24587-2_21 arXiv:quant-ph/0306051
[8] Stephen Fenner, Frederic Green, Steven Homer, and Randall Pruim. ``Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy''. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 455, 3953–3966 (1999). arXiv:quant-ph/9812056. https://doi.org/10.1098/rspa.1999.0485 arXiv:quant-ph/9812056
[9] AA Gončar. ``Zolotarev problems connected with rational functions''. Mathematics of the USSR-Sbornik 7, 623 (1969). https://doi.org/10.1070/SM1969v007n04ABEH001107
[10] Scott Aaronson. ``Shtetl Optimized: The QMA Singularity''. https://scottaaronson.blog/?p=9183 (2025). https://scottaaronson.blog/?p=9183
[11] Peter Borwein and Tamás Erdélyi. ``Polynomials and polynomial inequalities''. Volume 161. Springer Science & Business Media. (2012).
Could not fetch Crossref cited-by data during last attempt 2026-10-06 08:44:54: Could not fetch cited-by data for 10.22331/q-2026-10-06-2227 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-10-06 08:44:54: Cannot retrieve data from ADS due to rate limitations.
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.
Text integral sub licența deschisă a publicației · 467 cuvinte
Subiecte conexe
Improving CoT Monitorability of Evaluation Awareness via Verbalization Training
LessWrong · 2 oct. 2026
Limits to black-box amplification in QMA
arXiv · 22 sept. 2026
Presentation: Beyond Prompting: Context Engineering and Memory Management for AI Systems at Scale
InfoQ · 10 iun. 2026
Quantum Algorithms Halve Needed Data for Complex Material Simulations
Quantum Zeitgeist · 8 iun. 2026