Document Open Access Logo

Quantum Advantage for the LOCAL Model in Distributed Computing

Authors François Le Gall, Harumichi Nishimura, Ansis Rosmanis

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.49.pdf
  • Filesize: 0.48 MB
  • 14 pages

Document Identifiers

Author Details

François Le Gall
  • Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan
Harumichi Nishimura
  • Graduate School of Informatics, Nagoya University, Chikusa-ku, Nagoya, Aichi 464-8601, Japan
Ansis Rosmanis
  • Centre for Quantum Technologies, National University of Singapore, Block S15, 3 Science Drive 2, 117543, Singapore

Acknowledgements

FLG was partially supported by the JSPS KAKENHI grants No. 15H01677, No. 16H01705 and No. 16H05853. HN was partially supported by the JSPS KAKENHI grants No. 26247016, No. 16H01705 and No. 16K00015. AR was partially supported by the Singapore Ministry of Education and the National Research Foundation under grant R-710-000-012-135. Part of this work was done while AR was visiting Kyoto University, and AR would like to thank FLG for hospitality.

Cite As Get BibTex

François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum Advantage for the LOCAL Model in Distributed Computing. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.49

Abstract

There are two central models considered in (fault-free synchronous) distributed computing: the CONGEST model, in which communication channels have limited bandwidth, and the LOCAL model, in which communication channels have unlimited bandwidth. Very recently, Le Gall and Magniez (PODC 2018) showed the superiority of quantum distributed computing over classical distributed computing in the CONGEST model. In this work we show the superiority of quantum distributed computing in the LOCAL model: we exhibit two computational tasks that can be solved in a constant number of rounds in the quantum setting but require Omega(n) rounds in the classical (randomized) setting, where n denotes the size of the network.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum computing
  • distributed computing
  • LOCAL model

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. Theory of Computing, 1(1):47-79, 2005. URL: http://dx.doi.org/10.4086/toc.2005.v001a004.
  2. Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News, 45(3):82-104, 2014. URL: http://dx.doi.org/10.1145/2670418.2670440.
  3. Jonathan Barrett, Carlton M. Caves, Bryan Eastin, Matthew B. Elliott, and Stefano Pironio. Modeling Pauli measurements on graph states with nearest-neighbor classical communication. Physical Review A, 75:012103, 2007. URL: http://dx.doi.org/10.1103/PhysRevA.75.012103.
  4. Michael Ben-Or and Avinatan Hassidim. Fast quantum byzantine agreement. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 481-485, 2005. URL: http://dx.doi.org/10.1145/1060590.1060662.
  5. Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308-311, 2018. URL: http://dx.doi.org/10.1126/science.aar3106.
  6. Anne Broadbent and Alain Tapp. Can quantum mechanics help distributed computing? SIGACT News, 39(3):67-76, 2008. URL: http://dx.doi.org/10.1145/1412700.1412717.
  7. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. Classical Communication and Computation. In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 63-68, 1998. URL: http://dx.doi.org/10.1145/276698.276713.
  8. Yi-Jun Chang and Seth Pettie. A Time Hierarchy Theorem for the LOCAL Model. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pages 156-167, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.23.
  9. Vasil S. Denchev and Gopal Pandurangan. Distributed quantum computing: a new frontier in distributed systems or science fiction? SIGACT News, 39(3):77-95, 2008. URL: http://dx.doi.org/10.1145/1412700.1412718.
  10. Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pages 166-175, 2014. URL: http://dx.doi.org/10.1145/2611462.2611488.
  11. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1150-1162, 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.91.
  12. Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What Can Be Observed Locally? In Proceedings of the 23rd International Symposium on Distributed Computing, pages 243-257, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04355-0_26.
  13. Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going beyond Bell’s Theorem. In Bell’s Theorem, Quantum Theory, and Conceptions of the Universe, volume 37 of Fundamental Theories of Physics, pages 69-72. Springer, Dordrecht, 1989. URL: http://dx.doi.org/10.1007/978-94-017-0849-4_10.
  14. Aram W. Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549:203–209, 2017. URL: http://dx.doi.org/10.1038/nature23458.
  15. Marc Hein, Jens Eisert, and Hans J. Briegel. Multiparty entanglement in graph states. Physical Review A, 69:062311, June 2004. URL: http://dx.doi.org/10.1103/PhysRevA.69.062311.
  16. Stephan Holzer and Roger Wattenhofer. Optimal Distributed All Pairs Shortest Paths and Applications. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, pages 355-364, 2012. URL: http://dx.doi.org/10.1145/2332432.2332504.
  17. Peter Høyer and Ronald de Wolf. Improved Quantum Communication Complexity Bounds for Disjointness and Equality. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, pages 299-310, 2002. URL: http://dx.doi.org/10.1007/3-540-45841-7_24.
  18. François Le Gall and Frédéric Magniez. Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 337-346, 2018. URL: http://dx.doi.org/10.1145/3212734.3212744.
  19. Nathan Linial. Distributive Graph Algorithms-Global Solutions from Local Data. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 331-335, 1987. URL: http://dx.doi.org/10.1109/SFCS.1987.20.
  20. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  21. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2011. URL: http://dx.doi.org/10.1017/CBO9780511976667.
  22. David Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, 2000. URL: http://dx.doi.org/10.1137/1.9780898719772.
  23. David Peleg, Liam Roditty, and Elad Tal. Distributed Algorithms for Network Diameter and Girth. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, pages 660-672, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31585-5_58.
  24. Seiichiro Tani, Hirotada Kobayashi, and Keiji Matsumoto. Exact Quantum Algorithms for the Leader Election Problem. ACM Transactions on Computation Theory, 4(1):1:1-1:24, 2012. URL: http://dx.doi.org/10.1145/2141938.2141939.
  25. Ronald de Wolf. Quantum communication and complexity. Theoretical Computer Science, 287(1):337-353, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(02)00377-8.
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