Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0806.0450

On Perfect Completeness for QMA

Scott Aaronson

Published Jun 3, 2008• 1 citation
arXivHTMLPDF

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.

DOI
10.48550/arxiv.0806.0450

Related papers

On Perfect Completeness for QMA

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with onesided 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 QMA ≠ QMA1. 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 ⊆ ZQEXP.

•Jun 3, 2008•3 citations

On perfect completeness for QMA

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, 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" relative to which QMA \neq QMA_1. 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 \subseteq ZQEXP.

Quantum Information and Computation•Jan 1, 2009•29 citations

QMA has perfect completeness

Sabee Grewal, Dorian Rudolph

We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

quant-pharXiv:2609.13032•Sep 14, 2026•0 citations

The geometry of quantum computation

Mark R. Dowling, Michael A. Nielsen

Whether the class Quantum Merlin Arthur is equal to QMA_1, 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 QMA\neqQMA_1. 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\subseteq{ZQEXP}.

Quantum Information and Computation•Nov 1, 2008•137 citations

On perfect completeness for QMA

AaronsonScott

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with onesided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ide...

Quantum Information and Computation•Jan 1, 2009•2 citations

Quantum-Merlin-Arthur Problems Have Perfect Completeness with an Infinite Counter

Stacey Jeffery, Freek Witteveen

A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur (QMA), the quantum analog of nondeterministic polynomial time, is equal to QMA_{1}, its one-sided error variant. We show that QMA=QMA^{∞}=QMA_{1}^{∞}, where QMA_{1}^{∞} is like QMA_{1}, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an "infinite counter," and compare it to a program counter in a Las Vegas algorithm. The result, QMA=QMA^{∞} means such an infinite register does not increase the power of QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous QMA amplifiers. Our new construction achieves completeness 1-2^{-q} using O(1) calls to each of the original verifier and its inverse, and O(logq) other gates, proving that QMA has completeness doubly exponentially close to 1, i.e., QMA=QMA(1-2^{-2^{r}},2^{-r}) for any polynomial r.

Physical Review Letters•Apr 2, 2026•0 citations
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.
Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, 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" relative to which QMA \neq QMA_1. 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 \subseteq ZQEXP.
We prove QMA=QMA1\mathsf{QMA} = \mathsf{QMA_1}QMA=QMA1​, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and XXX gates, yielding a universal gate set for QMA1\mathsf{QMA_1}QMA1​. As a consequence, quantum 333-SAT is QMA\mathsf{QMA}QMA-complete. The construction relativizes to classical oracles, so known classical-oracle separations of QMA\mathsf{QMA}QMA from QCMA\mathsf{QCMA}QCMA extend to QMA1\mathsf{QMA_1}QMA1​.
A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur (QMA), the quantum analog of nondeterministic polynomial time, is equal to QMA_{1}, its one-sided error variant. We show that QMA=QMA^{∞}=QMA_{1}^{∞}, where QMA_{1}^{∞} is like QMA_{1}, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an "infinite counter," and compare it to a program counter in a Las Vegas algorithm. The result, QMA=QMA^{∞} means such an infinite register does not increase the power of QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous QMA amplifiers. Our new construction achieves completeness 1-2^{-q} using O(1) calls to each of the original verifier and its inverse, and O(logq) other gates, proving that QMA has completeness doubly exponentially close to 1, i.e., QMA=QMA(1-2^{-2^{r}},2^{-r}) for any polynomial r.