Source-linked AI summary
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova
TL;DR
The paper asks how one-way communication costs for f-Boolean Hidden Partition depend on the Boolean function f, extending the parity-focused Hidden Matching setting. It proves bounds in terms of sign degree, showing polynomial quantum advantage for every d ≥ 2 and exponential separation when d = 2.
Problem
The existence of exponential quantum–classical separations appears sensitive to the predicate applied to blocks, motivating a broader characterization for f-Boolean Hidden Partition.
Source: §1 · p. 2Method
The paper proves communication bounds using Fourier analysis and hypercontractivity tools for correlated inputs, and sign-representing polynomials for upper bounds.
Source: §1.2 · p. 4, §1.4 · p. 10Results
For every d ≥ 2, classical complexity is Θ(n^(1−1/d)), while quantum complexity lies between Ω(n^(1−2/d)) and O(n^(1−1/⌈d/2⌉) log n).
Source: §1.2 · p. 3Takeaways & Limitations
Sign degree characterizes exponential quantum advantage at d = 2, while every sign degree at least two gives at least polynomial quantum advantage.
Source: §1.2 · p. 3The lower-bound method for controlling correlation breaks down when analyzing many blocks together, where the remaining permutation can retain 2^Θ(|U|) correlation with Alice’s input.
Source: §1.3 · p. 5
Abstract
from arXiv · showhide
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 $\Omega(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 $\Theta(n^{1-1/d})$ while its quantum communication complexity lies between $\Omega(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$.
1 Introduction
The paper generalizes Boolean Hidden Matching to arbitrary block predicates and identifies sign degree as the parameter governing classical and quantum one-way communication complexity. It establishes classical bounds and characterizes quantum advantage, using sign-representing polynomials to develop classical bit-sampling and quantum parity-sampling protocols alongside lower-bound techniques for correlated inputs.
1 Introduction
- Prior work showed that larger parity blocks weaken the exponential quantum advantage, motivating broader predicates; Doriguello and Montanaro [DM20] introduced f-BHP but left its function-by-function classification incomplete.The paper closes gaps in that characterization and expands the family of exponential separations.Source: §1 · p. 2
1.1 The f-Boolean Hidden Partition Problem
- In f-BHP, Alice holds x and Bob holds a permutation and labels; on permuted k-bit blocks, all f-values either match all labels or oppose them, and Bob must decide which.The problem extends Boolean Hidden Matching by allowing any Boolean function f to combine each block.Source: §1.1 · p. 2, §1 · p. 2
1.2 Our Results
- For sign degree d≥2, classical complexity is Θ(n^(1−1/d)); quantum complexity is eΘ(n^(1−2/d)) for even d.For odd d, quantum complexity lies between Ω(n^(1−2/d)) and O(n^(1−1/ceil(d/2)) log n); at d=2 the bounds give Θ(√n) classical versus O(log n) quantum communication, while d≥3 gives polynomial quantum advantage.Source: §1.2 · pp. 3–4
1.3 Proof Overview: Lower Bound
- The lower-bound approach addresses correlations between Alice’s input and Bob’s permutation, which invalidate standard independent-input arguments, by analyzing conditional information about successive blocks.Fourier analysis and hypercontractivity underpin the bounds; the paper’s tools allow significant correlation between Alice and Bob.Source: §1.2 · p. 4, §1.3 · p. 5
1.3.1 Quantum Lower Bound
- Conditioning away other blocks preserves a density-matrix representation, and averaging over the random permutation connects conditional f-expectations to degree-at-least-d parities, yielding an Ω(n^(1−2/d)) quantum threshold.The argument uses matrix hypercontractivity and shows that below this message length Bob’s total advantage cannot be constant.Source: §1.3.1 · pp. 6–7
1.3.2 Classical Lower Bound
- Alice must send Ω(n^(1−1/d)) classical bits for Bob to succeed with probability 2/3.The lower-bound argument controls Bob’s squared posterior advantage over random guessing.Source: §1.3.2 · pp. 8, 10
- The classical proof controls squared posterior terms despite partial-support Fourier ratios that can grow arbitrarily large, using recursion and averaging over messages.The recursion handles large Fourier coefficients by restricting coordinates, while message averaging bounds the overall posterior contribution.Source: §1.3.2 · pp. 8, 10
1.4 Proof Overview: Upper Bound
- A degree-d sign-representing polynomial reduces the task to estimating sums of within-block parities, and classical sampling needs Θ(n^(1−1/d)) bits to learn a constant number of size-d parity copies.Alice sends identities of sampled input bits; each size-d parity is learned with probability (c/n)^d, up to a log factor.Source: §1.4 · pp. 10–11
- O(n^(1−1/⌈d/2⌉) log n) qubits suffice by sampling size-two parities, grouping each target parity into pairs and possibly a singleton.Repeating the procedure yields enough samples for Bob to estimate the polynomial’s desired quantity.Source: §1.4 · p. 11
2 The f-Boolean Hidden Partition Problem
The f-Boolean Hidden Partition game gives Alice an n-bit input and Bob a permuted set of disjoint k-bit blocks with labels; Bob must distinguish whether every block’s f-value agrees with or opposes its label. The section also defines sign degree, the polynomial-complexity parameter used for f.
2 The f-Boolean Hidden Partition Problem
- The instance uses n-bit x, a permutation σ, αn/k blocks of size k, and a label string y of length αn/k.The parameters satisfy αn/k is an integer; σ induces each block’s substring from x.Source: §2 · p. 11
- Bob must distinguish whether all block evaluations of f agree with their labels or all disagree, after receiving one message from Alice.These are the promised YES and NO cases.Source: §2 · p. 12
- Sign degree deg±(f) is the least total degree of a real polynomial whose sign represents the Boolean function f.It is also called threshold degree.Source: §2 · p. 12
- Sign degree is at least d exactly when some probability distribution q makes f have zero correlation with every parity χS of degree below d.The condition is E[f(x)χS(x)] = 0 for every |S| < d.Source: §2 · p. 12
3 Lower Bounds
The lower bounds use a hard distribution where f is uncorrelated with all parities of degree below d. Under this distribution, classical communication requires Ω(n^(1−1/d)) bits and quantum communication requires Ω(n^(1−2/d)) qubits for constant error.
3.1 Hard Distribution
- The hard distribution samples x from Q and chooses labels so all block evaluations either match them or all disagree, with equal probability.Q makes f uncorrelated with every parity of degree less than d.Source: §3.1 · pp. 12–13
3.2 Fourier Analysis and Hypercontractivity
- Fourier analysis and hypercontractivity provide tools for bounding the low-degree contributions used in the lower-bound arguments.The section introduces the noise operator and a matrix-valued hypercontractivity result for density-matrix-valued functions.Source: §3.2 · pp. 13–14
3.3 Classical Lower Bound
- Ω(n^(1−1/d)) classical bits are necessary for constant advantage under the hard distribution.Theorem 7 bounds success by 1/2 + ε when the message is below ε^(2/d)n^(1−1/d)/D bits.Source: §3.3 · p. 14
3.3.1 Proof of Lemma 8
- The classical proof bounds how much Alice’s message can change Bob’s conditional expectation of each block output given earlier block outputs.Lemma 8 supplies this conditional-expectation bound; the proof then uses it to bound Bob’s advantage.Source: §3.3 · p. 15, §3.3.1 · p. 16
3.3.2 Proof of Lemma 9
- The proof of Lemma 9 proceeds by induction and uses the low-degree orthogonality of f under q.The lemma’s setup requires the q-weighted Fourier coefficients of f to vanish below degree d.Source: §3.3.1 · p. 17, §3.3.2 · p. 18
3.4 Quantum Lower Bound
- Ω(n^(1−2/d)) quantum qubits are necessary for constant advantage under the hard distribution.Theorem 10 bounds success by 1/2 + ε when the message is below ε^(2/d)n^(1−2/d)/D qubits.Source: §3.4 · pp. 21–22
3.4.1 Proof of Lemma 11
- The quantum proof bounds the distinguishing power of Bob’s message by analyzing conditional density matrices for the two label cases.The proof develops a quantum analogue of the classical conditional-expectation lemma for these message states.Source: §3.4 · p. 21
4 Upper Bounds
The upper bounds use sampling for a classical protocol and fingerprint states for a quantum protocol. They yield O(n^(1−1/d)) classical bits and, for constant α, k, and ε, O(n^(1−1/⌈d/2⌉) log n) quantum communication.
4.1 Classical Upper Bound
- O(n^(1−1/d)) bits suffice for constant error in the randomized classical protocol.Alice samples coordinates at rate q = Cn^(−1/d) and sends their values; Bob uses them to estimate the sign-representing polynomial on the blocks.Source: §4.1 · pp. 24–25
4.2 Quantum Upper Bound
- O(n^(1−1/⌈d/2⌉) log n) quantum communication suffices when α, k, and ε are constant.The protocol uses fingerprint-state copies and samples Fourier monomials, pairing their positions so pair products can be recovered from measurements.Source: §4.2 · pp. 26, 27, 29
- The quantum protocol pads each sampled monomial with dummy positions, then uses a birthday collision to recover its paired products on one block.A block receiving all r distinct pair labels is found with constant probability using O(m^(1−1/r)) samples, where r = ⌈d/2⌉.Source: §4.2 · pp. 26–28
6 AI Disclosure
The authors disclose two GPT-6 Astra contributions to the paper’s ideas and state that humans wrote its proofs and other text. AI tools were also used for error checking.
6 AI Disclosure
- GPT-6 Astra contributed the idea of conditioning on earlier blocks instead of bounding every odd parity of block outputs.The authors also credit it with the recursive classical argument addressing quadratic dependence on Q/N.Source: §6 · p. 29
- Humans wrote the proofs and the paper’s other text.Source: §6 · p. 29
- AI tools were used to help find typos, bugs, and other errors.Source: §6 · p. 29