Quantum Communication Complexity of Distributed Set Joins
Stacey Jeffery1 and François Le Gall2

arXiv:1608.06617v1 [quant-ph] 23 Aug 2016

1

Institute for Quantum Information and Matter, California Institute of Technology,
Pasadena, USA, sjeffery@caltech.edu
2
Graduate School of Informatics, Kyoto University, Kyoto, Japan,
legall@i.kyoto-u.ac.jp
August 24, 2016

Abstract
Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht,
Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the
natural model of (classical) two-party communication complexity and obtained tight bounds for
the complexity of several important distributed set joins.
In this paper we initiate the study of the quantum communication complexity of distributed
set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which
corresponds to computing the composition join of two databases, showing that the product of
two n ×√n Boolean matrices, each owned by one of two respective parties, can be computed
e n`3/4 ) qubits of communication, where ` denotes the number of non-zero entries of
with O(
the product. Since √
Van Gucht et al. showed that the classical communication complexity of
e
this problem is Θ(n
`), our quantum algorithm outperforms classical protocols whenever the
output matrix is sparse. We also show a quantum lower bound and a matching classical upper
bound on the communication complexity of distributed matrix multiplication over F2 .
Besides their applications to database theory, the communication complexity of set joins is
interesting due to its connections to direct product theorems in communication complexity. In
this work we also introduce a notion of all-pairs product theorem, and relate this notion to
standard direct product theorems in communication complexity.

1

Introduction

Background Set joins are basic operations in relational database theory. The notion of set
join was introduced to the database community more than forty years ago by Codd [Cod70] to
express operations combining two tables in relational databases. This seminal paper considered,
in particular, the composition join: given two (relational) databases A and B, A represented as
a subset of {1, . . . , m} × {1, . . . , n} and B as a subset of {1, . . . , n} × {1, . . . , m}, the composition
join of A and B is the set {(i, j) | ∃k : (i, k) ∈ A and (k, j) ∈ B} ⊆ {1, . . . , m} × {1, . . . , m}.
Many other join operations have been defined so far and have found many applications (see, e.g.,
[AGK06, Cod70, HM97, LdB07, Mam03, MG03, RPNK00, VWWZ15]).
The computational complexity of join operations is naturally an important issue. Very recently
Van Gucht, Williams, Woodruff and Zhang [VWWZ15] have investigated this question in the twoparty communication complexity model where one party owns the first database, the second party
owns the second database, and both parties collaborate to compute the join of these two databases
1

using as little communication as possible. This model is interesting for two main reasons. First, it
models the natural and practical task of distributed computation of join operations. Second, in the
communication complexity setting it is possible to show strong lower bounds on the complexity of
problems. Indeed, one of the main contributions of [VWWZ15] was to show quantitative differences
between the (communication) complexities of various join operations.
Many join operations studied in database theory actually correspond to fundamental and wellstudied computational tasks in other areas of computer science. The composition join mentioned
above, in particular, corresponds to Boolean matrix multiplication, one central problems in theoretical computer science: if we represent the database A by an m × n matrix MA and B by an
n × m matrix MB (such that MA [i, j] = 1 if and only if (i, j) ∈ A, and similarly for MB ), the matrix
representation of the composition join of A and B is precisely the output of
Wthe Boolean matrix multiplication of MA and MB (i.e., the m × m matrix C such that C[i, j] = nk=1 MA [i, k] ∧ MB [k, j]).
The result by Van Gucht et al. on the communication complexity of the composition
√ join [VWWZ15]
e
shows that the communication complexity of Boolean matrix multiplication is Θ(n
`) for the square
case m = n (a more complicated formula is also given for the rectangular case), where ` denotes
the number of non-zero entries in the product C. Since the parameter ` represents the sparsity of
the output matrix, algorithms and communication protocols with complexity depending explicitly
on ` are sometimes called output-sensitive and have been studied in several settings other than
communication complexity as well [AP09, Bv06, JKLM16, Lin11].
Our Results In this paper we initiate the study of the quantum communication complexity
of distributed set joins. Our main result is about the set joins related to matrix multiplication.
We first show that the quantum communication complexity of the composition join (i.e., Boolean
√
matrix multiplication) is O( n`3/4
√log m) (Theorem 3.4). This is better than the best possible
classical protocol, which costs Ω(n `) as mentioned above. We also consider matrix multiplication
over the binary field and show that its quantum
√ communication complexity (and actually even its
e
classical communication complexity) is O(n `) (Theorem 4.1). We give a matching lower bound
as well (Theorem 4.4).
These bounds are also interesting since they confirm and substantiate our current understanding
of the power of quantum algorithms for problems related to matrix multiplication. Indeed, while
matrix multiplication over a field seems harder than Boolean matrix multiplication for quantum
computers, we currently do not have any technique to prove such a statement in the time complexity
setting. Our results prove this statement in the communication complexity setting, for instances
with sparse output matrices.
In addition to these concrete results, this work presents several interesting new open problems.
An OR lemma is a composition lemma that
says that the quantum communication complexity of
Wm
√
∨m
the function f (a1 , . . . , am , b1 , . . . , bm ) = i=1 f (ai , bi ) is at least Ω( mQ(f )), where Q(f ) is the
quantum communication complexity of f . We show that our upper bound for composition join is
tight up to logarithmic factors assuming the problem of Boolean matrix multiplication satisfies an
OR lemma (Proposition 5.3). We give further evidence that our upper bound is indeed tight by
showing that it is tight at extreme values of `, when ` = O(1) (Proposition 5.1) and when ` = Ω(n2 )
(Proposition 5.2).
We believe that proving lower bounds on set joins is a very interesting area of future research,
as doing so may give insight into direct product theorems in communication complexity, as well
as lower bounds in quantum query complexity for problems that involve read-many formulas, in
which different parts of the input are used multiple times, which makes it difficult to prove lower
bounds using standard composition theorems.

2

Organization The remainder of this paper is organized as follows. In Section 2, we give the
necessary preliminaries, including quantum communication complexity, and the groundwork for
studying the quantum communication complexity of set joins. In Section 3, we present our communication protocol for composition join. In Section 4, we present our classical communication
protocol and matching quantum lower bound for matrix multiplication over F2 . Finally, in Section 5, we give some evidence that our upper bound for composition join is tight, by reducing a
matching lower bound to a plausible OR lemma.

2
2.1

Preliminaries
Notation

Let 2[n] denote the set of subsets of [n]. A subset S of [n] := {1, . . . , n} can be represented by an
n-bit string, and we will sometimes conflate these two notions. Let S[i] denote the i-th bit of the
string corresponding to S, so S[i] = 1 if and only if i ∈ S. For any x ∈ {0, 1}n , we let |x| denote
the Hamming weight, which is the size of the corresponding subset of [n]. Similarly, for a Boolean
matrix A (i.e., a matrix with entries in {0, 1}), let |A| denote the number of 1s in A. Given an
m × n Boolean matrix A and an n × m Boolean matrix B, we write the Boolean product A ∗ B
and let AB denote their product over the finite field F2 = {0, 1}. Morever, for any integer k ∈ [n]
we let A[·, k] denote the k-th column of A and B[k, ·] the k-th row of B.

2.2

Quantum Communication Complexity

A communication problem is a function f : A × B → Y whose input has two parts, a ∈ A, which we
call Alice’s input, and b ∈ B, which we call Bob’s input. In the model of communication complexity,
first defined by Yao [Yao79], Alice and Bob want to run a protocol such that, at the end of the
protocol, Alice and Bob both output f (a, b) with high probability, and they want to minimize the
number of bits they need to communicate in order to achieve this.
In the model of quantum communication, also introduced by Yao [Yao93], Alice and Bob are
allowed a quantum communication channel and they want to minimize the number of quantum bits
(qubits) they need to communicate in order to compute the function. More precisely, a quantum
communication protocol consists of finite inner product spaces X and Y, a measurement {Π, I − Π}
on Y, and unitary operators {Ui }Ti=1 , such that for odd i, Ui acts on X ⊗ C, where C = C2 is
a single-qubit system, and for even i, Ui acts on C ⊗ Y. The protocol is said to have quantum
communication complexity T . The protocol is said to compute f with bounded error 1/3 if for all
(a, b) ∈ A × B, there exist states ρa and ρb on X and Y respectively, such that
| Tr ((IX ⊗ IC ⊗ Π)UT . . . U1 (ρa ⊗ |0ih0| ⊗ ρb )) − f (a, b)| ≤ 1/3.
That is, Alice begins the protocol in some state ρa depending on her input, and Bob begins the
protocol in some state ρb depending on his input, and Alice also has an additional system, C,
initialized to |0i, which will be used for communication with Bob. Alice applies U1 to X ⊗ C, and
then sends C to Bob, who applies U2 to C ⊗ Y, before sending C back to Alice. They continue until
they have applied all T unitaries, at which point, Bob measures Y, and the outcome determines
f (a, b) with error at most 1/3.
The bounded error quantum communication complexity of f , denoted Q(f ), is the minimum T
such that there exists a quantum communication protocol computing f with bounded error 1/3
with quantum communication complexity T . We will also consider the bounded error quantum
communication complexity of partial functions f : D → {0, 1} for D ⊆ A × B.
3

There are many variants of this model, including the setting of one-way communication complexity, in which Alice can send messages to Bob, but Bob cannot send messages to Alice, and only
Bob is required to output the correct answer. We let Q1 (f ) denote the one-way communication
complexity of f .
An important problem in the study of quantum communication complexity is the problem of
set disjointness, which is defined as follows.
Set Disjointness, DISJn
Alice’s input: a ∈ {0, 1}n
Bob’s input: b ∈ {0, 1}nW
Output: DISJn (a, b) = ni=1 ai bi
√
It is well known that Q(DISJn ) = Θ( n) [BCW98, Hd02, AA03, Raz03], beating the classical
communication complexity of Θ(n) [KS92, Raz92]. When one of the two input sets is small, we
can do even better as shown in the following elementary lemma.
Lemma 2.1 (Set disjointness
for small sets).
The bounded error quantum communication complex
q

min{|a|,|b|}
ity of DISJn (a, b) is O
|a∩b|+1 log n . Furthermore, if DISJn (a, b) = 1, then the protocol also
returns a uniform random i ∈ a ∩ b.

Proof. To begin the protocol, Alice sends Bob |a| using d log2 ne bits of communication, and Bob
sends Alice |b| using d log2 ne bits of communication. If |a| < |b|, Alice and Bob perform Grover
search on the set SA = {i ∈ [n] : ai = 1} for an index i ∈PSA such that fB (i) = 1, where
fB (i) = bi . They do this as follows. Alice computes |π(SA )i = i∈SA √1 |ii. In order to perform
|a|
P
the search, Alice and Bob must alternate RA = 2|π(SA )ihπ(SA )| − I and RB = i∈[n] (−1)bi |iihi|,
q

|a|
O
|a∩b|+1 times. Clearly Alice can implement RA , and Bob can implement RB , so they can
q

|a|
implement this algorithm using O
|a∩b|+1 rounds of communication, each time communicating
a d log2 ne-qubit state. Bob measures some i ∈ [n], and sends i, fB (i) to Alice. Both Alice and Bob
output fB (i). If |a| ≥ |b|, they do the protocol obtained by reversing Alice and Bob’s roles.
The algorithm in Lemma 2.1 actually finds a witness i ∈ a ∩ b, which is slightly stronger than
what is required to solve DISJ. We will also consider the problem of finding the entire intersection:
Find-all Set Intersection, DISJalln
Alice’s input: a ∈ {0, 1}n
Bob’s input: b ∈ {0, 1}n
Output: DISJalln (a, b) = {i ∈ [n] : ai = bi = 1}
In this case, we also have an advantage when a or b is small, as shown in the following lemma.
Lemma 2.2 (Find-all set intersection
for small sets). The bounded error quantum communication
p
complexity of DISJalln (a, b) is O( |a ∩ b| min{|a|, |b|} log n).
Proof. Alice and Bob run the following protocol.
1. S ← ∅, ã ← a, b̃ ← b.
2. Repeat:
(a) Use the protocol for DISJn (ã, b̃) to obtain i ∈ ã ∩ b̃. If DISJn (ã, b̃) = 0, output S.
4

(b) S ← S ∪ {i}, ãi ← 0, b̃i ← 0.
This protocol has communication complexity
s
|a∩b|

p
X
min{|a|, |b|}
|a ∩ b| min{|a|, |b|} log n
log n = Θ
|a ∩ b| − i + 1
i=1

qubits.

2.3

Set Joins and Direct Product Theorems

In this paper, we consider various set join problems. For any predicate Pn : 2[n] × 2[n] → {0, 1}, we
can define a set join, as follows.
P-Set Join, Pn⊗m
Alice’s input: A = (A1 , . . . , Am ), Ai ⊆ [n]
Bob’s input: B = (B1 , . . . , Bm ), Bi ⊆ [n]
Output: {(i, j) ∈ [m] × [m] : Pn (Ai , Bj ) = 1}
When Pn is the predicate such that Pn (A, B) = 1 if and only if A ∩ B 6= ∅, the resulting
join is called the composition join or sometimes set-intersection-non-empty join. As mentioned
in the introduction, this join is equivalent to Boolean matrix multiplication, where we consider
A1 , . . . , Am to be the rows of a matrix A ∈ {0, 1}m×n , and B1 , . . . , Bm to be the columns of a
matrix B ∈ {0, 1}n×m .
Consider a related construction: the direct product.
(m)

Direct product, Pn
Alice’s input: A = (A1 , . . . , Am ), Ai ⊆ [n]
Bob’s input: B = (B1 , . . . , Bm ), Bi ⊆ [n]
Output: {i ∈ [m] : Pn (Ai , Bi )}
(m)

Unlike set joins, such problems are well-studied, and much is known. Clearly, we have Q(Pn ) =
O(mQ(Pn ) log m) for any predicate Pn . Intuitively, one can usually expect that the resources needed
to solve m instances of Pn scale as at least m times the resources needed to solve one instance,
(m)
that is: Q(Pn ) = Ω(mQ(Pn )). This is called a (weak) direct product theorem for Pn . In fact, we
(m)
can sometimes prove a stronger statement: that even solving Pn with success probability 2−m
requires Ω(mQ(Pn )) quantum communication. Such a statement is called a strong direct product
theorem. Although such a statement likely holds for many problems in quantum communication
complexity, it can be very difficult to prove (see, e.g., [She12] and the references therein).
In the case of set joins, it is also easy to see that Q(Pn⊗m ) = O(m2 Q(Pn ) log m), however, unlike
the case of direct products, this naive upper bound is often not tight. For example, let Q1 (Pn )
denote the one-way communication complexity of Pn . Then we have the following:
Theorem 2.3. For any predicate Pn , Q(Pn⊗m ) ≤ O(mQ1 (Pn ) log m).
Proof. Consider an optimal one-way quantum communication protocol for Pn . Let ρ(A) be the
mixed state on at most Q1 (Pn ) qubits that Alice sends Bob and let U (B) be the unitary that Bob
applies to ρ(A) ⊗ |0ih0|W ⊗ |0ih0|A , for some workspace W and single-qubit answer register A, so
that he measures Pn (A, B) in the answer register with probability at least 2/3.
5

We construct a (one-way) protocol for Pn⊗m as follows. Let Alice have input A1 , . . . , Am , and
Bob B1 , . . . , Bm . For every i ∈ [m], Alice sends Bob (ρ(Ai ))⊗c log m , where c is a large enough
constant. For each i, j ∈ [m], Bob applies U (Bj )⊗c log m to (ρ(Ai ) ⊗ |0ih0|W ⊗ |0ih0|A )⊗c log m .
He then computes the majority of the answer registers in a new single-qubit
register, which he
P
†
measures. Let ρ(Ai , Bj ) := U (Bj )(ρ(Ai ) ⊗ |0ih0|W ⊗ |0ih0|A )U (Bj ) = b,b0 ∈{0,1} ρb,b0 ⊗ |bihb0 |, so
the state Bob measures is (up to permuting registers):
X

`
O

