Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements

Abstract

BellQMA protocols are a subclass of multi-prover quantum Merlin-Arthur protocols in which the verifier is restricted to perform nonadaptive,unentangled measurements on the quantum states received from each Merlin. In this paper, we prove that m-clause 3-SAT instances have BellQMA proofs of satisfiability with constant soundness gap, in which O(sqrt(m)polylog(m)) Merlins each send O(log m) qubits to Arthur. Our result answers a question of Aaronson et al., who gave a protocol with similar parameters that used entangled measurements; the analysis of our protocol is significantly simpler than that of Aaronson et al. Our result also complements recent work of Brandao, Christandl, and Yard, who showed upper bounds on the power of multiprover quantum proofs with unentangled but adaptive (LOCC) measurements.

13 pages

References in corpus (6)

• Concentrating Partial Entanglement by Local Operations
• Quantum fingerprinting
• Conditions for a class of entanglement transformations
• Faithful Squashed Entanglement
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• A quantum characterization of NP

Cited by in corpus (7)

• An improved semidefinite programming hierarchy for testing entanglement
• Limitations of semidefinite programs for separable states and entangled games
• Improved Soundness for QMA with Multiple Provers
• Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap
• Lower Bounds for Learning Quantum States with Single-Copy Measurements
• The 7 faces of quantum NP
• Approximation, Proof Systems, and Correlations in a Quantum World