With an infinite counter register as part of the witness, QMA and its perfect-completeness variant QMA_1 become the same complexity class, and a finite truncation gives doubly-exponential completeness amplification.
On Perfect Completeness for QMA
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which they are different. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP in ZQEXP.
fields
quant-ph 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
${\sf QMA}={\sf QMA}_1$ with an infinite counter
With an infinite counter register as part of the witness, QMA and its perfect-completeness variant QMA_1 become the same complexity class, and a finite truncation gives doubly-exponential completeness amplification.