Document Open Access Logo

Quantum Communication Complexity of Distributed Set Joins

Authors Stacey Jeffery, François Le Gall

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.54.pdf
  • Filesize: 445 kB
  • 13 pages

Document Identifiers

Author Details

Stacey Jeffery
François Le Gall

Cite As Get BibTex

Stacey Jeffery and François Le Gall. Quantum Communication Complexity of Distributed Set Joins. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.54

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.

Subject Classification

Keywords
  • quantum communication complexity
  • distributed quantum computing
  • database joins

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. H. Buhrman and R. Špalek. Quantum verification of matrix products. In Proceedings of the 17th ACM-SIAM symposium on Discrete algorithm, pages 880-889, 2006. Google Scholar
  6. E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377-387, 1970. Google Scholar
  7. 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. Google Scholar
  8. 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. Google Scholar
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. 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. Google Scholar
  12. B. Kalyanasundaram and G. Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, 1992. Google Scholar
  13. 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. URL: http://dx.doi.org/10.1137/05063235X.
  14. I. Kremer. Quantum communication. Master’s thesis, The Hebrew University of Jerusalem, 1995. Google Scholar
  15. 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. Google Scholar
  16. A. Lingas. A fast output-sensitive algorithm for Boolean matrix multiplication. Algorithmica, 61(1):36-50, 2011. Google Scholar
  17. 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. Google Scholar
  18. S. Melnik and H. Garcia-Molina. Adaptive algorithms for set containment joins. ACM Transactions on Database Systems, 28:56-99, 2003. Google Scholar
  19. 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. Google Scholar
  20. A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106:385-390, 1992. Google Scholar
  21. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, mathematics, 67:159-176, 2003. Google Scholar
  22. A. A. Sherstov. Strong direct product theorems for quantum communication and query complexity. SIAM Journal on Computing, 41(5):1122-1165, 2012. Google Scholar
  23. 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. Google Scholar
  24. J. Watrous. Course notes for Theory of Quantum Information. Available at: https://cs.uwaterloo.ca/~watrous/CS766/, 2013.
  25. 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. Google Scholar
  26. A. C.-C. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 352-360, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact