Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914417086562304 |
|---|---|
| author | Yang, Guangxu Zhang, Jiapeng |
| author_facet | Yang, Guangxu Zhang, Jiapeng |
| contents | Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing strong one-way NOF lower bounds would imply circuit lower bounds, resolve well-known problems in additive combinatorics, and yield wide-ranging applications in areas such as cryptography and distributed computing. However, proving strong lower bounds in one-way NOF communication remains highly challenging; many fundamental questions in one-way NOF communication remain wide open. One of the fundamental questions, proposed by Gavinsky and Pudlák (CCC 2008), is to establish an explicit exponential separation between quantum and classical one-way NOF communication.
In this paper, we resolve this open problem by establishing the first exponential separation between quantum and randomized communication complexity in one-way NOF model. Specifically, we define a lifted variant of the Hidden Matching problem of Bar-Yossef, Jayram, and Kerenidis (STOC 2004) and show that it admits an ($O(\log n)$)-cost quantum protocol in the one-way NOF setting. By contrast, we prove that any $k$-party one-way randomized protocol for this problem requires communication $Ω(\frac{n^{1/3}}{2^{k/3}})$. Notably, our separation applies even to a generalization of $k$-player one-way communication, where the first player speaks once, and all other $k-1$ players can communicate freely. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22795 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication Yang, Guangxu Zhang, Jiapeng Quantum Physics Computational Complexity Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing strong one-way NOF lower bounds would imply circuit lower bounds, resolve well-known problems in additive combinatorics, and yield wide-ranging applications in areas such as cryptography and distributed computing. However, proving strong lower bounds in one-way NOF communication remains highly challenging; many fundamental questions in one-way NOF communication remain wide open. One of the fundamental questions, proposed by Gavinsky and Pudlák (CCC 2008), is to establish an explicit exponential separation between quantum and classical one-way NOF communication. In this paper, we resolve this open problem by establishing the first exponential separation between quantum and randomized communication complexity in one-way NOF model. Specifically, we define a lifted variant of the Hidden Matching problem of Bar-Yossef, Jayram, and Kerenidis (STOC 2004) and show that it admits an ($O(\log n)$)-cost quantum protocol in the one-way NOF setting. By contrast, we prove that any $k$-party one-way randomized protocol for this problem requires communication $Ω(\frac{n^{1/3}}{2^{k/3}})$. Notably, our separation applies even to a generalization of $k$-player one-way communication, where the first player speaks once, and all other $k-1$ players can communicate freely. |
| title | Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2603.22795 |