Why Black‑Box Amplification in QMA Reaches Its Limit – Insights from Aaronson & Witteveen

Quantum Merlin‑Arthur (QMA) and amplification

QMA is the quantum analogue of the classical class NP. A verifier, implemented as a quantum circuit, receives a quantum witness (proof) and decides to accept or reject. The completeness parameter $c$ is the probability of accepting a correct witness, while the soundness parameter $s$ is the maximum acceptance probability for any invalid witness. In the standard definition $c=2/3$ and $s=1/3$, but these constants can be amplified by repeating the verification procedure.

Black‑box amplification limit

For two decades researchers have sought amplification methods that drive the completeness error $1-c$ arbitrarily close to zero while keeping the soundness error $s$ small. Aaronson and Witteveen show that any black‑box amplification—where the verifier may only query the original QMA verification circuit as an oracle—cannot reduce the completeness error below a doubly‑exponential quantity. Formally, if the original gap is $ heta$, then after any black‑box transformation the error is bounded below by $2^{- ext{poly}(2^{ ext{poly}(1/ heta)})}$, which matches the best known double‑exponential amplification of Freek Witteveen and Stacey Jeffery.

Technical approach

The proof constructs a rational function $R_ heta(x)$ of the angle $ heta$ that exactly encodes the largest eigenvalue of a certain operator derived from the verification circuit. By analysing the roots and poles of $R_ heta$, the authors obtain a tight bound on how much the acceptance probability can be increased using only black‑box access. The construction was assisted by an AI model (GPT‑5), which suggested the form of the rational function; the final argument was verified by the authors.

Consequences and open problems

Consequences:

The result shows that black‑box techniques have reached their theoretical limit for QMA amplification.

It confirms that the double‑exponential amplification achieved by Witteveen–Jeffery is essentially optimal under black‑box constraints.

Open problems highlighted by the authors:

Whether QMA can equal the perfect‑completeness class QMA$_1$ when the verifier is restricted to a finite universal gate set. Existing proofs rely on non‑constructive or non‑finite‑gate arguments.

Whether the separating angle $ heta$ can be fixed to a constant (e.g., $ heta=\pi$) rather than varying over an interval, which would simplify the separation construction.

Both questions are conjectured to have affirmative answers, but new techniques beyond black‑box methods appear necessary.

Full paper: https://arxiv.org/abs/2509.21131

Code example

来源：ScienceAI
本文
约1000字
，建议阅读
5
分钟
这次，理论物理学家
Scott Aaronson
和合作者
Freek Witteveen
给出了一个明确答案：用黑箱方法，你刷到头了。