{"id":"arxiv/2609.40273","url":"https://arxiv.org/abs/2609.40273","tags":["cs.CC","quant-ph"],"score":0,"title":"Exponential Quantum Advantage in Numbers-on-Forehead Communication","domain":"cs.CC","source":"arxiv","authors":["Haoyu Wang","Pei Wu","Guangxu Yang"],"reviews":0,"subject":"cs.CC","summary":"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Ω(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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}