Limits to black-box amplification in QMA
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.
Authors
- Scott Aaronson
Institutions
- University of Bonn (DE)
- QuSoft (NL)
- Simons Foundation (US)
Publication Details
- Journal
- Quantum
- Published
- 2026-10-06
- DOI
- https://doi.org/10.22331/q-2026-10-06-2227
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- European Commission
- Deutsche Forschungsgemeinschaft