A Caltech Library Service

On the Power of Entangled Quantum Provers

Kempe, Julia and Vidick, Thomas (2006) On the Power of Entangled Quantum Provers. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show that the value of a general two-prover quantum game cannot be computed by a semidefinite program of polynomial size (unless P=NP), a method that has been successful in more restricted quantum games. More precisely, we show that proof of membership in the NP-complete problem GAP-3D-MATCHING can be obtained by a 2-prover, 1-round quantum interactive proof system where the provers share entanglement, with perfect completeness and soundness s = 1 − 2^(−O(n)), and such that the space of the verifier and the size of the messages are O(log n). This implies that QMIP*_(log n,1,1−2−O(n))⊈ P unless P = NP and provides the first non-trivial lower bound on the power of entangled quantum provers, albeit with an exponentially small gap. The gap achievable by our proof system might in fact be larger, provided a certain conjecture on almost commuting versus nearly commuting projector matrices is true.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:(Submitted on 8 Dec 2006). Supported in part by ACI Sécurité Informatique SI/03 511 and ANR AlgoQP grants of the French Research Ministry, and also partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848. We thank Oded Regev and Ben Toner for extended discussions on QMIP∗ and MIP∗ and for generously sharing their knowledge with us, and Oded for providing the candidate counterexample. We thank Umesh Vazirani for very useful discussions during earlier work involving one quantum prover. We also thank Stanislav Szarek for discussions about almost commuting and almost diagonal matrices.
Funding AgencyGrant Number
ACI Sécurité InformatiqueSI/03 511
Agence Nationale pour la Recherche (ANR)UNSPECIFIED
European Commission015848
Record Number:CaltechAUTHORS:20160322-085312434
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65574
Deposited By: Ruth Sustaita
Deposited On:30 Mar 2016 23:53
Last Modified:03 Oct 2019 09:48

Repository Staff Only: item control page