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.STACS.2020.23
URN: urn:nbn:de:0030-drops-118840
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11884/
Go to the corresponding LIPIcs Volume Portal

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

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model

pdf-format:
LIPIcs-STACS-2020-23.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{izumi_et_al:LIPIcs:2020:11884,
  author =	{Taisuke Izumi and Fran{\c{c}}ois Le Gall and Fr{\'e}d{\'e}ric Magniez},
  title =	{{Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11884},
  URN =		{urn:nbn:de:0030-drops-118840},
  doi =		{10.4230/LIPIcs.STACS.2020.23},
  annote =	{Keywords: Quantum computing, distributed computing, CONGEST model}
}

Keywords: Quantum computing, distributed computing, CONGEST model
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

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