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

Quantum Information and Computation

The geometry of quantum computation

Mark R. Dowling, Michael A. Nielsen

Published Nov 1, 2008• 137 citations
Publisher

Abstract

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}.

DOI
10.26421/qic8.10-1

Related papers

On Perfect Completeness for QMA

Scott Aaronson

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.

arXiv:0806.0450•Jun 3, 2008•1 citation

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

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

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

Separating ClonableQMA and QCMA Relative to a Classical Oracle

Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung +1 more

Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.

cs.CCCross-listedarXiv:2610.06740•Oct 6, 2026•0 citations
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}.
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​.
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.