Editing Quantum algorithm (section)

==Algorithms based on the quantum Fourier transform==
The [[quantum Fourier transform]] is the quantum analogue of the [[discrete Fourier transform]], and is used in several quantum algorithms. The [[Hadamard transform]] is also an example of a quantum Fourier transform over an n-dimensional vector space over the field [[GF(2)|'''F'''<sub>2</sub>]]. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number of [[Quantum logic gate#Hadamard transform|quantum gate]]s.{{citation needed|date=February 2018}}

===Deutsch–Jozsa algorithm===
{{main|Deutsch–Jozsa algorithm}}

[[File:Deutsch-Jozsa-algorithm-quantum-circuit.png|thumb|Deutsch-Jozsa algorithm]]
The Deutsch–Jozsa algorithm solves a [[black-box]] problem that requires exponentially many queries to the black box for any deterministic classical computer, but can be done with a single query by a quantum computer. However, when comparing bounded-error classical and quantum algorithms, there is no speedup, since a classical probabilistic algorithm can solve the problem with a constant number of queries with small probability of error. The algorithm determines whether a function ''f'' is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half).

===Bernstein–Vazirani algorithm===
{{main|Bernstein–Vazirani algorithm}}

The Bernstein–Vazirani algorithm is the first quantum algorithm that solves a problem more efficiently than the best known classical algorithm. It was designed to create an [[oracle separation]] between [[BQP]] and [[BPP (complexity)|BPP]].

===Simon's algorithm===
{{main|Simon's algorithm}}

Simon's algorithm solves a black-box problem exponentially faster than any classical algorithm, including bounded-error probabilistic algorithms. This algorithm, which achieves an exponential speedup over all classical algorithms that we consider efficient, was the motivation for [[Shor's algorithm]] for factoring.

===Quantum phase estimation algorithm===
{{main|Quantum phase estimation algorithm}}

The [[quantum phase estimation algorithm]] is used to determine the eigenphase of an eigenvector of a unitary gate, given a quantum state proportional to the eigenvector and access to the gate.   The algorithm is frequently used as a subroutine in other algorithms.

===Shor's algorithm===
{{main|Shor's algorithm}}

Shor's algorithm solves the [[discrete logarithm]] problem and the [[integer factorization]] problem in polynomial time,<ref>
{{cite journal
 | last = Shor | first = P. W.
 | year = 1997
 | title = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
 | journal = [[SIAM Journal on Scientific and Statistical Computing]]
 | volume = 26 | issue = 5
 | pages = 1484–1509
 | arxiv = quant-ph/9508027
 | bibcode= 1995quant.ph..8027S
 | doi=10.1137/s0097539795293172
| s2cid = 2337707
 }}</ref> whereas the best known classical algorithms take super-polynomial time. It is unknown whether these problems are in [[P (complexity)|P]] or [[NP-complete]]. It is also one of the few quantum algorithms that solves a non-black-box problem in polynomial time, where the best known classical algorithms run in super-polynomial time.

===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>{{cite conference
 |last1=Boneh |first1=D.
 |last2=Lipton |first2=R. J.
 |year=1995
 |title=Quantum cryptoanalysis of hidden linear functions
 |editor-last=Coppersmith |editor-first=D.
 |book-title=Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology
 |pages=424–437
 |publisher=[[Springer-Verlag]]
 |isbn=3-540-60221-6
}}</ref> The more general hidden subgroup problem, where the group is not necessarily abelian, is a generalization of the previously mentioned problems, as well as [[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
 |last1=Moore |first1=C.|author1-link=Cris Moore
 |last2=Russell |first2=A.
 |last3=Schulman |first3=L. J.
 |year=2005
 |title=The Symmetric Group Defies Strong Fourier Sampling: Part I
 |eprint=quant-ph/0501056
}}</ref> and the [[dihedral group]], which would solve certain lattice problems.<ref>{{cite arXiv
 | last = Regev | first = O.
 | date = 2003
 | title = Quantum Computation and Lattice Problems
 | eprint = cs/0304005
}}</ref>

===Estimating Gauss sums===
A [[Gauss sum]] is a type of [[exponential sum]]. The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time.<ref>
{{Cite arXiv
 | last1=van Dam |first1=W.
 | last2=Seroussi |first2=G.
 | year =2002
 | title = Efficient Quantum Algorithms for Estimating Gauss Sums
 | eprint = quant-ph/0207131
}}</ref>

===Fourier fishing and Fourier checking===
Consider an [[Oracle machine|oracle]] consisting of ''n'' random Boolean functions mapping ''n''-bit strings to a Boolean value, with the goal of finding n ''n''-bit strings ''z''<sub>1</sub>,..., ''z<sub>n</sub>'' such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy

:<math>| \tilde{f}(z_i)| \geqslant 1</math>

and at least 1/4 satisfy

:<math>| \tilde{f}(z_i) | \geqslant 2.</math>

This can be done in [[BQP|bounded-error quantum polynomial time]] (BQP).<ref>
{{Cite arXiv
 | last = Aaronson | first = S.
 | year = 2009
 | title = BQP and the Polynomial Hierarchy
 | class = quant-ph
 | eprint = 0910.4698
}}</ref>