QCMA with One-sided Error Equals QCMA with Two-sided Error
Stephen P. Jordan, Daniel Nagaj
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.
and Nagaj, D.
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 March 4, 2024)