Exact Quantum Algorithms for the Leader Election Problem - Hirotada Kobayashi

It is well-known that no classical algorithm can solve exactly (i.e., the algorithm always halts and solves the problem with zero error) the leader election problem in anonymous networks. This work proposes two quantum algorithms that, when parties are connected by quantum communication channels, exactly solve the problem for any network topology in polynomial rounds and polynomial communication/time complexity with respect to the number of parties. This is joint work with Seiichiro Tani and Keiji Matsumoto.