Content deleted Content added
→Quantum Simulation: fix grammar |
|||
Line 68:
===Hidden subgroup problem===
The [[Abelian group|abelian]] [[hidden subgroup problem]] is a generalization of many problems that can be solved by a quantum computer, such as Simon's problem, solving [[Pell's equation]], testing the [[principal ideal]] of a [[ring (mathematics)|ring]] R and [[integer factorization|factoring]]. There are efficient quantum algorithms known for the Abelian hidden subgroup problem.<ref>D. Boneh and R. J. Lipton. ''Quantum cryptoanalysis of hidden linear functions.'' In Don Coppersmith, editor, CRYPTO '95, Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, 1995.</ref> The more general hidden subgroup problem, where the group isn't necessarily abelian, is a generalization of the previously-mentioned problems and [[graph isomorphism]] and certain [[lattice problems]]. Efficient quantum algorithms are known for certain non-abelian groups. However, no efficient algorithms are known for the [[symmetric group]], which would give an efficient algorithm for graph isomorphism,<ref>{{cite arxiv|eprint=quant-ph/0501056|author1=Cristopher Moore|author2=Alexander Russell|last3=Schulman | first3=Leonard J.|title=The Symmetric Group Defies Strong Fourier Sampling: Part I|class=quant-ph|year=2005|author3=Schulman}}</ref> and the [[dihedral group]], which would solve certain lattice problems.<ref>{{Cite arxiv
| last = Regev
| first = Oded
| |||