Seiichiro Tani

Exact Quantum Algorithms for the Leader Election Problem

It is well-known that no classical algorithm can solve deterministically the leader election problem in anonymous networks. This paper proposes two quantum algorithms that, when parties are connected by quantum communication links, deterministically solve the problem for any network topology in polynomial rounds and polynomial communication/local-time complexity in the number of parties.