 |
|
Subscribers:
to view the full text of a paper, click on the title of the paper. If you
have any problem to access the full text, please check with your librarian
or contact
qic@rintonpress.com
To subscribe to QIC, please click
Here.
|
Quantum
Information and Computation
ISSN: 1533-7146
published since 2001
|
|
Vol.9 No.1&2
January 2009 |
|
On
perfect completeness for QMA
(pp0081-0089)
Scott
Aaronson
doi:
https://doi.org/10.26421/QIC9.1-2-5
Abstracts: 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 not equal to ZQEXP.
Key words: quantum Merlin
Authur |
ˇˇ |