DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2017.6

Multiparty Quantum Communication Complexity of Triangle Finding

Authors: François Le Gall and Shogo Nakajima

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

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.

Cite as

François Le Gall and Shogo Nakajima. Multiparty Quantum Communication Complexity of Triangle Finding. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.TQC.2017.6,
  author =	{Le Gall, Fran\c{c}ois and Nakajima, Shogo},
  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 =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.6},
  URN =		{urn:nbn:de:0030-drops-85793},
  doi =		{10.4230/LIPIcs.TQC.2017.6},
  annote =	{Keywords: Quantum communication complexity, triangle finding, graph collision}
}

Search Results

Documents authored by Nakajima, Shogo

Multiparty Quantum Communication Complexity of Triangle Finding

Abstract

Cite as

Thanks for your feedback!

Could not send message