Quantum Distributed Algorithms: Recent Results

          @misc{ scivideos_15444,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-141},
            author = {},
            keywords = {},
            language = {en},
            title = {Quantum Distributed Algorithms: Recent Results},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15444 see, \url{https://scivideos.org/Simons-Institute/15444}}
          }
          

Abstract

The subject of this talk will be quantum distributed computing, i.e., distributed computing when the processors of the network can exchange quantum information. After describing the basics of distributed computing, I will explain a result obtained with Frédéric Magniez (arXiv:1804.02917) on quantum algorithms computing the diameter of the network. I will then present others results (arXiv:1810.10838 and arXiv:1908.11488) that show separations between the computational powers of quantum and classical distributed algorithms in several fundamental models of distributed computing. I will conclude my talk by mentioning interesting and important open questions in quantum distributed computing.