  It is well understood that the use of quantum entanglement significantly
enhances the computational power of systems. Much of the attention has focused
on Bell states and their multipartite generalizations. However, in the
multipartite case it is known that there are several inequivalent classes of
states, such as those represented by the W-state and the GHZ-state. Our main
contribution is a demonstration of the special computational power of these
states in the context of paradigmatic problems from classical distributed
computing. Concretely, we show that the W-state is the only pure state that can
be used to exactly solve the problem of leader election in anonymous quantum
networks. Similarly we show that the GHZ-state is the only one that can be used
to solve the problem of distributed consensus when no classical post-processing
is considered. These results generalize to a family of W- and GHZ-like states.
At the heart of the proofs of these impossibility results lie symmetry
arguments.
