Constant-round quantum advantage in communication complexity for total functions

Communication complexity [22, 23] provides a basic setting for studying the power of quantum communication. Two parties, Alice and Bob, receive inputs $x,y\in\{0,1\}^{n}$ and want to compute a function $f(x,y)$ using as little communication as possible. A central question is to quantify the advantage of quantum communication over classical communication. The case of total functions is particularly fundamental, as it provides a more natural setting in which the protocol must work on every pair of inputs, without any promise on the inputs.

The first asymptotic quantum advantage for a total function was shown in the seminal work by Buhrman, Cleve, and Wigderson [8] for set disjointness. For $\mathsf{DISJ}_{n}(x,y)=1\Leftrightarrow x_{i}y_{i}=0\text{ for every }i\in[n]$, their protocol runs Grover search [12] on the virtual input $z=x\wedge y$, whose $i$-th bit $z_{i}=x_{i}\wedge y_{i}$ is jointly determined by Alice and Bob. To implement a quantum query $|i,b\rangle\mapsto|i,b\oplus z_{i}\rangle$ on a superposition of indices, Alice coherently computes $x_{i}$ into an ancilla and sends the index, answer, and ancilla registers to Bob. Bob uses $y_{i}$ to flip the answer qubit precisely when $x_{i}=y_{i}=1$, sends the registers back to Alice, and Alice uncomputes the ancilla. Thus, each Grover query is implemented through an Alice-to-Bob-to-Alice exchange of $O(\log n)$ qubits. Since Grover search makes $O(\sqrt{n})$ queries, this gives a quantum protocol using $O(\sqrt{n}\log n)$ communication.

Classical bounded-error protocols require linear communication, $R_{cc}(\mathsf{DISJ}_{n})=\Theta(n)$, as shown in [15, 18]. The quantum upper bound was subsequently improved by Høyer and de Wolf [13], and Aaronson and Ambainis [1] obtained the optimal bound $Q_{cc}(\mathsf{DISJ}_{n})=O(\sqrt{n})$, matching Razborov’s lower bound [19]. Thus, disjointness exhibits a quadratic separation between randomized and quantum communication complexity.

The cheat-sheet framework of Aaronson, Ben-David, and Kothari [3] made it possible to go beyond the quadratic Grover-type separation in query complexity. Anshu et al. [4] developed a communication analogue, and obtained the first super-quadratic separation for a total communication problem. Subsequent work of Bansal and Sinha [5] and Sherstov, Storozhenko, and Wu [20] strengthened the underlying randomized-versus-quantum query separations. These improved query separations can be transferred to communication complexity by combining randomized lifting theorems such as [10] for the randomized lower bounds with the query-to-communication simulation of Buhrman, Cleve, and Wigderson [8] for the quantum upper bounds.

The resulting quantum protocols are, however, highly interactive. In the standard measure of two-way quantum communication complexity, only the total amount of communication is counted, while the number of rounds is unrestricted. As illustrated above for disjointness, the BCW simulation implements each quantum query through an Alice-to-Bob-to-Alice exchange and hence uses two rounds per query. The later disjointness protocols and the cheat-sheet-based upper bounds follow the same distributed-query paradigm. Consequently, their round complexity scales with the sequential query complexity of the underlying quantum algorithms, which is polynomial in the input length in all previously known constructions.

This motivates the following question:

Can a total function exhibit a polynomial quantum advantage in communication complexity
using only a constant number of rounds of quantum communication?

We answer the question above affirmatively. To the best of our knowledge, this gives the first polynomial quantum advantage for a total function using only a constant number of messages. We denote by $Q^{r}_{cc}(f)$ the $r$-round quantum communication complexity for $f$.

Our result is a power $3/2-1/(4t)$ separation. In particular, setting $t=1$ gives a 4-round protocol and a power $5/4$ separation. More generally, for every constant $\varepsilon>0$, choosing a sufficiently large but fixed $t$ gives a constant-round separation of power $3/2-\varepsilon$. Moreover, our $2t+2$-round communication protocol consists of $2t$-round quantum communication and subsequent $2$-round classical communication. In particular, our 4-round communication involves only $2$-round quantum communication.

As an immediate consequence of Theorem 1.1, we also obtain an exponential round separation in bandwidth-limited distributed computing. On a two-node network, a $T$-round algorithm for the CONGEST model with bandwidth $B$ can be viewed as a two-party communication protocol with $T$-rounds of $B$ (qu)bits communication.

