Editing Grover's algorithm (section)

== Geometric proof of correctness==
[[File:Grovers algorithm geometry.png|thumb|upright=1.4|Picture showing the geometric interpretation of the first iteration of Grover's algorithm. The state vector <math>|s\rang</math> is rotated towards the target vector <math>|\omega\rang</math> as shown.]]
There is a geometric interpretation of Grover's algorithm, following from the observation that the quantum state of Grover's algorithm stays in a two-dimensional subspace after each step. Consider the plane spanned by <math>|s\rang</math> and <math>|\omega\rang</math>; equivalently, the plane spanned by <math>|\omega\rang</math> and the perpendicular [[Bra–ket notation|ket]] <math>\textstyle |s'\rang = \frac{1}{\sqrt{N - 1}}\sum_{x \neq \omega} |x\rang</math>.

Grover's algorithm begins with the initial ket <math>|s\rang</math>, which lies in the subspace. The operator <math>U_{\omega}</math> is a reflection at the hyperplane orthogonal to <math>|\omega\rang</math> for vectors in the plane spanned by <math>|s'\rang</math> and <math>|\omega\rang</math>, i.e. it acts as a reflection across <math>|s'\rang</math>. This can be seen by writing <math>U_\omega</math> in the form of a [[Householder transformation|Householder reflection]]:

<math display="block"> U_\omega = I - 2|\omega\rangle\langle \omega|.</math>

The operator <math> U_s = 2 |s\rangle \langle s| - I</math> is a reflection through <math>|s\rang</math>. Both operators <math>U_s</math> and <math>U_{\omega}</math> take states in the plane spanned by <math>|s'\rang</math> and <math>|\omega\rang</math> to states in the plane. Therefore, Grover's algorithm stays in this plane for the entire algorithm.

It is straightforward to check that the operator <math>U_s U_{\omega}</math> of each Grover iteration step rotates the state vector by an angle of <math>\theta = 2\arcsin\tfrac{1}{\sqrt{N}} </math>. So, with enough iterations, one can rotate from the initial state <math>|s\rang</math> to the desired output state <math>|\omega\rang</math>. The initial ket is close to the state orthogonal to <math>|\omega\rang</math>:

<math display="block"> \lang s'|s\rang = \sqrt{\frac{N-1}{N}}. </math>

In geometric terms, the angle <math>\theta/2</math> between <math>|s\rang</math> and <math>|s'\rang</math> is given by

<math display="block"> \sin \frac{\theta}{2} = \frac{1}{\sqrt{N}}. </math>

We need to stop when the state vector passes close to <math>|\omega\rang</math>; after this, subsequent iterations rotate the state vector ''away'' from <math>|\omega\rang</math>, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is

<math display="block"> \sin^2\left( \Big( r + \frac{1}{2} \Big)\theta\right),</math>

where ''r'' is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore <math>r \approx \pi \sqrt{N} / 4</math>.