2026-09-11
Limits to black-box amplification in QMA
Publication
Publication
Quantum , Volume 10 p. 2227:1- 2227:7
We study the limitations of black-box amplification in the quantum complexity class 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 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 QMA and QMA_1 quantitative, using techniques from complex approximation theory.
| Additional Metadata | |
|---|---|
| doi.org/10.22331/q-2026-10-06-2227 | |
| Quantum | |
| ASC-Q | |
| creativecommons.org/licenses/by/4.0/ | |
| Organisation | Algorithms and Complexity |
|
Aaronson, S., Harris, P.& Witteveen, F. (2026). Limits to black-box amplification in QMA. Quantum, 10, 2227:1–2227:7.https://doi.org/10.22331/q-2026-10-06-2227 |
|
