License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.54
URN: urn:nbn:de:0030-drops-64663
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6466/
Go to the corresponding LIPIcs Volume Portal

Jeffery, Stacey ; Le Gall, François

Quantum Communication Complexity of Distributed Set Joins

pdf-format:
LIPIcs-MFCS-2016-54.pdf (0.4 MB)

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 times n Boolean matrices, each owned by one of two respective parties, can be computed with widetilde-O(sqrt{n} ell^{3/4}) qubits of communication, where ell denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is widetilde-Theta(n sqrt{ell}), 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 F_2.

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.

BibTeX - Entry

@InProceedings{jeffery_et_al:LIPIcs:2016:6466,
  author =	{Stacey Jeffery and Fran{\c{c}}ois Le Gall},
  title =	{{Quantum Communication Complexity of Distributed Set Joins}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6466},
  URN =		{urn:nbn:de:0030-drops-64663},
  doi =		{10.4230/LIPIcs.MFCS.2016.54},
  annote =	{Keywords: quantum communication complexity, distributed quantum computing, database joins}
}

Keywords: quantum communication complexity, distributed quantum computing, database joins
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI