License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.35
URN: urn:nbn:de:0030-drops-156319
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15631/
Go to the corresponding LIPIcs Volume Portal

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

Quantum Distributed Algorithms for Detection of Cliques

pdf-format:
LIPIcs-ITCS-2022-35.pdf (1.0 MB)

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.

BibTeX - Entry

@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2022.35,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Le Gall, Fran\c{c}ois and Leitersdorf, Dean and Oshman, Rotem},
  title =	{{Quantum Distributed Algorithms for Detection of Cliques}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{35:1--35:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15631},
  URN =		{urn:nbn:de:0030-drops-156319},
  doi =		{10.4230/LIPIcs.ITCS.2022.35},
  annote =	{Keywords: distributed graph algorithms, quantum algorithms, cycles, cliques, Congested Clique, CONGEST}
}

Keywords: distributed graph algorithms, quantum algorithms, cycles, cliques, Congested Clique, CONGEST
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

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