Quantum Complexity of Testing Group Commutativity

Details Quantum Complexity of Testing Group Commutativity Quantum Complexity of Testing Group Commutativity

2005-06-30

arxiv.org/abs/quant-ph/0506265v4

Physics

Quantum Physics

10 pages, requires fullpage,amsthm,amsfonts,amsmath; To appear in Algorithmica; earlier version appeared in ICALP 2005; correc

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quantum Complexity of Testing Group Commutativity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Complexity of Testing Group Commutativity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Complexity of Testing Group Commutativity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-235637