Which Functions Admit Polynomial Quantum Advantage in Boolean Hidden Partition?

Sign degree decides the classical-quantum split

The paper studies the one-way communication complexity of f-Boolean Hidden Partition (f-BHP). Alice holds an n-bit string x; Bob holds Ω(n) disjoint blocks of its indices plus a string of labels y. The promise is that evaluating f on each block either agrees with every label or disagrees with every label, and Bob must decide which case holds using a single message from Alice.

The parameter that governs the answer is the sign degree of f, written deg±(f). A polynomial p sign-represents f when p(z)f(z) > 0 for every input z, and the sign degree is the minimum degree of such a polynomial. The paper confirms that this quantity, not the pure high degree used in earlier lower bounds, is what determines both classical and quantum complexity across the whole f-BHP family.

Classical complexity is tight at Θ(n^(1−1/d))

For every f with sign degree d ≥ 2, the randomized classical communication complexity of f-BHP is Θ(n^(1−1/d)). The lower bound Ω(n^(1−1/d)) resolves a conjecture of Doriguello and Montanaro, who had proved such bounds only in terms of the pure high degree, a quantity that is at most the sign degree but can be much smaller.

The matching upper bound O(n^(1−1/d)) shows the classical complexity is pinned down up to constant factors. This is a statement about randomized classical protocols sending bits; it does not by itself say anything about quantum messages, which are measured in qubits.

Quantum bounds are tight for even sign degree

The quantum communication complexity of f-BHP lies between Ω(n^(1−2/d)) and O(n^(1−1/⌈d/2⌉) log n). For even d, these two expressions coincide up to logarithmic factors, so the quantum complexity is Θ̃(n^(1−2/d)). For odd d, a gap remains between the lower bound Ω(n^(1−2/d)) and the upper bound O(n^(1−1/⌈d/2⌉) log n).

The lower bound Ω(n^(1−2/d)) applies for sign degree d ≥ 3, while the upper bound O(n^(1−1/⌈d/2⌉) log n) applies for every d ≥ 2. The paper is explicit that the odd-d case is not fully resolved, so the quantum complexity there is characterized only up to the stated interval.

Three regimes of sign degree

Combining the new bounds with the earlier results of Doriguello and Montanaro splits the f-BHP family into three regimes. When deg±(f) ≤ 1, logarithmic classical communication already suffices. When deg±(f) = 2, the classical complexity is Θ(√n) while a quantum protocol uses only O(log n) qubits, an exponential separation. When deg±(f) ≥ 3, quantum communication itself must be polynomial in n, but it always remains polynomially smaller than classical communication.

The functions of sign degree two are therefore exactly those yielding an exponential separation between classical and quantum one-way communication complexity, and every sign degree of at least two yields at least a polynomial quantum advantage. The case d = 2 supplies a new infinite family of exponential separations.

Why correlated inputs break the standard tools

The lower bounds use Boolean Fourier analysis and hypercontractivity, the standard toolkit for one-way communication lower bounds. The obstacle is that the hard distribution for f-BHP requires Alice's input on a block to be drawn from a distribution q tied to f, which makes the block permutation σ correlated with Alice's input. The paper notes that message-permutation pairs can be 2^Θ(n) times more likely than the product of their marginals, and many pairs can have zero probability of co-occurring.

Standard arguments assume the parities Bob cares about are independent of Alice's message, and they break once that independence is lost. The paper's technical contribution is a set of tools that tolerate significant correlation between Alice and Bob, which the authors expect to be useful for other one-way problems that are too easy under independent inputs.

Revealing blocks one at a time

Instead of bounding every odd parity of the block outputs f(x_i), the proof reveals f(x_1), f(x_2), … one block at a time and asks how much Bob learns about f(x_i) conditional on the earlier blocks, before he looks at y_i. If Bob has learned anything about the vector of block values, he must have learned something about these conditional single-block values, even when he has learned nothing about any given block unconditionally.

The dual characterization of sign degree supplies the starting point: if f has sign degree d, there is a distribution q on {±1}^k such that E_{z∼q}[f(z)χ_S(z)] = 0 for every |S| < d. Sampling a block from q therefore makes any subset of fewer than d bits uninformative about f on that block. The paper also credits two key ideas to GPT-6 Astra: analyzing individual blocks conditional on earlier blocks, and the recursive argument used in the classical case to handle the quadratic dependence on Q/N.

How the quantum protocol reaches its bound

The upper bound comes from a protocol in which Alice sends copies of a fingerprint state |ψ_x⟩, each carrying O(log n) qubits. Bob measures each copy in a basis adapted to his blocks and a sampled Fourier monomial S of size r, learning one random pair-product u_{i,ℓ} per useful outcome. A generalized birthday argument shows that after O((k/α)^{1/r} n^{1−1/r}) copies, some block J receives r distinct pair labels with probability at least 2/3, letting Bob reconstruct χ_S(x_J) as the product of those pair-products.

Bob then forms Z = ‖p̂‖_1 sgn(p̂(S)) y_J χ_S(x_J), which has expectation at least 2β/3 under the promise, where β is the margin of the sign-representing polynomial. Repeating the trial R = ⌈9‖p̂‖_1^2 / (2β^2) ln(1/ε)⌉ times and taking the sign of the sum drives the error below ε by Hoeffding's inequality. The total communication is O((‖p̂‖_1^2/β^2)(k/α)^{1/⌈d/2⌉} n^{1−1/⌈d/2⌉} log n log(1/ε)) qubits.

What the characterization does not settle

The classical side is fully determined: Θ(n^(1−1/d)) for every d ≥ 2. The quantum side is tight only for even d; for odd d the complexity is known only to lie between Ω(n^(1−2/d)) and O(n^(1−1/⌈d/2⌉) log n), so the exact exponent remains open. The bounds are stated for the f-BHP promise problem with α ∈ (0,1) and k | αn, and the upper bound carries logarithmic factors and constants depending on the sign-representing polynomial's margin β and ℓ_1 norm.

The most decision-relevant threshold is sign degree two. That is the unique regime where classical communication is Θ(√n) while quantum communication is O(log n), so d = 2 is where the exponential separation lives; d ≥ 3 still gives a polynomial quantum advantage, but no longer an exponential one. Readers comparing candidate functions f should therefore check deg±(f) first, since it alone separates the logarithmic, exponential, and polynomial regimes.

Sources used in this answer