  This paper gives the first separation of quantum and classical pure (i.e.,
non-cryptographic) computing abilities with no restriction on the amount of
available computing resources, by considering the exact solvability of a
celebrated unsolvable problem in classical distributed computing, the ``leader
election problem'' on anonymous networks. The goal of the leader election
problem is to elect a unique leader from among distributed parties. The paper
considers this problem for anonymous networks, in which each party has the same
identifier. 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, even if it is given the number of parties. This paper gives two
quantum algorithms that, given the number of parties, can exactly solve the
problem for any network topology in polynomial rounds and polynomial
communication/time complexity with respect to the number of parties, when the
parties are connected by quantum communication links.
