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:0902.3175 · Chicago Journal of Theoretical Computer Science

The One-Way Communication Complexity of Group Membership

Scott Aaronson, François Le Gall, Alexander C. Russell, Seiichiro Tani

Published Jan 1, 2011• 4 citations
arXivHTMLPDF

Abstract

This paper studies the one-way communication complexity of the subgroup membership problem, a classical problem closely related to basic questions in quantum computing.Here Alice receives, as input, a subgroup H of a finite group G; Bob receives an element y ∈ G. Alice is permitted to send a single message to Bob, after which he must decide if his input y is an element of H.We establish the following bounds on the classical communication complexity of this problem in the bounded-error setting:1.The problem can be solved with O(log |G|)-bit communication with the promise that H is normal.2. The problem can be solved with O(d max • log |G|)-bit communication, where d max is the maximum degree of an irreducible complex representation of G.3. For any prime p not dividing |G|, the problem can be solved with O(log |G| + d max • log p)-bit communication, where d max is the maximum degree of an irreducible F p -representation of G.

DOI
10.4086/cjtcs.2011.006

Related papers

On relating one-way classical and quantum communication complexities

Naresh Goud Boddu, Rahul Jain, Han-Hsuan Lin

Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function f(x,y) , where x is given to Alice and y is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results.Let f:X×Y→Z∪{⊥} be a partial function and μ be a distribution with support contained in f−1(Z) . Denote d=|Z| . Let Rϵ1,μ(f) be the classical one-way communication complexity of f ; Qϵ1,μ(f) be the quantum one-way communication complexity of f and Qϵ1,μ,∗(f) be the entanglement-assisted quantum one-way communication complexity of f , each with distributional error (average error over μ ) at most ϵ . We show:1) If μ is a product distribution, η>0 and 0≤ϵ≤1−1/d , then, R2ϵ−dϵ2/(d−1)+η1,μ(f)≤2Qϵ1,μ,∗(f)+O(log⁡log⁡(1/η)). 2)If μ is a non-product distribution and Z={0,1} , then ∀ϵ,η>0 such that ϵ/η+η<0.5 , R3η1,μ(f)=O(Qϵ1,μ(f)⋅CS(f)/η3), where CS(f)=maxyminz&am

arXiv:2107.11623•Quantum•May 22, 2023•5 citations

A new exponential separation between quantum and classical one-way communication complexity

Ashley Montanaro

We present a new example of a partial boolean function whose one-way quantum communication complexity is exponentially lower than its one-way classical communication complexity. The problem is a natural generalisation of the previously studied Subgroup Membership problem: Alice receives a bit string $x$, Bob receives a permutation matrix $M$, and their task is to determine whether $Mx=x$ or $Mx$ is far from $x$. The proof uses Fourier analysis and an inequality of Kahn, Kalai and Linial.

arXiv:1007.3587•Quantum Information and Computation•Jul 1, 2011•14 citations

An exponential separation between entanglement-assisted and unassisted one-way quantum communication

Ryan Anselm, Srijita Kundu, Olivier Lalonde +1 more

A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions $f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ that can be computed with $O(\log n)$ bits of one-way classical communication given prior entanglement, but that require $Ω(n^{1/3})$ qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.

quant-pharXiv:2610.02099•Oct 2, 2026•0 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

New bounds on the classical and quantum communication complexity of some graph properties

Gábor Ivanyos, Hartmut Klauck, Troy Lee +2 more

We study the communication complexity of a number of graph properties where the edges of the graph $G$ are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.

arXiv:1204.4596•Leibniz international proceedings in informatics•Jan 1, 2012•16 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
This paper studies the one-way communication complexity of the subgroup membership problem, a classical problem closely related to basic questions in quantum computing.Here Alice receives, as input, a subgroup H of a finite group G; Bob receives an element y ∈ G. Alice is permitted to send a single message to Bob, after which he must decide if his input y is an element of H.We establish the following bounds on the classical communication complexity of this problem in the bounded-error setting:1.The problem can be solved with O(log |G|)-bit communication with the promise that H is normal.2. The problem can be solved with O(d max • log |G|)-bit communication, where d max is the maximum degree of an irreducible complex representation of G.3. For any prime p not dividing |G|, the problem can be solved with O(log |G| + d max • log p)-bit communication, where d max is the maximum degree of an irreducible F p -representation of G.
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function f(x,y) , where x is given to Alice and y is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results.Let f:X×Y→Z∪{⊥} be a partial function and μ be a distribution with support contained in f−1(Z) . Denote d=|Z| . Let Rϵ1,μ(f) be the classical one-way communication complexity of f ; Qϵ1,μ(f) be the quantum one-way communication complexity of f and Qϵ1,μ,∗(f) be the entanglement-assisted quantum one-way communication complexity of f , each with distributional error (average error over μ ) at most ϵ . We show:1) If μ is a product distribution, η>0 and 0≤ϵ≤1−1/d , then, R2ϵ−dϵ2/(d−1)+η1,μ(f)≤2Qϵ1,μ,∗(f)+O(log⁡log⁡(1/η)). 2)If μ is a non-product distribution and Z={0,1} , then ∀ϵ,η>0 such that ϵ/η+η<0.5 , R3η1,μ(f)=O(Qϵ1,μ(f)⋅CS(f)/η3), where CS(f)=maxyminz&am
We present a new example of a partial boolean function whose one-way quantum communication complexity is exponentially lower than its one-way classical communication complexity. The problem is a natural generalisation of the previously studied Subgroup Membership problem: Alice receives a bit string xxx, Bob receives a permutation matrix MMM, and their task is to determine whether Mx=xMx=xMx=x or MxMxMx is far from xxx. The proof uses Fourier analysis and an inequality of Kahn, Kalai and Linial.
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions fn ⁣:{0,1}n×{0,1}n→{0,1}f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}fn​:{0,1}n×{0,1}n→{0,1} that can be computed with O(log⁡n)O(\log n)O(logn) bits of one-way classical communication given prior entanglement, but that require Ω(n1/3)Ω(n^{1/3})Ω(n1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
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.
We study the communication complexity of a number of graph properties where the edges of the graph GGG are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.
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.