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

Guangxu Yang, Jiapeng Zhang · 2025

Read Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication by Guangxu Yang, Jiapeng Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16804.txt.

Introduction

Guangxu Yang and Jiapeng Zhang prove that quantum messages can beat classical ones by an exponential margin in a strange game of distributed knowledge. In the number-on-forehead model, each player sees the others' inputs written on their foreheads but not their own. The simultaneous variant, where all speak at once to a referee, had never shown a clean quantum-classical split. Their 2025 paper supplies one.

They devise a problem, the gadgeted hidden matching problem, that three quantum players solve while exchanging only a logarithmic trickle of communication. Any classical randomized team speaking simultaneously, they prove, needs a polynomially larger flood. The hard part was the lower bound: the usual discrepancy tool bounds quantum protocols too, so it cannot separate the two. Their new technique for bounding randomized play in this setting is offered as a tool of independent interest.

Catalog record

CREATORGuangxu Yang, Jiapeng Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16804

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication Guangxu Yang, Jiapeng Zhang 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 ) O(\log n) simultaneous quantum communication. In contrast, any simultaneous randomized protocol requires Ω ⁡ ( n 1 / 16 ) \Omega(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. 1 Introduction One of the central goals in the study of quantum advantage is to demonstrate separations between quantum and classical computation in various computational models. In this direction, substantial progress has been achieved in communication complexity, where a line of work [ BCW98 , Raz99 , BYJK04 , GKK+07 , RK11 , Gav16 , GRT22 , Gav19 , Gav20 , GGJL24 ] has established exponential separations in multiple settings. These results provide explicit problems that can be solved by quantum protocols using only (\log n)^{O(1)} communication, whereas any classical randomized protocol solving the same problem must use n^{\Omega(1)} communication. However, all of the aforementioned results pertain to two-party communication models. In contrast, separations in multiparty communication, specifically the Number-on-Forehead (NOF) models, remain poorly understood. Lower bounds in the NOF models are especially intriguing because NOF protocols can simulate a broader range of computational models than those in the two-party setting. To this end, Göös, Gur, Jain, and Li [ GGJL24 ] highlighted the separation of quantum and randomized communication in NOF models as an important open problem. The main obstacle to obtaining strong quantum-versus-classical separations in the NOF setting, as noted by [ GGJL24 ] , lies in the lack of techniques for proving lower bounds for randomized NOF protocols. Existing approaches, such as the discrepancy method, often apply equally well to quantum communication, making it difficult to distinguish between the power of quantum and classical protocols in the NOF model [ LSS09 ] . In this paper, we study the simultaneous NOF model , a variant of the NOF communication model. In this setting, each player i sends a single message, computed based on all inputs except x_{i} , to a referee (or the last player), who then determines the output after receiving all the messages. Although the simultaneous NOF model appears weaker than the standard NOF model, proving strong lower bounds in this setting remains highly challenging. Strong simultaneous NOF lower bounds have significant implications in various areas, including lower bounds for the ACC circuit class [ HG90 , PRS97 ] , private information retrieval [ CKGS98 ] , and position-based cryptography [ BDFP17 ] . Furthermore, many known non-trivial NOF protocols such as the \sqrt{\log N} protocol for Exactly-N [ CFL83 ] , the O\left(\frac{n\log\log n}{\log n}\right) for multipointer jumping [ BS15 ] and Shifting [ HG90 ] , and Grolmusz protocols for generalized inner-product [ Gro94 ] and set disjointness [ RY20 ] are all simultaneous protocols. 1.1 Our Results In this paper, we establish the first exponential separation between quantum and bounded-error randomized communication complexity in the simultaneous NOF model. Our problem is inspired by the Hidden Matching Problem introduced by [ BYJK04 ] . In the Hidden Matching Problem, 1. Alice is given a string z\in\{0,1\}^{n} . 2. Bob is given M\in\mathcal{M}_{n} where \mathcal{M}_{n} denotes the family of all possible perfect matchings on n nodes. Their goal is for Bob to output a tuple \langle i,j,b\rangle such that the edge (i,j) belongs to M and b=z_{i}\oplus z_{j} . As shown in [ BYJK04 ] , the Hidden Matching Problem admits an O(\log n) simultaneous quantum communication protocol, while any one-way randomized protocol requires \Omega(\sqrt{n}) communication. Inspired by [ BYJK04 ] , we introduce the Gadgeted Hidden Matching Problem (GHM). Let m:=n/2 . For each i\in[m] , we define a perfect matching M_{i} between \{0,\dots,m-1\} and \{m,\dots,2m-1\} as M_{i}:=\left\{\left(\ell,m+\left((i+\ell)\bmod m\right)\right):\ell\in[m]\right\}. Let \mathcal{M}=\{M_{1},\dots,M_{m}\} denote the collection of these matchings. The GHM is defined as follows: Definition 1.1 . Let g:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow[m] be any gadget function. The Gadgeted Hidden Matching Problem , denoted \text{GHM}\circ g , involves three inputs distributed among the players as follows: • Alice receives z,y\in\{0,1\}^{n} , • Bob receives z,x\in\{0,1\}^{n} , • Charlie receives x,y\in\{0,1\}^{n} . The goal is for Charlie to output a tuple \langle\ell,r,b\rangle such that (\ell,r)\in M_{g(x,y)} and b=z_{\ell}\oplus z_{r} . Remarkably, this problem remains easy for quantum communication. Similar to the Hidden Matching Problem, Alice only needs to send a uniform superposition of the string z , with a communication cost of O(\log n) qubits. Charlie can then perform a measurement on this superposition, which depends on the matching M_{g(x,y)} , and output the parity of some pair in M_{g(x,y)} (see the appendix for more details). We note that Bob does not need to send any message using this protocol. Thus, the main result of our paper is the n^{\Omega(1)} randomized simultaneous NOF communication. Theorem 1.2 . There exists an explicit gadget function g:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow[m] such that the randomized simultaneous NOF communication complexity of \text{GHM}\circ g is \Omega(n^{1/16}) . When g is clear from context, we simplify \text{GHM}\circ g to GHM . 2 Preliminaries We begin by fixing some notation. The set of integers \{0,\ldots,n-1\} is denoted by [n] . We use capital letters like X to denote sets, and bold symbols like \bm{X} to denote random variables. In particular, for a set X , we use \bm{X} to denote the random variable that is uniformly distributed over the set X . A search problem is a relation S\subseteq X\times Y\times Z\times Q , where Q is the set of possible solutions. On input (x,y,z)\in X\times Y\times Z , the goal is to find a solution q\in Q such that (x,y,z,q)\in S . Note that for the (Gadgeted) Hidden Matching Problem, all inputs are guaranteed to have at least one solution. 2.1 Simultaneous Number-on-Forehead Model In the three-party simultaneous NOF communication complexity model, Alice, Bob, and Charlie collaborate to compute a search problem S\subseteq X\times Y\times Z\times Q . Their inputs are as follows: • Alice receives (y,z)\in Y\times Z . • Bob receives (x,z)\in X\times Z . • Charlie receives (x,y)\in X\times Y . The randomized SM protocol \Pi=(\Pi_{A},\Pi_{B},\Pi_{C}) proceeds as follows: 1. Alice and Bob simultaneously send messages to Charlie, where Alice’s message \Pi_{A}(y,z,r) depends only on the input (y,z) and public randomness r and Bob’s message \Pi_{B}(x,z,r) depends only on the input (x,z) and public randomness r . 2. After receiving both messages, Charlie outputs a solution q=\Pi_{C}(\Pi_{A}(y,z),\Pi_{B}(x,z),x,y,r)\in Q . The protocol \Pi computes S with error \epsilon if for any (x,y,z) , \operatorname*{\mathbf{Pr}}_{r}[(x,y,z,q)\in S]\geq 1-\epsilon . 2.2 Basics of Information Theory Our proof approach involves several

Read the complete text