REVIEW 1 cited by
Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, QCMA = QCMA1. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, e.g., {Hadamard, Toffoli, NOT}. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that additively adjusts the success probability, which may be of independent interest.
Forward citations
Cited by 1 Pith paper
-
${\sf QMA}={\sf QMA}_1$ with an infinite counter
With an infinite counter register as part of the witness, QMA and its perfect-completeness variant QMA_1 become the same complexity class, and a finite truncation gives doubly-exponential completeness amplification.
Discussion (0). Continue with ORCID to comment.