Jordan, S.
and Nagaj, D.
(2011),
QCMA with One-sided Error Equals QCMA with Two-sided Error, Quantum Information & Computation, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=909926
(Accessed October 18, 2025)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
QCMA with One-sided Error Equals QCMA with Two-sided Error
Published
Author(s)
, Daniel Nagaj
Abstract
QCMA is the set of decision problems such that if the answer is yes, there exists a classical bitstring, or proof, that can be efficiently verified by a quantum computer. The verifier is allowed a small probability of rejecting a valid proof or accepting invalid proofs. We show that for all problems in QCMA, the acceptance probability for valid proofs can be boosted to one, thus QCMA with one-sided error is equal to QCMA. This is a quantum analogue to the result of Zachos and Furer, that the classical complexity class MA with one sided error is the same as MA with two-sided error. Because a quantum oracle separating QCMA and QCMA with one sided error is known, our result is a rare example of a non-relativizing proof.Citation
Quantum Information & Computation
Pub Type
Journals
Download Paper
Keywords
quantum complexity theory perfect completeness QCMA
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact [email protected].
Created November 30, 2011, Updated February 19, 2017