REVIEW 1 cited by
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
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
abstract
This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. First, it is proved that any problem in QMA has a two-message quantum interactive proof system of perfect completeness with constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP_1(2) of problems having two-message quantum interactive proofs of perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. It is also proved that any problem having an $m$-message quantum interactive proof system necessarily has an $(m+1)$-message quantum interactive proof system of perfect completeness. This improves the previous result due to Kitaev and Watrous, where the resulting system of perfect completeness requires $m+2$ messages if not using the parallelization result.
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.