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.