Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

Understand

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.