Exponential Quantum Advantage in Numbers-on-Forehead Communication

@misc{wang2026exponential,
  title = {{Exponential Quantum Advantage in Numbers-on-Forehead Communication}},
  author = {Haoyu Wang and Pei Wu and Guangxu Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.40273},
  eprint = {2609.40273},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40273},
}

TY  - UNPB
TI  - Exponential Quantum Advantage in Numbers-on-Forehead Communication
AU  - Haoyu Wang
AU  - Pei Wu
AU  - Guangxu Yang
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2609.40273
UR  - https://arxiv.org/abs/2609.40273
AB  - 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 Ω̃(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.
ER  -