arXiv:2610.06789
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova
Abstract
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$.
AI Summary
The paper asks which Boolean predicates preserve quantum advantage in generalizations of Boolean Hidden Matching. In the $f$-Boolean Hidden Partition problem, Alice receives an $n$-bit string; Bob receives disjoint ordered blocks of $k$ indices and labels promised either to agree with every blockwise evaluation of $f$ or to disagree with all of them. Alice sends one classical or quantum message to distinguish these cases. For fixed $f$ and block density $\alpha\in(0,1)$, the controlling parameter is the sign degree $d=\deg_\pm(f)$. For every $d\ge2$, randomized classical communication is $\Theta(n^{1-1/d})$. Quantum communication is bounded below by $\Omega(n^{1-2/d})$ and above by $O(n^{1-1/\lceil d/2\rceil}\log n)$. Together with existing logarithmic protocols at low sign degree, these bounds identify $d=2$ as exactly the regime with exponential quantum advantage and $d\ge2$ as exactly the regime with polynomial advantage. The lower bounds resolve a conjecture replacing earlier dependence on pure high degree with sign degree. The lower-bound construction uses a dual witness for sign degree to define a hard distribution correlating Alice’s input with Bob’s partition. Fourier analysis and scalar or matrix hypercontractivity are applied after conditioning on earlier block outputs; a recursive argument handles witness distributions without full support in the classical case. Upper bounds estimate a sign-representing polynomial using random coordinate samples classically and fingerprint-state pair-parity measurements with birthday collisions quantumly. Quantum bounds match up to logarithmic factors for even $d$; an exponent gap remains for odd $d$. Constants can depend on $f$ and $\alpha$.
However, two key ideas came from GPT-6 Astra.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.