The problem is to determine if a black box [[Group (mathematics)|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). 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 <math>\Theta(k^2)</math> and <math>\Theta(k)</math> respectively.<ref>{{Cite web |last=Pak |first=Igor |title=Testing commutativity of a group and the power of randomization |year=2000 |url=http://www.math.ucla.edu/~pak/papers/Approx1.ps |postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}}</ref> A quantum algorithm requires <math>\Omega(k^{2/3})</math> queries but the best known algorithm uses <math>O(k^{2/3} \log k)</math> queries.<ref>{{cite journal |last1=Magniez |first1=Frederic |last2=Nayak |first2=Ashwin |year=2007 |title=Quantum Complexity of Testing Group Commutativity |journal=Algorithmica |volume=48 |issue=3 |pages=221–232 |publisher=Springer-Verlag New York, Inc. |doi=10.1007/s00453-007-0057-8 |url=http://portal.acm.org/citation.cfm?id=1275137.1275139}}</ref>
==BQP-complete problems==
Line 179:
| pages = 427–436
| date =
| origyear =
| year = 2006
| month =
Line 186 ⟶ 185:
| archivedate =
| doi = 10.1145/1132516.1132579
}}
| postscript = <!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}} }}
</ref> which as far as we know, is hard to compute classically in the worst case scenario.
===Quantum Simulation===
The idea that quantum computers might be more powerful than classical computers originated in Richard Feynman's observation that classical computers seem to require exponential time to simulate many-particle quantum systems.<ref>{{Cite journal | last1=Feynman | first1=Richard P. | author1-link=Richard Feynman | title=Simulating physics with computers | year=1982 | journal=International Journal of Theoretical Physics | volume=21 | page=467 | postscript=<!--None-->|bibcode = 1982IJTP...21..467F |doi = 10.1007/BF02650179 | issue=6–7 }}</ref> Since then, the idea that quantum computers can simulate quantum physical processes exponentially faster than classical computers has been greatly fleshed out and elaborated. Efficient (that is, polynomial-time) quantum algorithms have been developed for simulating both Bosonic and Fermionic systems<ref>{{Cite journal | doi=10.1103/PhysRevLett.79.2586 | last1=Abrams | first1=D.S. | last2=Lloyd | first2=Seth | author2-link=Seth Lloyd | title=Simulation of many-body Fermi systems on a universal quantum computer | publisher=APS | year=1997 | journal=[[Physical Review Letters]] | volume=79 | issue=13 | pages=2586–2589 | postscript=<!--None--> | bibcode=1997PhRvL..79.2586A|arxiv = quant-ph/9703054 }}. {{arXiv|quant-ph/9703054}}</ref> and in particular, the simulation of chemical reactions beyond the capabilities of current classical supercomputers requires only a few hundred qubits.<ref>{{Cite journal | doi=10.1073/pnas.0808245105 | last1=Kassal | first1=I. | last2=Jordan | first2=S.P. | last3=Love | first3=P.J. | last4=Mohseni | first4=M. | last5=Aspuru-Guzik | first5=A. | title=Polynomial-time quantum algorithm for the simulation of chemical dynamics | year=2008 | journal=[[Proceedings of the National Academy of Sciences|Proceedings of the National Academy of Sciences of the United States of America]] | volume=105 | issue=48 | pages=18681–18686 | pmid=19033207 | pmc=2596249 | postscript=<!--None-->|bibcode = 2008PNAS..10518681K }}.|arxiv= {{arXiv|0801.2986}}</ref> Quantum computers can also efficiently simulate topological quantum field theories.<ref>{{Cite journal | doi=10.1007/s002200200635 | last1=Freedman | first1=Michael | last2=Kitaev | first2=Alexei | last3=Wang | first3=Zhenghan | title=Simulation of Topological Field Theories by Quantum Computers | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | year=2002 | journal=Communications in Mathematical Physics | volume=227 | issue=3 | pages=587–603 | postscript=<!--None-->|arxiv = quant-ph/0001071 |bibcode = 2002CMaPh.227..587F }}</ref> In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating "quantum" topological invariants such as Jones<ref>{{Cite journal | doi=10.1007/s00453-008-9168-0 | last1=Aharonov | first1=Dorit | last2=Jones | first2=V. | last3=Landau | first3=Z. | title=A polynomial quantum algorithm for approximating the Jones polynomial | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | year=2009 | journal=Algorithmica | volume=55 | issue=3 | pages=395–421 | postscriptarxiv=<!--None-->}}. {{arXiv|quant-ph/0511096}}</ref> and HOMFLY<ref>{{Cite journal | last1=Wocjan | first1=P. | last2=Yard | first2=J. | title=The Jones polynomial: quantum algorithms and applications in quantum complexity theory | year=2008 | journal=Quantum Information and Computation | volume=8 | issue=1 | pages=147–180 | postscriptarxiv==<!--None-->}}. {{arXiv|quant-ph/0603069}}</ref> polynomials, and the Turaev-Viro invariant of three-dimensional manifolds.<ref>{{Cite journal | last1=Alagic | first1=G. | last2=Jordan | first2=S.P. | last3=Koenig | first3=R. | last4=Reichardt | first4=Ben W. | title=Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation | year=2010 | postscriptarxiv=<!--None-->}}. {{arXiv|1003.0923}}</ref>
