Exact Quantum Algorithms for the Leader Election Problem

Date/Time: 16 March 2005 - ()

Speaker: Hirotada Kobayashi (ERATO, Japan)

It is well-known that no classical algorithm can solve exactly (i.e., in bounded time without error) the leader election problem in anonymous networks. This paper proposes two quantum algorithms that, when the parties are connected by quantum communication links, can exactly solve the problem for any network topology in polynomial rounds and polynomial communication/time complexity with respect to the number of parties. Our algorithms work well even in the case where only the upper bound of the number of parties is given.