Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. It is proved that any problem in QMA has a two-message quantum interactive proof system with perfect completeness and constant soundness error, where the verifier has only to send a constant number...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2015-01, Vol.44 (2), p.243-289
Main Authors: Kobayashi, Hirotada, Le Gall, François, Nishimura, Harumichi
Format: Article
Language:English
Subjects:
Completeness
Computation
Constants
Construction
Interactive
Messages
Parallel processing
Proving
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. It is proved that any problem in QMA has a two-message quantum interactive proof system with perfect completeness and 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 with 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 with perfect completeness for every ${m \geq 2}$. This improves the previous construction due to Kitaev and Watrous, which increases the number of messages by two to achieve perfect completeness, if not using the parallelization result.
ISSN:0097-5397
1095-7111
DOI:10.1137/140971944