  We consider the problem of testing the commutativity of a black-box group
specified by its k generators. The complexity (in terms of k) of this problem
was first considered by Pak, who gave a randomized algorithm involving O(k)
group operations. We construct a quite optimal quantum algorithm for this
problem whose complexity is in O (k^{2/3}). The algorithm uses and highlights
the power of the quantization method of Szegedy. For the lower bound of
Omega(k^{2/3}), we give a reduction from a special case of Element Distinctness
to our problem. Along the way, we prove the optimality of the algorithm of Pak
for the randomized model.
