1 Search Results for "Nakajima, Shogo"

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-dev.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}
}
  • Refine by Author
  • 1 Le Gall, François
  • 1 Nakajima, Shogo

  • Refine by Classification

  • Refine by Keyword
  • 1 Quantum communication complexity
  • 1 graph collision
  • 1 triangle finding

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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