An official website of the United States government
Here’s how you know
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)
Stephen P. Jordan, 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.
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 February 12, 2025)