dorsal/arxiv
View SchemaQuantum communication complexity of symmetric predicates
| Authors | Alexander Razborov |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0204025 |
| URL | https://arxiv.org/abs/quant-ph/0204025 |
| DOI | 10.1070/IM2003v067n01ABEH000422 |
| Journal | Izvestiya of the Russian Academy of Science, mathematics, Vol. 67, No 1, 2003, pp. 159-176 (145-159 in Engl. transl.) |
Abstract
We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of every predicate $f(x,y)$ depending only on $|x\cap y|$ ($x,y\subseteq [n]$). Namely, for a predicate $D$ on $\{0,1,...,n\}$ let $\ell_0(D)\df \max\{\ell : 1\leq\ell\leq n/2\land D(\ell)\not\equiv D(\ell-1)\}$ and $\ell_1(D)\df \max\{n-\ell : n/2\leq\ell < n\land D(\ell)\not\equiv D(\ell+1)\}$. Then the bounded-error quantum communication complexity of $f_D(x,y) = D(|x\cap y|)$ is equal (again, up to a logarithmic factor) to $\sqrt{n\ell_0(D)}+\ell_1(D)$. In particular, the complexity of the set disjointness predicate is $\Omega(\sqrt n)$. This result holds both in the model with prior entanglement and without it.
{
"annotation_id": "fa4c159d-f292-43c7-9bbd-9a610b877ad2",
"date_created": "2026-03-02T18:01:48.535000Z",
"date_modified": "2026-03-02T18:01:48.535000Z",
"file_hash": "0b4667104d607ca0b7379c60717f6e5bebd63c59a513d61b5dc409acc1b98469",
"private": false,
"record": {
"abstract": "We completely (that is, up to a logarithmic factor) characterize the\nbounded-error quantum communication complexity of every predicate $f(x,y)$\ndepending only on $|x\\cap y|$ ($x,y\\subseteq [n]$). Namely, for a predicate $D$\non $\\{0,1,...,n\\}$ let $\\ell_0(D)\\df \\max\\{\\ell : 1\\leq\\ell\\leq n/2\\land\nD(\\ell)\\not\\equiv D(\\ell-1)\\}$ and $\\ell_1(D)\\df \\max\\{n-\\ell : n/2\\leq\\ell \u003c\nn\\land D(\\ell)\\not\\equiv D(\\ell+1)\\}$. Then the bounded-error quantum\ncommunication complexity of $f_D(x,y) = D(|x\\cap y|)$ is equal (again, up to a\nlogarithmic factor) to $\\sqrt{n\\ell_0(D)}+\\ell_1(D)$. In particular, the\ncomplexity of the set disjointness predicate is $\\Omega(\\sqrt n)$. This result\nholds both in the model with prior entanglement and without it.",
"arxiv_id": "quant-ph/0204025",
"authors": [
"Alexander Razborov"
],
"categories": [
"quant-ph"
],
"doi": "10.1070/IM2003v067n01ABEH000422",
"journal_ref": "Izvestiya of the Russian Academy of Science, mathematics, Vol. 67,\n No 1, 2003, pp. 159-176 (145-159 in Engl. transl.)",
"title": "Quantum communication complexity of symmetric predicates",
"url": "https://arxiv.org/abs/quant-ph/0204025"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "878b923a-d2dd-4322-9556-d95ff71f0c24",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}