Abstract
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 \(\tilde{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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Magniez, F., Nayak, A. Quantum Complexity of Testing Group Commutativity. Algorithmica 48, 221–232 (2007). https://doi.org/10.1007/s00453-007-0057-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-0057-8