Skip to main content
U.S. flag

An official website of the United States government

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.
Citation
Quantum Information & Computation

Keywords

quantum complexity theory perfect completeness QCMA

Citation

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 March 4, 2024)
Created November 30, 2011, Updated February 19, 2017