Physics – Quantum Physics
Scientific paper
2006-12-08
Physics
Quantum Physics
17 pages
Scientific paper
We show that the value of a general two-prover quantum game cannot be computed by a semi-definite program ofvpolynomial 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))} \nsubseteq 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.
Kempe Julia
Vidick Thomas
No associations
LandOfFree
On the Power of Entangled Quantum Provers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Power of Entangled Quantum Provers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Power of Entangled Quantum Provers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-573368