This paper introduces quantum ``multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.
This paper introduces quantum ``multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.
This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA⊆PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.
This paper studies quantum Arthur-Merlin games, which are a restricted form of quantum interactive proof system in which the verifier's messages are given by unbiased coin-flips. The following results are proved. For one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA /spl sube/ PP. In the case of three or more messages, quantum Arthur-Merlin games are equivalent in power to ordinary quantum interactive proof systems. In fact, for any language having a quantum interactive proof system there exists a three-message quantum Arthur-Merlin game in which Arthur's only message consists of just a single coin-flip that achieves perfect completeness and soundness error exponentially close to 1/2. Any language having a two-message quantum Arthur-Merlin game is contained in BP /spl middot/ PP. This gives some suggestion that three messages are stronger than two in the quantum Arthur-Merlin setting.
We prove QMA=QMA1, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and X gates, yielding a universal gate set for QMA1. As a consequence, quantum 3-SAT is QMA-complete. The construction relativizes to classical oracles, so known classical-oracle separations of QMA from QCMA extend to QMA1.
This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, ${\QCMA = \QCMA_1}$. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, \emph{e.g.}, {Hadamard, Toffoli, NOT}. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that \emph{additively} adjusts the success probability, which may be of independent interest.
Interference and entanglement are among the most fundamental properties of quantum mechanics. In this work, we investigate the power of interference in the role of detecting entanglement in the context of quantum Merlin-Arthur verification. In particular, we show that unentanglement gives no additional power to stoquastic Merlin-Arthur proof systems, whose restriction to a classical gate set results in entrywise non-negative acceptance operators and non-negative optimal witnesses, therein removing destructive interference from the verification process. Our results show that for any polynomial number of unentangled witnesses k=k(n), StoqMA(k)=StoqMA. The analytic core of this result is a new non-negative de Finetti theorem for separately bosonic states. If a mixed state ρ is supported on the tensor product of symmetric subspaces of H1⊗R⊗H2⊗R⊗⋯⊗Hk⊗R then there exists a separable state τ on H1⊗⋯⊗Hk such that Tr(M(ρH1⊗⋯⊗Hk−τ))≤2R−1klog2dim(H1⊗⋯⊗Hk), simultaneously for all non-negative effects M. For any such operator M, one can define the separately symmetric lift SSR(M) whose largest eigenvalue approximates the maximum acceptance probability of M over product states within the same error bound. Such a lift can be approximated by a stoquastic verifier, giving that product-state constraint of StoqMA(k) verifiers can be absorbed into a polynomially larger one-witness StoqMA verification, while preserving an inverse polynomial completeness-soundness gap.