ρxi ,x0i ⊗ |xihx0 | ⊗ |maj(x)ihmaj(x0 )|,

x,x0 ∈{0,1}` i=1

where maj(x) = 1 if |x| ≥ `/2 and 0 otherwise. Assume that Pn (Ai , Bj ) = 1, as the 0 case is nearly
identical. Then the probability of success in a single round is Tr(ρ1,1 ) ≥ 2/3, so the probability of
success upon measuring the majority register is:
X
x∈{0,1}` :|x|≥`/2

Π`i=1 Tr(ρxi ,xi )

b`/2c 

=

X
k=0


`
Tr(ρ1,1 )k (1 − Tr(ρ1,1 ))`−k ≥ 1 − e−Ω(`) = 1 − m−Ω(1) ,
k

where the inequality follows from Hoeffding’s inequality, and the constant in Ω(1) depends on c.
Thus, Bob gets the correct answer with high probability, but furthermore, this measurement causes
negligible damage to the state ρ(Ai , Bj )⊗` , so Bob can apply (U (Bj )† )⊗` to recover ρ(Ai )⊗` , to be
used again. The error in the state remains negligible as long as Bob does this no more than mO(1)
times.
Call a theorem of the form Q(Pn⊗m ) = Ω(min{mn, m2 Q(Pn )}) a (weak) all-pairs product theorem. The min{mn, ·} is to account for the fact that we always have a trivial upper bound of mn,
and so if we did not include this, the statement would always be false for some values of m and
n. In this work, we give an example of a set-join for which an all-pairs direct product theorem
√
does not hold — in particular, in Section 3 we will give an upper bound of O(m3/2 n) for the
composition join, showing that this problem does not satisfy an all-pairs product theorem. Although we show that such a statement holds for matrix multiplication over F2 , in that case, we
have min{mn, m2 Q(Pn )} = mn for all m and n, so the best strategy is always for Alice to send her
whole input to Bob, rather than for Alice and Bob to compute m2 instances of Pn . It is an open
question whether or not there exists a predicate for which an all-pairs product theorem holds in a
non-trivial sense — that is, the best strategy is to compute m2 instances of Pn .

3

Composition Join (Boolean Matrix Multiplication)

In this section, we give an upper bound on the communication complexity of Boolean matrix
multiplication (equivalent to computing the composition join), proving our main theorem. As in
[VWWZ15], we consider the following promise version of the problem, in which the output has at
most ` ones.
Boolean Matrix Multiplication, BMMm,n,`
Alice’s input: A ∈ {0, 1}m×n
Bob’s input: B ∈ {0, 1}n×m
Promise: |A ∗ B| ≤ `
Output: BMMm,n,` (A, B) = A ∗ B = {(i, j) ∈ [m]×[m] : ∃k ∈ [n], A[i, k] = B[k, j] = 1}

6

The communication protocol we give is inspired by the query-optimal quantum algorithm for
Boolean matrix multiplication given in [JKLM16]. The algorithm of [JKLM16] is based on a
subroutine for a problem called graph collision. For any family of bipartite graphs G on n vertices,
the communication version of graph collision on G is as follows.
Graph Collision, GCG
Alice’s input: fA ∈ {0, 1}n
Bob’s input: fB ∈ {0, 1}nW
Output: GCG (fA , fB ) = (i,j)∈G fA (i)fB (j)
An efficient protocol for this problem can easily be constructed in the communication complexity
setting:
p
Lemma 3.1 (Graph collision). Q(GCG (fA , fB )) = O( min{|fA |, |fB |}) for any family of bipartite
graphs G.
Proof. Alice sends Bob |fA |, and Bob sends Alice |fB | using 2 log n bits of communication. If
|fA | ≤ |fB |, Alice sets a = fA and Bob sets b = {i ∈ [n] : ∃j ∈ [n], (i, j) ∈ G, fB (j) = 1}.
Otherwise, Alice sets a = {j ∈ [n] : ∃i ∈ [n], (i, j) ∈ G, fA (i) = 1} and Bob sets b = fB . They
finally compute DISJ(a, b).
When we solve graph collision as a subroutine, we will actually want to additionally find all
graph collisions in a particular instance. That is, we will want to solve the following problem.
Find All Graph Collisions, GCallG
Alice’s input: fA ∈ {0, 1}n
Bob’s input: fB ∈ {0, 1}n
Output: GCallG (fA , fB ) = {(i, j) ∈ G : fA (i) = fB (j) = 1}
The following upper bound for GCallG is a corollary of the previous lemma (its proof is similar to
the proof of Lemma 2.2).
p
Corollary 3.2 (Find all graph collisions). Q(GCallG (fA , fB )) = O( λ min{|fA |, |fB |}), where
λ = |{(i, j) ∈ G : fA (i) = fB (j) = 1}|.
The final ingredient we need before presenting our quantum communication protocol for Boolean
matrix multiplication is a quantum communication protocol that searches for a 1-instance among n
independent instances of a communication problem. Its proof is fairly straightforward and simply
combines quantum search with the original communication protocol.
Lemma 3.3 (Search over communication instances). Let f : X × Y → {0, 1} be a communication
problem with bounded error quantum communication complexity Q(f ). Let F : X np
× Y n → {0, 1}
be the problem of finding some i ∈ [n] such that f (xi , yi ) = 1. Then Q(F ) = O( nt Q(f ) log n),
where t = |{i ∈ [n] : f (xi , yi ) = 1}|.
P
Proof. Alice creates |πi = i∈[n] √1n |ii. Alice and Bob implement quantum search by repeating
the reflections
X
R1 = 2|πihπ| − I and R2 =
(−1)f (xi ,yi ) |iihi|
i∈[n]

p
O(
P n/t) times. Each implementation of R2 is accomplished
P as follows. Let Alice’s state be
i∈[n] αi |ii. Alice performs the mapping |ii 7→ |i, ii, to get
i∈[n] αi |i, ii and sends half of the
7

state to Bob. Conditioned on their quantum state, Alice and Bob perform the protocol for f
using input
P (xi , yi ), that is, they perform the protocol on a superposition of inputs. This leaves
the state i∈[n] αi |i, f (xi , yi )iA |i, f (xi , yi )iB (here we assume, without loss of generality, that the
final
in the protocol for f does not contain any garbage). Alice then maps this state to
P state
f
(x
,y
i
i ) |i, f (x , y )i |i, f (x , y )i . They run the protocol in reverse to uncompute f (x , y ),
i i A
i i B
i i
i (−1)P
f (xi ,yi ) |ii |ii . Bob sends his half to Alice, so she can uncompute it, leaving the
leaving
α
(−1)
A B
P i i
state i αi (−1)f (xi ,yi ) |ii, and thus implementing R2 .
We are now ready to state and prove our main theorem.
Theorem 3.4 (Upper bound for Boolean matrix multiplication). For all ` ∈ {1, . . . , m2 },
√
Q(BMMm,n,` ) = O( n`3/4 log m).
Proof. Alice and Bob run the following communication protocol.
1. Alice and Bob individually store the all-zero matrix C of size m × m.
2. Repeat:
(a) Alice and Bob jointly find k ∈ [n] such that GCC (A[·, k], B[k, ·]) = 1. If none exists,
Alice and Bob output C.
(b) Alice and Bob jointly compute S ← GCallC (A[·, k], B[k, ·]).
(c) Alice and Bob individually compute C ← C + S.
In this protocol Alice and Bob each maintain a matrix C containing the 1s of the product A ∗ B
found by the protocol so far. They repeatedly search for a new k ∈ [n] such that fAk = A[·, k] and
fBk = B[k, ·] have graph collisions with respect to the graph given by the complement of C. When
they find such a k, they compute all graph collisions. Suppose they find {k1 , . . . , kt } before there
are no more k to be found, and let λi be the
i. By Lemma 3.1
qnumber of ones found at round

ki
ki
n
and Lemma 3.3, in round i step 2a costs O
t−i+1 min{|fA |, fB |} log m . By Corollary 3.2, in
q

ki
ki
round i step 2b costs O
λi min{|fA |, |fB |} log m . Thus, the total cost is at most:
t r
X
i=1

n
t−i+1


q
q
ki
ki
ki
ki
min{|fA |, |fB |} + λi min{|fA |, fB |} log m.

Note that for any k, every (i, j) such that fAk (i) = fBk (j) = 1 implies √
that (A ∗ B)[i, j] = 1, so we
k
k
k
k
necessarily have ` ≥ |fA | · |fB |. We therefore have min{|fA |, |fB |} ≤ ` for all k ∈ [n], and thus,
the total cost is at most (up to constants):
v


u t

t r
X
X
u
p
√
n
`1/4
+ λi log m ≤ `1/4  nt + tt
λi  log m
t−i+1
i=1
i=1
√
√
≤ `1/4 ( nt + t`) log m,
√
Pt
−1/2 = Θ( t) and Cauchy-Schwartz inequality,
where in the first line we use the fact that P
i=1 i
and in the second line we use the fact that ti=1 λi = `, since ` is the total number of ones we
8

find over all rounds. Finally, observe that since t is the number of distinct witnesses k ∈ [n] found,
t ≤ n, and since we find at least one new 1 in every round except the last, we also have t ≤ ` + 1.
Thus, the total communication is at most


p
√
√
(`1/4 n + `3/4 ) min{n, `} log m = O `3/4 n log m ,
as claimed.

4

Matrix Multiplication over Finite Fields

In this section we consider matrix multiplication over finite fields and give tight bounds (up to
possible polylogarithmic factors) on its communication complexity. We work out here only the case
of square matrices over the binary field. Formally, the problem we consider is the following.
Square matrix multiplication over F2 , MMn,`
Alice’s input: A ∈ Fn×n
2
Bob’s input: B ∈ Fn×n
2
Promise: |AB| ≤ `
Output: the matrix AB ∈ Fn×n
2
The main result of this section is the following upper bound on the classical (and thus quantum)
communication complexity of this problem.
Theorem 4.1 (Upper bound
√ for matrix multiplication over F2 ). The classical communication
e
complexity of MMn,` is O(n `).
We will need two lemmas to prove Theorem 4.1. The first lemma is a finite-field version of a
result related to compressed sensing used in [VWWZ15]. The proof of this finite-field version can
be found in [DM09].
Lemma 4.2. For any positive integer n and any integer κ ∈ {1, . . . , n}, there are a distribution
O(κ)×n
on random matrices M ∈ F2
and a reconstruction function Rec(·) such that for any vector
x ∈ Fn2 with at most κ non-zero entries the inequality


Pr Rec(M x) = x > 0.99.
M

holds (i.e., Rec(·) applied on M x returns x with high probability).
The second lemma shows how to use Freivalds’ technique to detect non-zero columns of a matrix
product. Similar ideas were used in [GLL14].
Lemma 4.3. Let m and n be two positive integers. Consider the setting where Alice has for input
a matrix A ∈ Fm×n
and Bob has for input a matrix B ∈ F2n×n . Alice and Bob can detect, with high
2
e
probability, which columns of AB contain at least one non-zero entry with O(n)
communication.
Proof. Consider the following procedure: Alice takes a vector v uniformly at random in Fm
2 ; Alice
sends the row-vector v T A ∈ Fn2 to Bob; Bob sends the row-vector v T AB ∈ Fn2 to Alice. This
procedure has communication complexity 2n and, for each column of AB, enables Alice and Bob
to decide with probability at least 1/2 whether this column contains at least one non-zero entry.
By repeating this procedure a logarithmic number of times, Alice and Bob are able to find, with
high probability, which columns of AB contain at least one non-zero entry.
9

We are now ready to prove Theorem 4.1.
√
√
Proof of Theorem 4.1. We assume for convenience that both ` and n/ ` are integers (the general
√
case is handled similarly). We will say that a column of AB is dense if it contains
√ at least 0.9 `
non-zero entries, and say that a column of AB is sparse if it contains at most 1.1 ` non-zero entries
(note that a column can be both sparse and dense). The protocol is as follows.
1. Alice and Bob partition the columns of AB into dense columns and sparse columns: they
compute a set of indexes S ⊆ {1, . . . , n} such that, for any j ∈ {1, . . . , n}, the j-th column of
AB is dense if j ∈ S and sparse if j ∈
/ S.
2. Alice and Bob compute all entries of all columns of AB with index in S.
3. Alice and Bob compute all entries of all the columns of AB with index in [n] \ S.
e
Step 1 can be done probabilistically
√ with O(n) bits0 of communication
√ by repeating the following
procedure: Alice constructs a (n/ `) × n matrix A by selecting n/ ` rows of A uniformly at
random; Alice and Bob then use the protocol of Lemma 4.3 (with A0 as Alice’s input and B as
Bob’s input) to decide which columns of A0 B have more than one non-zero entry. Repeating this
procedure a logarithmic number of times enables Alice and Bob to decide, with high probability,
which
√ columns of AB are not dense: for a non-dense column of AB (i.e., a column with less than
0.9 ` non-zero entries) the corresponding column of A0 B will not contain any non-zero entry with
high probability (on the choice of A0 ). The indices of the other columns are collected in S. The
indices in S thus correspond only to dense columns of AB. While the set S may not contain the
indices of all the dense columns of AB, it can be seen
√ from a similar argument that all non-sparse
columns of AB (i.e., the columns with at least 1.1 ` non-zero entries) will be put in S, which
means that all indices in [n] \ S correspond to
√ columns of AB that are sparse.
√
1
Step 2 can be done with O(|S|n) = O( `n) bits of communication (note that |S| ≤ 0.9
`
since AB has only at most ` non-zero entries): Bob simply sends the entries B[i, j] for all (i, j) ∈
{1, . . . , n} × S, and then Alice computes
AB[i, j] for all (i, j) ∈ {1, . . . , n} × S.
√
√
e
Step 3 can be done with O(n `) bits of communication using Lemma 4.2 with κ = d1.1 `e, by
repeating the following procedure a logarithmic number of times: Alice chooses a random matrix M
as in Lemma 4.2 and sends M A to Bob; for each j ∈ {1, . . . , n}\S, Bob computes Rec(M Az) where z
denotes the j-th column of B.
We now show a lower bound on the quantum (and thus also classical) communication complexity of matrix multiplication over F2 , which matches the upper bound of Theorem 4.1 up to
polylogarithmic factors.
√
Theorem 4.4. The quantum communication complexity of MMn,` is Ω(n `).
√
Proof. Assume
for convenience
that ` is an integer (the
general case is handled similarly). Let
√
√
√
√
n `
1
`
1
`
n
x , . . . , x√ , y , . . . , y √
be 2 ` vectors in F2 . Let x ∈ F2 be the vector obtained
by concatenating
√
n `
1
1
`
`
x , . . . , x , and y ∈ F2 be the vector obtained by concatenating y , . . . , y .
√
Construct the n × n matrix
A by putting the vector √
xi as its i-th row, for each i ∈ {1, . . . , `},
√
and setting the next n − ` rows to zero (observe that ` ≤ n since ` ≤ n2 ).√Construct the n × n
matrix B√by putting the vector y j as its j-th column, for each j ∈ {1, . . . , `}, and setting the
next n − ` columns to zero. Observe that |AB| ≤ ` and the parity of the diagonal entries of the
matrix product AB is equal to
√
`
M
xi · y i = x · y.
i=1

10

√

We thus obtain a reduction from computing the inner product of two vectors in Fn2√ ` to solving
MMn,` . Since the quantum communication complexity of the former problem is Ω(n `), as shown
in [Kre95], we obtain the same lower bound for MMn,` .

5

Lower Bounds for Boolean Matrix Multiplication

An important open problem of this work is to prove a tight lower bound on the bounded error
quantum communication complexity of Boolean matrix multiplication, i.e., to show that the upper
bound of Theorem 3.4 is tight. Let us focus on the square case (i.e., m = n). We are able to
prove two lower bounds, each of which is tight for one extreme value of `: ` = O(1) or ` = Ω(n2 ),
but neither is tight for the range ` ∈ (ω(1), o(n2 )). We further show that assuming a plausible
OR-lemma, our upper bound is indeed tight, up to logarithmic factors.
√
Proposition 5.1. For all ` ∈ {1, . . . , n2 }, Q(BMMn,n,` ) = Ω( n`). In particular, when ` = O(1),
√
then Q(BMMn,n,` ) = Ω( n`3/4 ).
√
√
`
Proof. We can embed ` ≤ n instances {(a(i) , b(i) )}i=1
of
√ DISJn in an instance of BMMn,n,` as
(i)
follows. Let A have a in the i-th row for√i = 1, . . . , `, and all zeros elsewhere, and let B
have b(i) in the√i-th √
column for i = 1, . . . , `, and zeros elsewhere. Then AB is 0 except in
the upper left
`
×
` submatrix, so |AB| ≤ `, and (AB)[i, i] = DISJn (a(i) , b(i) ), so AB en√
√
√
√ √
( `)
codes DISJn√ (a(1) , . . . , a( `) , b(1) , . . . , b( `) ). The result follows from the Ω( ` n) lower bound
( `)

