Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.06789

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova

quant-phcs.CCSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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$.

No sign of AI-generated textAI use disclosed
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.

Related papers

Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem

João Fernando Doriguello, Ashley Montanaro

In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. In this problem, Alice’s bits are matched into pairs according to a partition that Bob holds. These pairs are compressed using a Parity function and it is promised that the final bit-string is equal either to another bit-string Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function f. Efficient communication protocols are presented depending on the sign-degree of f. If its sign-degree is less than or equal to 1, we show an efficient classical protocol. If its sign-degree is less than or equal to 2, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions f of sign-degree greater than or equal to 2, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function f whose pure high degree is greater than or equal to 2. Similarly, we prove, also via Fourier analysis, a quantum lower bound for any function f whose pure high degree is greater than or equal to 3. These results give a large family of new exponential classical-quantum communication separations.

arXiv:2001.05553•Leibniz international proceedings in informatics•Jan 1, 2020•4 citations

Exponential Separation of Quantum and Classical One-Way Communication Complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM$_n$: Alice gets as input a string ${\bf x}\in\{0, 1\}^n$, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple $\langle i,j,b \rangle$ such that the edge $(i,j)$ belongs to the matching M and $b=x_i\oplus x_j$. We prove that the quantum one-way communication complexity of HM$_n$ is $O(\log n)$, yet any randomized one-way protocol with bounded error must use $\Omega({\sqrt{n}})$ bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HM$_n$, we show that the quantum one-way communication complexity remains $O(\log n)$ and that the 0-error randomized one-way communication complexity is $\Omega(n)$. We prove that any randomized linear one-way protocol with bounded error for this problem requires $\Omega(\sqrt[3]{n \log n})$ bits of communication.

SIAM Journal on Computing•Jan 1, 2008•57 citations

Optimal and Verifiable Quantum Advantages in Communication Complexity

Ryan Anselm, Michelle Ding, Dar Gilboa +1 more

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 $Ω(2^n)$ 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 $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th 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.

quant-pharXiv:2610.05585•Oct 6, 2026•0 citations

The one-way communication complexity of the Boolean Hidden Matching Problem

Iordanis Kerenidis, Ran Raz

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].

arXiv:quant-ph/0607173•Jul 25, 2006•21 citations

Exponential separation of quantum and classical one-way communication complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•111 citations

Quantum-Classical Equivalence for AND-Functions

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2 more

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(x_1 \land y_1, \ldots, x_n \land y_n), $$ 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 \circ \mathrm{AND}_2$ 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.

cs.CCCross-listedarXiv:2606.03249•Leibniz international proceedings in informatics•Jun 3, 2026•0 citations
We study the one-way communication complexity of the fff-Boolean Hidden Partition problem. Here, Alice is given an nnn-bit string and Bob is given Ω(n)Ω(n)Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of fff 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 fff is the parity function.
We establish classical and quantum communication bounds for fff-Boolean Hidden Partition in terms of the sign degree ddd of fff, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1d \le 1d≤1 and quantum protocols when d≤2d \le 2d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every fff of sign degree d≥2d \ge 2d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d)Θ(n^{1-1/d})Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d)Ω(n^{1-2/d})Ω(n1−2/d) and \bOn1−1/⌈d/2⌉log⁡n\bO{n^{1-1/\lceil d/2 \rceil} \log n}\bOn1−1/⌈d/2⌉logn. This completely characterizes the functions fff admitting polynomial quantum advantage as those for which d≥2d \ge 2d≥2, with a new infinite family of exponential separations given by the case d=2d = 2d=2.
The paper asks which Boolean predicates preserve quantum advantage in generalizations of Boolean Hidden Matching. In the fff-Boolean Hidden Partition problem, Alice receives an nnn-bit string; Bob receives disjoint ordered blocks of kkk indices and labels promised either to agree with every blockwise evaluation of fff or to disagree with all of them. Alice sends one classical or quantum message to distinguish these cases.
For fixed fff and block density α∈(0,1)\alpha\in(0,1)α∈(0,1), the controlling parameter is the sign degree d=deg⁡±(f)d=\deg_\pm(f)d=deg±​(f). For every d≥2d\ge2d≥2, randomized classical communication is Θ(n1−1/d)\Theta(n^{1-1/d})Θ(n1−1/d). Quantum communication is bounded below by Ω(n1−2/d)\Omega(n^{1-2/d})Ω(n1−2/d) and above by O(n1−1/⌈d/2⌉log⁡n)O(n^{1-1/\lceil d/2\rceil}\log n)O(n1−1/⌈d/2⌉logn). Together with existing logarithmic protocols at low sign degree, these bounds identify d=2d=2d=2 as exactly the regime with exponential quantum advantage and d≥2d\ge2d≥2 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 ddd; an exponent gap remains for odd ddd. Constants can depend on fff and α\alphaα.
In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. In this problem, Alice’s bits are matched into pairs according to a partition that Bob holds. These pairs are compressed using a Parity function and it is promised that the final bit-string is equal either to another bit-string Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function f. Efficient communication protocols are presented depending on the sign-degree of f. If its sign-degree is less than or equal to 1, we show an efficient classical protocol. If its sign-degree is less than or equal to 2, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions f of sign-degree greater than or equal to 2, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function f whose pure high degree is greater than or equal to 2. Similarly, we prove, also via Fourier analysis, a quantum lower bound for any function f whose pure high degree is greater than or equal to 3. These results give a large family of new exponential classical-quantum communication separations.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn_nn​: Alice gets as input a string x∈{0,1}n{\bf x}\in\{0, 1\}^nx∈{0,1}n, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple ⟨i,j,b⟩\langle i,j,b \rangle⟨i,j,b⟩ such that the edge (i,j)(i,j)(i,j) belongs to the matching M and b=xi⊕xjb=x_i\oplus x_jb=xi​⊕xj​. We prove that the quantum one-way communication complexity of HMn_nn​ is O(log⁡n)O(\log n)O(logn), yet any randomized one-way protocol with bounded error must use Ω(n)\Omega({\sqrt{n}})Ω(n​) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn_nn​, we show that the quantum one-way communication complexity remains O(log⁡n)O(\log n)O(logn) and that the 0-error randomized one-way communication complexity is Ω(n)\Omega(n)Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(nlog⁡n3)\Omega(\sqrt[3]{n \log n})Ω(3nlogn​) bits of communication.
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 nnn-qubit quantum one-way protocol, whereas every randomized two-way protocol requires Ω(2n)Ω(2^n)Ω(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 nnn-qubit quantum one-way protocol, while every randomized one-way protocol requires Ω(2n)Ω(2^n)Ω(2n) bits of communication. We also construct a family of efficiently verifiable total search problems achieving an nnn versus Ωd(nd)Ω_d(n^d)Ωd​(nd) separation between quantum one-way and randomized one-way communication for every fixed d≥2d \ge 2d≥2. In the quantum protocol, Alice prepares her message using a single unitary from the dddth 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=2d = 2d=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 give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.
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), F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), F(x,y)=f(x1​∧y1​,…,xn​∧yn​), when the outer function fff 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 fff, the bounded-error quantum and classical deterministic communication complexities of the function f∘AND2f \circ \mathrm{AND}_2f∘AND2​ are polynomially related, up to polylogarithmic factors in nnn. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of fff. 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.