We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $Ω(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function.
We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.
We study the one-way communication complexity of the f-Boolean Hidden Partition problem. Here, Alice is given an n-bit string and Bob is given Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of f on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where f is the parity function.
We establish classical and quantum communication bounds for f-Boolean Hidden Partition in terms of the sign degree d of f, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1 and quantum protocols when d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every f of sign degree d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d) and \bOn1−1/⌈d/2⌉logn. This completely characterizes the functions f admitting polynomial quantum advantage as those for which d≥2, with a new infinite family of exponential separations given by the case d=2.
We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an n-qubit quantum one-way protocol, whereas every randomized two-way protocol requires Ω(2n) bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an n-qubit quantum one-way protocol, while every randomized one-way protocol requires Ω(2n) bits of communication.
We also construct a family of efficiently verifiable total search problems achieving an n versus Ωd(nd) separation between quantum one-way and randomized one-way communication for every fixed d≥2. In the quantum protocol, Alice prepares her message using a single unitary from the dth level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For d=2, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage.
Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.
We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function f on length-n strings over a fixed alphabet of size q, invariant under simultaneous coordinate permutations, we prove Rpub(f)=Oq(tlog(2+n/t)), where t=min{n,Q∗(f)2}, Rpub denotes public-coin randomized communication complexity, and Q∗ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed ε∈(0,1), there are binary permutation-invariant partial functions with quantum communication complexity Oε(loglogn) and randomized communication complexity Ωε((logn)1−ε). We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor.
Growing alphabets and graph symmetries admit exponential separations. For every fixed ε∈(0,1), we exhibit permutation-invariant partial functions on length-n strings over an n-symbol alphabet with quantum communication complexity Oε(logn) and randomized communication complexity Ωε(n1−ε). For graph-invariant partial functions on v-vertex graphs, we obtain Oε(logv) quantum versus Ωε(v2−ε) randomized communication complexity. All separation protocols require no prior entanglement.
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form F(x,y)=f(x1∧y1,…,xn∧yn), when the outer function f is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors.
In this work, we settle this problem in a strong way. We show that for every Boolean function f, the bounded-error quantum and classical deterministic communication complexities of the function f∘AND2 are polynomially related, up to polylogarithmic factors in n. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of f.
Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement.
We first introduce XOR Equality, a total Boolean function in which each of k players receives an unrestricted string xj∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0n. For k≥8 and worst-case error at most 1/3, we prove quantum lower bounds of Ω(min{n,k2}) on total communication and Ω(min{n/k,k}) on maximum message length. A classical public-coin protocol uses two bits per player with error at most 1/4. For n=k2 and worst-case error at most 1/3, we prove that quantum protocols require maximum message length Ω(n) qubits, whereas two public-coin bits per player suffice.
We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a k-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(0,1/8), we also prove a bounded-error quantum lower bound of Ω(n(k−1)/(k+1)) while we show that public-coin protocols solve the relation unambiguously with maximum message length O(logn), giving exponential separations in both regimes. The implicit constants are independent of k, and both quantum lower bounds become linear when k≥clogn for any fixed c>0.
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions fn:{0,1}n×{0,1}n→{0,1} that can be computed with O(logn) bits of one-way classical communication given prior entanglement, but that require Ω(n1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.