Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication

2025/06/20 by Yang, Guangxu, Zhang, Jiapeng · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2506.16804

Abstract

Quantum versus classical separation plays a central role in understanding the advantages of quantum computation. In this paper, we present the first exponential separation between quantum and bounded-error randomized communication complexity in a variant of the Number-on-Forehead (NOF) model. Namely, the three-player Simultaneous Number-on-Forehead model. Specifically, we introduce the Gadgeted Hidden Matching Problem and show that it can be solved using only O(log n) simultaneous quantum communication. In contrast, any simultaneous randomized protocol requires Ω(n^1/16) communication. On the technical side, a key obstacle in separating quantum and classical communication in NOF models is that all known randomized NOF lower bound tools, such as the discrepancy method, typically apply to both randomized and quantum protocols. In this regard, our technique provides a new method for proving randomized lower bounds in the NOF setting and may be of independent interest beyond the separation result.

Cited by

• A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Related

• Quantum multiparty communication complexity and circuit lower bounds
• Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity
• Quantum versus Randomized Communication Complexity, with Efficient Players
• Quantum vs. Classical Communication and Computation
• Quantum versus classical simultaneity in communication complexity