Editing Grover's algorithm (section)

== Algorithm ==
[[File:Grover's algorithm circuit.svg|500px|thumb|right|[[Quantum circuit]] representation of Grover's algorithm]]
The steps of Grover's algorithm are given as follows:
# Initialize the system to the uniform superposition over all states<br/><math>|s\rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle. </math>
# Perform the following "Grover iteration" <math>r(N)</math> times:
## Apply the operator <math>U_\omega</math>
## Apply the ''Grover diffusion'' operator <math>U_s = 2 \left|s\right\rangle\!\! \left\langle s\right| - I</math>
# [[Measurement in quantum mechanics|Measure]] the resulting quantum state in the computational basis.

For the correctly chosen value of <math>r</math>, the output will be <math>|\omega\rang</math> with probability approaching 1 for ''N'' ≫ 1. Analysis shows that this eventual value for <math>r(N)</math> satisfies <math>r(N) \leq \Big\lceil\frac{\pi}{4}\sqrt{N}\Big\rceil</math>.

Implementing the steps for this algorithm can be done using a number of gates linear in the number of qubits.<ref name=Nielsen-Chuang/> Thus, the gate complexity of this algorithm is <math>O(\log(N)r(N))</math>, or <math>O(\log(N))</math> per iteration.