dorsal/arxiv
View SchemaOn the Power of Entangled Quantum Provers
| Authors | Julia Kempe, Thomas Vidick |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0612063 |
| URL | https://arxiv.org/abs/quant-ph/0612063 |
Abstract
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.
{
"annotation_id": "1dc41ce0-60d3-4a79-b705-167210375a60",
"date_created": "2026-03-02T18:02:34.183000Z",
"date_modified": "2026-03-02T18:02:34.183000Z",
"file_hash": "ba1dc357681df9ea6e21860a06e280a686b91c726cbc577ad80fa9ae98f16306",
"private": false,
"record": {
"abstract": "We show that the value of a general two-prover quantum game cannot be\ncomputed by a semi-definite program ofvpolynomial size (unless P=NP), a method\nthat has been successful in more restricted quantum games. More precisely, we\nshow that proof of membership in the NP-complete problem GAP-3D-Matching can be\nobtained by a 2-prover, 1-round quantum interactive proof system where the\nprovers share entanglement, with perfect completeness and soundness\ns=1-2^(-O(n)), and such that the space of the verifier and the size of the\nmessages are O(log n). This implies that QMIP^*_{log n,1,1-2^(-O(n))}\n\\nsubseteq P unless P = NP and provides the first non-trivial lower bound on\nthe power of entangled quantum provers, albeit with an exponentially small gap.\nThe gap achievable by our proof system might in fact be larger, provided a\ncertain conjecture on almost commuting versus nearly commuting projector\nmatrices is true.",
"arxiv_id": "quant-ph/0612063",
"authors": [
"Julia Kempe",
"Thomas Vidick"
],
"categories": [
"quant-ph"
],
"title": "On the Power of Entangled Quantum Provers",
"url": "https://arxiv.org/abs/quant-ph/0612063"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "750271bb-7aa1-4da7-9eab-e533a75ab265",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}