Metraipolis › archive › dc_9aa63b376ec7

Exponential Quantum Advantage in Numbers-on-Forehead Communication — arXiv:2609.40273

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40273
License (as archived)
CC0-1.0
Archived
2026-10-07T15:17:57.947Z
SHA-256 of the archived text
2753dec7c0cec483ad63ebe487b3162d6c3a21287b69756876875258bc161a07
Stable URL of this page
https://metraipolis.com/documento/dc_9aa63b376ec7

How to cite

Exponential Quantum Advantage in Numbers-on-Forehead Communication — arXiv:2609.40273 — arXiv (en), https://arxiv.org/abs/2609.40273 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9aa63b376ec7 (Metraipolis archive dc_9aa63b376ec7, sha256 2753dec7c0cec483ad63ebe487b3162d6c3a21287b69756876875258bc161a07)
BibTeX
@misc{dc9aa63b376ec7,
  title = {Exponential Quantum Advantage in Numbers-on-Forehead Communication — arXiv:2609.40273},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40273},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9aa63b376ec7; sha256 2753dec7c0cec483ad63ebe487b3162d6c3a21287b69756876875258bc161a07},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40273. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetilde{\Omega}(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC) ; Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.40273 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:51:27.473Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).