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

On perfect completeness for QMA

AaronsonScott

Published Jan 1, 2009• 2 citations
Publisher

Abstract

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...
DOI
10.5555/2021256.2021261

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

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

QMA-complete problems

Adam D. Bookatz

In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date (The reader is invited to share more proven QMA-complete problems with the author). Such problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a purported solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. An attempt has been made to make this paper as self-contained as possible so that it can be accessible to computer scientists, physicists, mathematicians, and quantum chemists. Problems of interest to all of these professions can be found here.

Quantum Information and Computation•May 1, 2014•26 citations

QMA-complete problems

Adam D. Bookatz

In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date. Such problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a purported solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. An attempt has been made to make this paper as self-contained as possible so that it can be accessible to computer scientists, physicists, mathematicians, and quantum chemists. Problems of interest to all of these professions can be found here.

arXiv:1212.6312•Dec 27, 2012•1 citation
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.
In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date (The reader is invited to share more proven QMA-complete problems with the author). Such problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a purported solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. An attempt has been made to make this paper as self-contained as possible so that it can be accessible to computer scientists, physicists, mathematicians, and quantum chemists. Problems of interest to all of these professions can be found here.
In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date. Such problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a purported solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. An attempt has been made to make this paper as self-contained as possible so that it can be accessible to computer scientists, physicists, mathematicians, and quantum chemists. Problems of interest to all of these professions can be found here.