Document Open Access Logo

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model

Authors Taisuke Izumi, François Le Gall, Frédéric Magniez

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.23.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Taisuke Izumi
  • Graduate School of Engineering, Nagoya Institute of Technology, Japan
François Le Gall
  • Graduate School of Mathematics, Nagoya University, Japan
Frédéric Magniez
  • Université de Paris, IRIF, CNRS, France

Acknowledgements

The authors are grateful to anonymous reviewers for helpful comments. TI was partially supported by JST SICORP grant No. JPMJSC1606 and JSPS KAKENHI grant No. JP19K11824. FLG was supported by JSPS KAKENHI grants Nos. JP15H01677, JP16H01705, JP16H05853, JP19H04066 and by the MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grant No. JPMXS0118067394. FM was partially supported by the ERA-NET Cofund in Quantum Technologies project QuantAlgo and the French ANR Blanc project QuData.

Cite AsGet BibTex

Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.23

Abstract

This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound O(n) to Õ(n^{1/3}), where n denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in Õ(n^{1/4}) rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now Õ(n^{1/4}) and Θ~(n^{1/3}), respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum computing
  • distributed computing
  • CONGEST model

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. CoRR, abs/1711.01623, 2017. URL: http://arxiv.org/abs/1711.01623.
  2. Aleksandrs Belovs. Span programs for functions with constant-sized 1-certificates: extended abstract. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 77-84, 2012. URL: https://doi.org/10.1145/2213977.2213985.
  3. Charles H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing, 18(4):766-776, 1989. URL: https://doi.org/10.1137/0218053.
  4. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 63-68, 1998. URL: https://doi.org/10.1145/276698.276713.
  5. 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. URL: https://doi.org/10.1007/s00446-016-0270-2.
  6. Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed triangle detection via expander decomposition. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 821-840, 2019. URL: https://doi.org/10.1137/1.9781611975482.51.
  7. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 66-73, 2019. Google Scholar
  8. Danny Dolev, Christoph Lenzen, and Shir Peled. "Tri, Tri Again": Finding triangles and small subgraphs in a distributed setting - (extended abstract). In Proceedings of the International Symposium on Distributed Computing (DISC), pages 195-209, 2012. URL: https://doi.org/10.1007/978-3-642-33651-5_14.
  9. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 367-376, 2014. URL: https://doi.org/10.1145/2611462.2611493.
  10. Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 166-175, 2014. URL: https://doi.org/10.1145/2611462.2611488.
  11. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1150-1162, 2012. URL: https://doi.org/10.1137/1.9781611973099.91.
  12. Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? In Proceedings of the International Symposium on Distributed Computing (DISC), pages 243-257, 2009. URL: https://doi.org/10.1007/978-3-642-04355-0_26.
  13. Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and routing in almost mixing time. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 131-140, 2017. URL: https://doi.org/10.1145/3087801.3087827.
  14. Mohsen Ghaffari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 31:1-31:16, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.31.
  15. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 212-219, 1996. URL: https://doi.org/10.1145/237814.237866.
  16. Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Large cuts with local algorithms on triangle-free graphs. The Electronic Journal of Combinatorics, 24(4):P4.21, 2017. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p21.
  17. 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 ACM Symposium on Principles of Distributed Computing (PODC), pages 84-93, 2019. Google Scholar
  18. Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 381-389, 2017. URL: https://doi.org/10.1145/3087801.3087811.
  19. François Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 216-225, 2014. URL: https://doi.org/10.1109/FOCS.2014.31.
  20. François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 337-346, 2018. URL: https://doi.org/10.1145/3212734.3212744.
  21. 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), pages 49:1-49:14, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.49.
  22. Troy Lee, Frédéric Magniez, and Miklos Santha. Improved quantum query algorithms for triangle finding and associativity testing. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1486-1502, 2013. URL: https://doi.org/10.1137/1.9781611973105.107.
  23. Frédéric Magniez, Miklos Santha, and Mario Szegedy. Quantum algorithms for the triangle problem. SIAM Journal on Computing, 37(2):413-424, 2007. URL: https://doi.org/10.1137/050643684.
  24. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2011. Google Scholar
  25. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the distributed complexity of large-scale graph computations. In Proceedings of the Symposium on Parallel Algorithms and Architectures (SPAA), pages 405-414, 2018. URL: https://doi.org/10.1145/3210377.3210409.
  26. Seth Pettie and Hsin-Hao Su. Distributed coloring algorithms for triangle-free graphs. Information and Computation, 243:263-280, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.018.
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 Imprint Privacy Contact