Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication

Quantum Physics [Submitted on 24 Mar 2026] Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication Guangxu Yang, Jiapeng Zhang 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 \Omega(\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. Comments: 16 pages Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC) Cite as: arXiv:2603.22795 [quant-ph]   (or arXiv:2603.22795v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.22795 Focus to learn more Submission history From: Guangxu Yang [view email] [v1] Tue, 24 Mar 2026 04:38:22 UTC (31 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 Change to browse by: cs cs.CC References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)