dorsal/arxiv
View SchemaBounded-Error Quantum State Identification and Exponential Separations in Communication Complexity
| Authors | Dmytro Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511013 |
| URL | https://arxiv.org/abs/quant-ph/0511013 |
Abstract
We consider the problem of bounded-error quantum state identification: given either state \alpha_0 or state \alpha_1, we are required to output `0', `1' or `?' ("don't know"), such that conditioned on outputting `0' or `1', our guess is correct with high probability. The goal is to maximize the probability of not outputting `?'. We prove a direct product theorem: if we're given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is O(ab). Our proof is based on semidefinite programming duality and may be of wider interest. Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. Both are shown in the strongest possible sense. First, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs Omega(n^{1/3}) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Second, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs Omega((n/log n)^{1/3}) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity of a situation where entanglement buys you much more than quantum communication does.
{
"annotation_id": "ebd5df07-8fad-44a3-994d-36dbebc4ffdf",
"date_created": "2026-03-02T18:02:20.030000Z",
"date_modified": "2026-03-02T18:02:20.030000Z",
"file_hash": "c9bc8ea1cd11fc5b9c0b5181da01bcb41e0898617799ed24af012f46309b53f3",
"private": false,
"record": {
"abstract": "We consider the problem of bounded-error quantum state identification: given\neither state \\alpha_0 or state \\alpha_1, we are required to output `0\u0027, `1\u0027 or\n`?\u0027 (\"don\u0027t know\"), such that conditioned on outputting `0\u0027 or `1\u0027, our guess\nis correct with high probability. The goal is to maximize the probability of\nnot outputting `?\u0027. We prove a direct product theorem: if we\u0027re given two such\nproblems, with optimal probabilities a and b, respectively, and the states in\nthe first problem are pure, then the optimal probability for the joint\nbounded-error state identification problem is O(ab). Our proof is based on\nsemidefinite programming duality and may be of wider interest.\n Using this result, we present two exponential separations in the simultaneous\nmessage passing model of communication complexity. Both are shown in the\nstrongest possible sense. First, we describe a relation that can be computed\nwith O(log n) classical bits of communication in the presence of shared\nrandomness, but needs Omega(n^{1/3}) communication if the parties don\u0027t share\nrandomness, even if communication is quantum. This shows the optimality of\nYao\u0027s recent exponential simulation of shared-randomness protocols by quantum\nprotocols without shared randomness. Second, we describe a relation that can be\ncomputed with O(log n) classical bits of communication in the presence of\nshared entanglement, but needs Omega((n/log n)^{1/3}) communication if the\nparties share randomness but no entanglement, even if communication is quantum.\nThis is the first example in communication complexity of a situation where\nentanglement buys you much more than quantum communication does.",
"arxiv_id": "quant-ph/0511013",
"authors": [
"Dmytro Gavinsky",
"Julia Kempe",
"Oded Regev",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity",
"url": "https://arxiv.org/abs/quant-ph/0511013"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "efab63d2-b27c-43c7-a609-7c9a4a216f13",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}