Quantum Complexity of Testing Group Commutativity

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 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.

10 pages, requires fullpage,amsthm,amsfonts,amsmath; To appear in Algorithmica; earlier version appeared in ICALP 2005; corrects minor typos, results are unchanged

References in corpus (1)

• A quantum lower bound for the collision problem

Cited by in corpus (12)

• Search via Quantum Walk
• Quantum speedup of classical mixing processes
• Quantum walks can find a marked element on any graph
• Hitting time for the continuous quantum walk
• Almost uniform sampling via quantum walks
• The Quantum Query Complexity of Algebraic Properties
• Quantum Property Testing of Group Solvability
• Efficient quantum walk on the grid with multiple marked elements
• Quantum Algorithm for Commutativity Testing of a Matrix Set
• Quantum search with variable times
• Quantum Property Testing for Solvable Groups
• Quantum Complexity Bounds for Independent Set Problems