On the Power of Entangled Quantum Provers
| dc.creator | Kempe, Julia | |
| dc.creator | Vidick, Thomas | |
| dc.date | 2006-12-08 | |
| dc.date.accessioned | 2026-07-07T07:35:08Z | |
| dc.date.available | 2026-07-07T07:35:08Z | |
| dc.description | 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. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0612063 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0612063 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/120001 | |
| dc.subject | Quantum Physics | |
| dc.title | On the Power of Entangled Quantum Provers | |
| dc.type | text |