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.TQC.2017.6
URN: urn:nbn:de:0030-drops-85793
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8579/
Go to the corresponding LIPIcs Volume Portal

Le Gall, François ; Nakajima, Shogo

Multiparty Quantum Communication Complexity of Triangle Finding

pdf-format:
LIPIcs-TQC-2017-6.pdf (0.5 MB)

Abstract

Triangle finding (deciding if a graph contains a triangle or not) is a central problem in quantum query complexity. The quantum communication complexity of this problem, where the edges of the graph are distributed among the players, was considered recently by Ivanyos et al. in the two- party setting. In this paper we consider its k-party quantum communication complexity with k >= 3. Our main result is a ~O(m^(7/12))-qubit protocol, for any constant number of players k, deciding with high probability if a graph with m edges contains a triangle or not. Our approach makes connections between the multiparty quantum communication complexity of triangle finding and the quantum query complexity of graph collision, a well-studied problem in quantum query complexity.

BibTeX - Entry

@InProceedings{legall_et_al:LIPIcs:2018:8579,
  author =	{Fran{\c{c}}ois Le Gall and Shogo Nakajima},
  title =	{{Multiparty Quantum Communication Complexity of Triangle Finding}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{6:1--6:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Mark M. Wilde},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8579},
  URN =		{urn:nbn:de:0030-drops-85793},
  doi =		{10.4230/LIPIcs.TQC.2017.6},
  annote =	{Keywords: Quantum communication complexity, triangle finding, graph collision}
}

Keywords: Quantum communication complexity, triangle finding, graph collision
Collection: 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)
Issue Date: 2018
Date of publication: 14.03.2018

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