Spring 2020

Quantum Distributed Algorithms: Recent Results

Thursday, Feb. 27, 2020 2:30 pm3:00 pm PST

Add to Calendar


François Le Gall (Nagoya University)


Calvin Lab Auditorium

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.

PDF icon Francois Le Gall Slides700.7 KB