In particular, when $t=1$, this gives a 4-rounds quantum algorithm and an $\widetilde{\Omega}(\sqrt{n})$ classical round lower bound.

We use the partial function $\mathscr{F}_{n}$ from Sherstov, Storozhenko, and Wu [20] (or equivalently the corresponding result of Bansal and Sinha [5]). For every fixed $t$, this function can be computed with $t$ quantum queries and constant advantage, while its randomized query complexity is

Following the cheat-sheet construction of Aaronson, Ben-David, and Kothari [3], we then compose $\mathscr{F}_{n}$ with the $\wedge\!\vee_{n}$ tree and add a cheat-sheet array, obtaining a total query function $\mathscr{G}_{n}$. This amplifies the randomized query lower bound to

We finally compose every input bit of $\mathscr{G}_{n}$ with an inner-product gadget $\mathsf{IP}_{m}$, where $m=\Theta(\log n)$. The randomized lifting theorem of [10] transfers the query lower bound to randomized communication complexity. The construction of $\mathscr{G}_{n}\circ\mathsf{IP}_{m}$ and its randomized lower bound follow the standard cheat-sheet and lifting framework. Our contribution is the constant-message quantum protocol described next.

For our quantum upper bound, consider one of the $10\log n$ instances of $\mathscr{F}_{n}\circ\wedge\!\vee_{n}\circ\mathsf{IP}_{m}$. The $j$-th input bit seen by $\mathscr{F}_{n}$ is the value of an $\wedge\!\vee_{n}$ tree whose leaves are inner-product gadgets distributed between Alice and Bob. To simulate a coherent query to this bit, Alice sends the query index, the target qubit, and a coherent copy of her entire block for the queried $\wedge\!\vee_{n}$ instance. Bob computes all relevant inner products, evaluates the $\wedge\!\vee_{n}$ tree into the target qubit, and returns the registers. Alice then uncomputes her block. This is a direct BCW-style simulation: by sending her entire block, Alice enables Bob to evaluate the inner $\wedge\!\vee_{n}$ function exactly within a single Alice-to-Bob-to-Alice exchange.

After the address has been computed, the remaining two messages are classical. Alice sends Bob her inner-product blocks for the addressed cheat-sheet cell, allowing Bob to reconstruct its contents. Bob then sends Alice the certificates together with his shares of the input bits referred to by them. Alice verifies the $\wedge\!\vee_{n}$ certificates against the reconstructed input bits, thereby checking both their claimed values and the promise condition for $\mathscr{F}_{n}$. Alice checks that the addressed cell contains valid certificates for the tentative address. This final verification ensures correctness even for arbitrary cheat-sheet contents and promise-violating inputs, as required because $\mathscr{G}_{n}$ is a total function.

Our work is closely related to two lines of research. The first is the study of parallel (non-adaptive) quantum query complexity. Carolan, Gilani, and Vempati [9] used the cheat-sheet framework to obtain a quantum advantage with a constant number of rounds of parallel queries. Their motivation is different from ours: they study the power of parallel quantum queries, whereas we ask whether a quantum advantage in communication complexity requires many rounds of interaction. Nevertheless, the resulting algorithms share a similar high-level structure. In both settings, many quantum queries are arranged into a constant number of sequential stages, with all queries within each stage performed in parallel. In our communication setting, all queries in one such stage are simulated together through a single Alice-to-Bob-to-Alice exchange. Consequently, the number of communication rounds is determined by the number of parallel query stages rather than by the total number of queries. Our protocol then uses two additional classical messages to read the addressed cheat-sheet cell and verify the certificates contained in it.

The second is the study of bounded-round quantum communication complexity for set disjointness. Jain, Radhakrishnan, and Sen [14] showed that any $r$-round quantum protocol for $\mathsf{DISJ}_{n}$ requires $\Omega(n/r^{2})$ communication. Braverman et al. [6] subsequently improved this bound to $\widetilde{\Omega}(n/r+r)$, obtaining a near-optimal round and communication tradeoff. In particular, any constant-round quantum protocol for $\mathsf{DISJ}_{n}$ requires $\Omega(n)$ communication. Thus, the unrestricted-round quadratic quantum advantage for disjointness disappears in the constant-round setting. Our result shows that this phenomenon is not universal: a total function can exhibit a polynomial quantum advantage even when the number of rounds is bounded by a constant.

Independently and concurrently with our work, Gavinsky [11] showed a total function that admits a 2-round quantum protocol with poly-logarithmic communication complexity and requires polynomial randomized communication complexity, which is stronger than our result.