Skip to content
DraconiticResearch
Search Sources API
197,785 studies31 sourcesUpdated 25 min ago
Peer-reviewedCC BY 4.0Quantum

Limits to black-box amplification in QMA

  • Scott Aaronson1
  • Phillip Harris2
  • Freek Witteveen3
  1. 1University of Texas at Austin. Supported by the Simons Foundation
  2. 2University of Bonn
  3. 3QuSoft & CWI, Amsterdam
Open at sourcePDFDOICite

Abstract

We study the limitations of black-box amplification in the quantum complexity class Q M A . 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 Q M A 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 Q M A and Q M A 1 quantitative, using techniques from complex approximation theory.

Related

  1. Same Events, Weaker Bound: Model Dependence in Magellanic Microlensing Limits on Primordial Black Holes
    David Morales-Zapien, Lucas Brown, Stefano Profumo
    arXivPreprintCC BY 4.0Full textCosmologyHigh-energy astrophysicsarXiv
  2. Black Strings and Black Holes: Worldsheet Spectra and Near-Extremal Limits
    Ziyi Li
    arXivPreprintarXiv licenceFull textHigh-energy & particle physicsarXiv
  3. Topological ModMax--AdS Black Holes: Extremality, Charge Normalization, and Limits of WGC Diagnostics
    Saeed Noori Gashti, Behnam Pourhassan, Saheb Soroushfar
    arXivPreprintCC BY 4.0Full textGravitation & general relativityHigh-energy & particle physicsarXiv
  4. Black Hole-Tower Correspondence: Species backreaction in minimal black hole limits
    Miquel Aparici, Alvaro Herráez, Joaquin Masias
    arXivPreprintCC0Full textHigh-energy & particle physicsarXiv
  5. On flat space limits of AdS4 black holes
    Pedro Vicente Marto, Shradha Ramakrishnan, Stefan Vandoren
    arXivPreprintarXiv licenceFull textHigh-energy & particle physicsarXiv

Cite

BibTeXRIS
BibTeX
@article{aaronson2026limits,
  title = {{Limits to black-box amplification in QMA}},
  author = {Scott Aaronson and Phillip Harris and Freek Witteveen},
  journal = {Quantum},
  year = {2026},
  month = oct,
  doi = {10.22331/q-2026-10-06-2227},
  url = {https://quantum-journal.org/papers/q-2026-10-06-2227/},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - Limits to black-box amplification in QMA
AU  - Scott Aaronson
AU  - Phillip Harris
AU  - Freek Witteveen
PY  - 2026
DA  - 2026/10/06
JO  - Quantum
DO  - 10.22331/q-2026-10-06-2227
UR  - https://quantum-journal.org/papers/q-2026-10-06-2227/
AB  - We study the limitations of black-box amplification in the quantum complexity class Q M A . 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 Q M A 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 Q M A and Q M A 1 quantitative, using techniques from complex approximation theory.
SN  - 2521-327X
ER  -