We give the first exponential quantum advantage in the general interactive three-party Number-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)$ quantum communication but $\widetilde{\Omega}(n^{1/32})$ randomized communication in the NOF model. 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 (STOC 2024) 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 (TQC 2024), this yields our randomized lower bound.