Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
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 ≤ 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 ⌉ log n. 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.
Related
- Quantum Query Complexity of Maximum Degree and its Generalizations
- Exponential advantage in continuous-variable quantum state learning
- Quantum metrological advantage of high-order squeezed states
- A Framework for Quantum Advantage
- Constant-round quantum advantage in communication complexity for total functions
BibTeX
@misc{bun2026characterizing,
title = {{Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem}},
author = {Mark Bun and Joao F. Doriguello and John Kallaugher and Nadezhda Voronova},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06789},
eprint = {2610.06789},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06789},
}
RIS
TY - UNPB
TI - Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
AU - Mark Bun
AU - Joao F. Doriguello
AU - John Kallaugher
AU - Nadezhda Voronova
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06789
UR - https://arxiv.org/abs/2610.06789
AB - 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 Θ(n^1−1/d) while its quantum communication complexity lies between Ω(n^1−2/d) and bOn^1−1/⌈ d/2 ⌉ log n. 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.
ER -