black box group commutative algorithm oracle
The problem is to determine if a black box group, given by k generators, is commutative. A black box group is a group with an oracle function, which must be used to perform the group operations (multiplication, inversion, and comparison with identity). We are interested in the query complexity, which is the number of oracle calls needed to solve the problem. The deterministic and randomized query complexities are 



Θ
(

k

2


)


{\displaystyle \Theta (k^{2})}

 and 



Θ
(
k
)


{\displaystyle \Theta (k)}

 respectively. A quantum algorithm requires 



Ω
(

k

2

/

3


)


{\displaystyle \Omega (k^{2/3})}

 queries but the best known algorithm uses 



O
(

k

2

/

3


log
⁡
k
)


{\displaystyle O(k^{2/3}\log k)}

 queries.
