Theorem 1

Theorem 1: Given the state vector of our register with one state with amplitude k, and every other state with amplitude l, after an application of A:

• the amplitude in the one state is k^' = $\left(\vphantom{\frac{2}{N} - 1 }\right.$${\frac{{2}}{{N}}}$ - 1$\left.\vphantom{\frac{2}{N} - 1 }\right)$k + 2${\frac{{(N-1)}}{{N}}}$l
• the amplitude of the remaining (N - 1) states is l^' = ${\frac{{2}}{{N}}}$k + ${\frac{{(N-1)}}{{N}}}$l

Proof: Given the definition of A as A_ij = 2/N if i $\not=$j and A_ii = - 1 + 2/N, it follows from the definition of matrix multiplication of k and l by A that:

• k^' = $\left(\vphantom{\frac{2}{N} - 1 }\right.$${\frac{{2}}{{N}}}$ - 1$\left.\vphantom{\frac{2}{N} - 1 }\right)$k + 2${\frac{{(N-1)}}{{N}}}$l
• l^' = ${\frac{{2-N}}{{N}}}$l + ${\frac{{2}}{{N}}}$k + ${\frac{{2(N-2)}}{{N}}}$l

The second expression simplifies to l^' = ${\frac{{2}}{{N}}}$k + ${\frac{{(N-2)}}{{N}}}$l with some simple algebraic manipulation. [Grover96]