Document Open Access Logo

Multiparty Quantum Communication Complexity of Triangle Finding

Authors François Le Gall, Shogo Nakajima

PDF
Thumbnail PDF

File

LIPIcs.TQC.2017.6.pdf
  • Filesize: 485 kB
  • 11 pages

Document Identifiers

Author Details

François Le Gall
Shogo Nakajima

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.TQC.2017.6

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.

Subject Classification

Keywords
  • Quantum communication complexity
  • triangle finding
  • graph collision

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson and Andris Ambainis. Quantum search of spatial regions. In Proceedings of the 51st Symposium on Foundations of Computer Science, pages 200-209, 2003. Google Scholar
  2. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210-239, 2007. Google Scholar
  3. Andris Ambainis. Quantum search with variable times. Theory of Computing Systems, 47(3):786-807, 2010. Google Scholar
  4. Aleksandrs Belovs. Span programs for functions with constant-sized 1-certificates. In Proceedings of the 44th Symposium on Theory of Computing, pages 77-84, 2012. Google Scholar
  5. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 30th Symposium on Theory of Computing, pages 63-68, 1998. Google Scholar
  6. Harry Buhrman, Christoph Dürr, Mark Heiligman, and Peter Høyer. Quantum algorithms for element distinctness. SIAM Journal on Computing, 34(6):1324-1330, 2005. Google Scholar
  7. Titouan Carette, Mathieu Laurière, and Frédéric Magniez. Extended learning graphs for triangle finding. In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science, pages 20:1-20:14, 2017. Google Scholar
  8. Andrew M. Childs and Robin Kothari. Quantum query complexity of minor-closed graph properties. SIAM Journal on Computing, 41(6):1426-1450, 2012. Google Scholar
  9. Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In Proceedings of the 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 148-159, 2012. Google Scholar
  10. Stacey Jeffery, Robin Kothari, and Frédéric Magniez. Nested quantum walks with quantum data structures. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1474-1485, 2013. Google Scholar
  11. Bala Kalyanasundaram and Georg Schintger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, 1992. Google Scholar
  12. François Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In Proceedings of the 28th Symposium on the Theory of Computing, pages 216-225, 2014. Google Scholar
  13. François Le Gall and Shogo Nakajima. Quantum algorithm for triangle finding in sparse graphs. In Proceedings of the 26th International Symposium on Algorithms and Computation, pages 590-600, 2015. Google Scholar
  14. Troy Lee, Frédéric Magniez, and Miklos Santha. Improved quantum query algorithms for triangle finding and associativity testing. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1486-1502, 2013. Google Scholar
  15. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142-164, 2011. Google Scholar
  16. Frédéric Magniez, Miklos Santha, and Mario Szegedy. Quantum algorithms for the triangle problem. SIAM Journal on Computing, 37(2):413-424, 2007. Google Scholar
  17. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd Symposium on Theory of Computing, pages 603-610, 2010. Google Scholar
  18. Alexander A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-390, 1992. Google Scholar
  19. Alexander A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya Mathematics, 67(1):145-159, 2003. Google Scholar
  20. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the 51st Symposium on Foundations of Computer Science, pages 645-654, 2010. Google Scholar
  21. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM Journal on Computing, 42(3):831-854, 2013. Google Scholar
  22. Andrew C. Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11th Symposium on Theory of Computing, pages 209-213, 1979. Google Scholar
  23. Andrew C. Yao. Quantum circuit complexity. In Proceedings of the 34st Symposium on Foundations of Computer Science, pages 352-361, 1993. Google Scholar
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 About DROPS Imprint Privacy Contact