Theorem 2

Theorem 2: Let the state vector before step 2a of Grover's algorithm be as follows:

• For the unique marked state S_m which satisfies C(S_m) = 1 the amplitude is k such that 0 < k < 1/$\sqrt{{2}}$

• For each of the remaining (N - 1) states the amplitude is l such that l > 0

In this case we seek to prove both:

• The change in k, $\Delta$k after steps 2a and 2b in Grover's algorithm is bounded below by $\Delta$k > ${\frac{{1}}{{2\sqrt{N}}}}$
• After steps 2a and 2b in Grover's algorithm l > 0

Proof: Let the initial amplitudes be k and l, let the amplitudes after the selected phase inversion step 2a be k^' and l^', let the amplitudes after the inversion about average step 2b be k^'' and l^''.

By theorem 1 we know k^'' = $\left(\vphantom{1-\frac{2}{N} }\right.$1 - ${\frac{{2}}{{N}}}$$\left.\vphantom{1-\frac{2}{N} }\right)$k + 2${\frac{{(N-1)}}{{N}}}$l (note the reversal of terms in the coefficient of k, this is due to the phase inversion of k in step 2a), therefore $\Delta$k = k^'' - k = - ${\frac{{2k}}{{N}}}$ +2$\left(\vphantom{1-\frac{1}{N}}\right.$1 - ${\frac{{1}}{{N}}}$$\left.\vphantom{1-\frac{1}{N}}\right)$l. By the assumption 0 < k < 1/$\sqrt{{2}}$ and Corollary 1.2 it follows that | l| > ${\frac{{1}}{{\sqrt{2N}}}}$. By assumption l is positive, thus l > ${\frac{{1}}{{\sqrt{2N}}}}$. Combining this with $\Delta$k = k^'' - k = - ${\frac{{2k}}{{N}}}$ +2$\left(\vphantom{1-\frac{1}{N}}\right.$1 - ${\frac{{1}}{{N}}}$$\left.\vphantom{1-\frac{1}{N}}\right)$l. it follows that $\Delta$k > ${\frac{{1}}{{2\sqrt{N}}}}$. [Grover96]

To show l^'' positive consider after step 2a of the algorithm, after the selective phase inversion, but before the inversion about average. At this point k^' < 0 and l^' > 0, since $\left(\vphantom{0 < k < \frac{1}{2\sqrt{N}} }\right.$0 < k < ${\frac{{1}}{{2\sqrt{N}}}}$$\left.\vphantom{0 < k < \frac{1}{2\sqrt{N}} }\right)$ and | l| > ${\frac{{1}}{{\sqrt{2N}}}}$ (from previous paragraph) that $\left\vert\vphantom{\frac{k^{'}}{l^{'}}}\right.$${\frac{{k^{'}}}{{l^{'}}}}$$\left.\vphantom{\frac{k^{'}}{l^{'}}}\right\vert$ < $\sqrt{{N}}$. This means that after step 2a our register is in a state covered by Corollary 1.1, which states after the inversion about average operation l^'' will be positive.