Editing Quantum algorithm (section)

===Group commutativity===
The problem is to determine if a [[black box group|black-box group]], given by ''k'' generators, is [[Commutativity|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). The interest in this context lies in the query complexity, which is the number of oracle calls needed to solve the problem. The deterministic and randomized query complexities are <math>\Theta(k^2)</math> and <math>\Theta(k)</math>, respectively.<ref>
{{cite journal
 |last=Pak |first=Igor |author1-link=Igor Pak
 |year=2012
 |title=Testing commutativity of a group and the power of randomization
 |journal= [[LMS Journal of Computation and Mathematics]]
 |volume=15 |pages=38–43
 |doi=10.1112/S1461157012000046
 |doi-access=free
 }}</ref> A quantum algorithm requires <math>\Omega(k^{2/3})</math> queries, while the best-known classical algorithm uses <math>O(k^{2/3} \log k)</math> queries.<ref>
{{cite journal
 |last1=Magniez |first1=F.
 |last2=Nayak |first2=A.
 |year=2007
 |title=Quantum Complexity of Testing Group Commutativity
 |journal=[[Algorithmica]]
 |volume=48 |issue=3 |pages=221–232
 |doi=10.1007/s00453-007-0057-8
|arxiv=quant-ph/0506265|s2cid=3163328
 }}</ref>