Document Open Access Logo

Quantum Distributed Algorithms for Detection of Cliques

Authors Keren Censor-Hillel , Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.35.pdf
  • Filesize: 0.98 MB
  • 25 pages

Document Identifiers

Author Details

Keren Censor-Hillel
  • Technion, Haifa, Israel
Orr Fischer
  • Tel-Aviv University, Israel
François Le Gall
  • Nagoya University, Aichi, Japan
Dean Leitersdorf
  • Technion, Haifa, Israel
Rotem Oshman
  • Tel-Aviv University, Israel

Funding

This project was partially supported by the European Union’s Horizon 2020 Research and Innovation Programme under grant agreement no. 755839. François Le Gall was supported by JSPS KAKENHI grants Nos. JP19H04066, JP20H05966, JP20H00579, JP20H04139, JP21H04879 and MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grants No. JPMXS0118067394 and JPMXS0120319794.

Cite As Get BibTex

Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum Distributed Algorithms for Detection of Cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 35:1-35:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.35

Abstract

The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed algorithms that run faster than the fastest known classical counterparts, and even separations between the two models. A prime example is the result by Izumi, Le Gall, and Magniez [STACS 2020], who showed that triangle detection by quantum distributed algorithms is easier than triangle listing, while an analogous result is not known in the classical case.
In this paper we present a framework for fast quantum distributed clique detection. This improves upon the state-of-the-art for the triangle case, and is also more general, applying to larger clique sizes.
Our main technical contribution is a new approach for detecting cliques by encapsulating this as a search task for nodes that can be added to smaller cliques. To extract the best complexities out of our approach, we develop a framework for nested distributed quantum searches, which employ checking procedures that are quantum themselves.
Moreover, we show a circuit-complexity barrier on proving a lower bound of the form Ω(n^{3/5+ε}) for K_p-detection for any p ≥ 4, even in the classical (non-quantum) distributed CONGEST setting.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • distributed graph algorithms
  • quantum algorithms
  • cycles
  • cliques
  • Congested Clique
  • CONGEST

Metrics

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

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen. Fooling views: a new lower bound technique for distributed computations under congestion. Distributed Computing, 33(6):545-559, 2020. Google Scholar
  2. Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News, 45(3):82-104, 2014. Google Scholar
  3. Michael Ben-Or and Avinatan Hassidim. Fast quantum byzantine agreement. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pages 481-485, 2005. Google Scholar
  4. Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf. Tight distributed listing of cliques. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 2878-2891, 2021. Google Scholar
  5. Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast distributed algorithms for girth, cycles and small subgraphs. In Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020), pages 33:1-33:17, 2020. Google Scholar
  6. Keren Censor-Hillel, François Le Gall, and Dean Leitersdorf. On distributed listing of cliques. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 474-482, 2020. Google Scholar
  7. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. Distributed Computing, 32(6):461-478, 2019. Google Scholar
  8. Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed triangle detection via expander decomposition. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 821-840, 2019. Google Scholar
  9. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 66-73, 2019. Google Scholar
  10. Artur Czumaj and Christian Konrad. Detecting cliques in CONGEST networks. Distributed Computing, 33(6):533-543, 2020. Google Scholar
  11. Vasil S. Denchev and Gopal Pandurangan. Distributed quantum computing: a new frontier in distributed systems or science fiction? SIGACT News, 39(3):77-95, 2008. Google Scholar
  12. Danny Dolev, Christoph Lenzen, and Shir Peled. "tri, tri again": Finding triangles and small subgraphs in a distributed setting. In Proceedings of the 26th International Symposium on Distributed Computing (DISC 2012), pages 195-209, 2012. Google Scholar
  13. Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear-time distributed algorithms for detecting small cliques and even cycles. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019), pages 15:1-15:16, 2019. Google Scholar
  14. Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear-time distributed algorithms for detecting small cliques and even cycles (journal version). To appear in Distributed Computing, 2021. Google Scholar
  15. Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC 2014), pages 166-175, 2014. Google Scholar
  16. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 153-162, 2018. Google Scholar
  17. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1150-1162, 2012. Google Scholar
  18. Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? In Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009), pages 243-257, 2009. Google Scholar
  19. Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and routing in almost mixing time. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 131-140, 2017. Google Scholar
  20. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pages 212-219, 1996. Google Scholar
  21. Taisuke Izumi and François Le Gall. Quantum distributed algorithm for the all-pairs shortest path problem in the CONGEST-CLIQUE model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 84-93, 2019. Google Scholar
  22. Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum distributed algorithm for triangle finding in the CONGEST model. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 23:1-23:13, 2020. Google Scholar
  23. Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 381-389, 2017. Google Scholar
  24. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM journal on computing, 18(6):1149-1178, 1989. Google Scholar
  25. François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 337-346, 2018. Google Scholar
  26. François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum advantage for the LOCAL model in distributed computing. In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pages 49:1-49:14, 2019. Google Scholar
  27. Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC 2013), pages 42-50, 2013. Google Scholar
  28. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the distributed complexity of large-scale graph computations. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 405-414, 2018. Google Scholar
  29. Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1993), pages 331-340, 1993. Google Scholar
  30. Seiichiro Tani, Hirotada Kobayashi, and Keiji Matsumoto. Exact quantum algorithms for the leader election problem. ACM Transactions on Computation Theory, 4(1):1:1-1:24, 2012. 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