Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

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.

41 pages; v2: soundness parameters improved, correction of a minor error in Lemma 23, and removal of the sentences claiming that our techniques are quantumly nonrelativizing

References in corpus (7)

• Coding Theorem and Strong Converse for Quantum Channels
• One-and-a-half quantum de Finetti theorems
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• How hard is it to approximate the Jones polynomial?
• Quantum Strategies and Local Operations
• On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
• Efficient algorithm for a quantum analogue of 2-SAT

Cited by in corpus (3)

• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• Generalized Quantum Arthur-Merlin Games
• Space-Efficient Error Reduction for Unitary Quantum Computations