Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00453-007-0057-8 | Algorithmica |
Keywords | Field | DocType |
Markov Chain,Group Element,Quantum Algorithm,Query Complexity,Quantum Walk | Randomized algorithm,Discrete mathematics,Abelian group,Combinatorics,Property testing,Upper and lower bounds,Quantum computer,Quantum walk,Quantum algorithm,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
48 | 3 | 0178-4617 |
ISBN | Citations | PageRank |
3-540-27580-0 | 20 | 1.14 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frédéric Magniez | 1 | 570 | 44.33 |
| Ashwin Nayak | 2 | 645 | 61.76 |