on Q(DISJn

) shown in [KSdW07].

Proposition 5.2. For all ` ∈ {1, . . . , n2 }, Q(BMMn,n,` ) = Ω(`). In particular, when ` = Ω(n2 ),
√
then Q(BMMn,n,` ) = Ω(`3/4 n).
Proof. We can embed an instance (a, b) of the inner product function IP` in an instance of BMMn,n,`
as follows. Let B = I be the identity matrix, and let A contain the `-bit string a in the first `
positions. Then Alice and Bob jointly compute AB = A, and Bob can compute IP(a, b) and send
the resulting bit to Alice. Since Q(IP` ) = Ω(`), we have Q(BMMn,n,` ) = Ω(`).
Proposition 5.3. Suppose computing the entrywise-OR of k independent instances of BMMn,n,n2
√
has bounded error quantum communication complexity Ω( kQ(BMMn,n,n2 )). Then for any ` ∈ [n2 ],
√
Q(BMMn,n,` ) = Ω(`3/4 n).
Proof. Let (A1 , B1 ), . . . , (Ak , Bk )
and B as follows:

A1
 0

A= .
 ..
0

be independent instances of BMM√`,√`,` , for k =

. . . Ak
... 0 

..  ,
..
. . 
... 0

n
√
.
`

Define A




B1 0 . . . 0


B =  ... ... . . . ...  .
Bk 0 . . . 0

W
Then A ∗ B has ki=1 Ai ∗ Bi in the top left corner,qand zeros elsewhere. So |A ∗ B| ≤ `, and
√
√
computing A ∗ B costs at least kQ(BMM√`,√`,` ) ≥ √n` ` = `3/4 n.
The above proposition actually holds equally true for the non-promise problem BMMm,n =
√
BMMm,n,m2 , and would imply Q(BMMm,n ) = Ω(m3/2 n).

11

Acknowledgments
The authors are grateful to Troy Lee and Ronald de Wolf for helpful discussions. FLG is supported
by the Grant-in-Aid for Young Scientists (A) No. 16H05853 and the Grant-in-Aid for Scientific
Research (A) No. 16H01705 of the Japan Society for the Promotion of Science, and the Grantin-Aid for Scientific Research on Innovative Areas No. 24106009 of the Ministry of Education,
Culture, Sports, Science and Technology in Japan. SJ is supported by the Institute for Quantum
Information and Matter, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support
of the Gordon and Betty Moore Foundation (GBMF-12500028).

References
[AA03]

S. Aaronson and A. Ambainis. Quantum search of spatial regions. In Proceedings of the 44th
IEEE Symposium on Foundations of Computer Science, pages 200–209, 2003. 4

[AGK06]

A. Arasu, V. Ganti, and R. Kaushik. Efficient exact set-similarity joins. In Proceedings of the
32nd International Conference on Very Large Data Bases, pages 918–929, 2006. 1

[AP09]

R. R. Amossen and R. Pagh. Faster join-projects and sparse matrix multiplications. In Proceedings of the International Conference on Database Theory, pages 121–126, 2009. 2

[BCW98]

H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 30th ACM Symposium on Theory of Computing, pages 63–68, 1998.
4

[Bv06]

H. Buhrman and R. Špalek. Quantum verification of matrix products. In Proceedings of the
17th ACM-SIAM symposium on Discrete algorithm, pages 880–889, 2006. 2

[Cod70]

E. F. Codd. A relational model of data for large shared data banks. Communications of the
ACM, 13(6):377–387, 1970. 1

[DM09]

S. C. Draper and S. Malekpour. Compressed sensing over finite fields. In Proceedings of the
IEEE International Symposium on Information Theory, pages 669–673, 2009. 9

[GLL14]

L. Gasieniec, C. Levcopoulos, and A. Lingas. Efficiently correcting matrix products. In Proceedings of the 25th International Symposium on Algorithms and Computation, pages 53–64, 2014.
9

[Hd02]

P. Høyer and R. de Wolf. Improved quantum communication bounds for disjointness and equality. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science,
pages 299–310, 2002. 4

[HM97]

S. Helmer and G. Moerkotte. Evaluation of main memory join algorithms for joins with set
comparison join predicates. In Proceedings of 23rd International Conference on Very Large
Data Bases, pages 386–395, 1997. 1

[JKLM16]

S. Jeffery, R. Kothari, F. Le Gall, and F. Magniez. Improving quantum query complexity of
Boolean matrix multiplication using graph collision. Algorithmica, 2016. To appear. 2, 7

[Kre95]

I. Kremer. Quantum communication. Master’s thesis, The Hebrew University of Jerusalem,
1995. 11

[KS92]

B. Kalyanasundaram and G. Schnitger. The probabilistic communication complexity of set
intersection. SIAM Journal on Discrete Mathematics, 5(4):545–557, 1992. 4

[KSdW07]

H. Klauck, R. Spalek, and R. de Wolf. Quantum and classical strong direct product theorems
and optimal time-space tradeoffs. SIAM Journal on Computing, 36(5):1472–1493, 2007. 11

[LdB07]

D. Leinders and J. Van den Bussche. On the complexity of division and set joins in the relational
algebra. Journal of Computer and System Sciences, 73(4):538–549, 2007. 1

12

[Lin11]

A. Lingas. A fast output-sensitive algorithm for Boolean matrix multiplication. Algorithmica,
61(1):36–50, 2011. 2

[Mam03]

N. Mamoulis. Efficient processing of joins on set-valued attributes. In Proceedings of the 2003
ACM SIGMOD International Conference on Management of Data, pages 157–168, 2003. 1

[MG03]

S. Melnik and H. Garcia-Molina. Adaptive algorithms for set containment joins. ACM Transactions on Database Systems, 28:56–99, 2003. 1

[Raz92]

A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science,
106:385–390, 1992. 4

[Raz03]

A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the
Russian Academy of Science, mathematics, 67:159–176, 2003. 4

[RPNK00]

K. Ramasamy, J. M. Patel, J. F. Naughton, and R. Kaushik. Set containment joins: The good,
the bad and the ugly. In Proceedings of 26th International Conference on Very Large Data
Bases, pages 351–362, 2000. 1

[She12]

A. A. Sherstov. Strong direct product theorems for quantum communication and query complexity. SIAM Journal on Computing, 41(5):1122–1165, 2012. 5

[VWWZ15] D. Van Gucht, R. Williams, D. P. Woodruff, and Q. Zhang. The communication complexity
of distributed set-joins with applications to matrix multiplication. In Proceedings of the ACM
Symposium on Principles of Database Systems, pages 199–212, 2015. 1, 2, 6, 9
[Yao79]

A. C.-C. Yao. Some complexity questions related to distributive computing. In Proceedings of
the 11th ACM Symposium on Theory of Computing, pages 209–213, 1979. 3

[Yao93]

A. C.-C. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on
Foundations of Computer Science, pages 352–360, 1993. 3

13

