Quantum Complexity of Testing Group Commutativity
<|reference_start|>Quantum Complexity of Testing Group Commutativity: 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.<|reference_end|>
@article{magniez2005quantum,
    title={Quantum Complexity of Testing Group Commutativity},
    author={Frederic Magniez (CNRS-LRI) and Ashwin Nayak (U. Waterloo and
  Perimeter Inst.)},
    journal={arXiv preprint arXiv:quant-ph/0506265},
    year={2005},
    archivePrefix={arXiv},
    eprint={quant-ph/0506265},
    primaryClass={quant-ph cs.DS}
}