  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.
