dorsal/arxiv
View SchemaQuantum multiparty communication complexity and circuit lower bounds
| Authors | Iordanis Kerenidis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0504087 |
| URL | https://arxiv.org/abs/quant-ph/0504087 |
Abstract
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show that if the quantum k-party communication complexity of a function f is $\Omega(n/2^k)$, then its classical k-party communication is $\Omega(n/2^{k/2})$. Finding such an f would allow us to prove strong classical lower bounds for (k>log n) players and hence resolve a main open question about symmetric circuits. Furthermore, we prove that for the Generalized Inner Product (GIP) function, the quantum model is exponentially more efficient than the classical one. This provides the first exponential separation for a total function between any quantum and public coin randomized communication model.
{
"annotation_id": "53a1b2b3-ef99-469c-b080-42a152311eb1",
"date_created": "2026-03-02T18:02:15.966000Z",
"date_modified": "2026-03-02T18:02:15.966000Z",
"file_hash": "717aca911e9c0b859b32aedf7869300c2c21b8fd76976da4aa042ae9b06d0312",
"private": false,
"record": {
"abstract": "We define a quantum model for multiparty communication complexity and prove a\nsimulation theorem between the classical and quantum models. As a result of our\nsimulation, we show that if the quantum k-party communication complexity of a\nfunction f is $\\Omega(n/2^k)$, then its classical k-party communication is\n$\\Omega(n/2^{k/2})$. Finding such an f would allow us to prove strong classical\nlower bounds for (k\u003elog n) players and hence resolve a main open question about\nsymmetric circuits. Furthermore, we prove that for the Generalized Inner\nProduct (GIP) function, the quantum model is exponentially more efficient than\nthe classical one. This provides the first exponential separation for a total\nfunction between any quantum and public coin randomized communication model.",
"arxiv_id": "quant-ph/0504087",
"authors": [
"Iordanis Kerenidis"
],
"categories": [
"quant-ph"
],
"title": "Quantum multiparty communication complexity and circuit lower bounds",
"url": "https://arxiv.org/abs/quant-ph/0504087"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "809c6fb4-895a-429e-b32e-9b2e2129b636",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}