Quantum Search Algorithm

By examining this operator in the instance of $|\Psi\rangle = \frac{1}{2} \left(|00\rangle +|01\rangle+|10\rangle+|11\rangle \right)$, i.e. the equal superposition of two qubits, and a post-phase-flip state $|k\rangle_2 = \left(a_{00}|00\rangle +a_{01}|01\rangle+a_{10}|10\rangle+a_{11}|11\rangle \right)$, we expect to preview the behavior of this so called phase-shift operator. The general form of this transformation is $\displaystyle{(2 |\Psi\rangle \langle\Psi| - I) |k\rangle_n = 2 |\Psi\rangle \langle\Psi||k\rangle_n - |k\rangle_n}$. For a clear writing, the part before the minus sign will be evaluated first.

$$|\Psi\rangle \langle\Psi||k\rangle_n$$ $$\begin{matrix} = & \frac{1}{2}\left(|00\rangle + |01\rangle + |10\rangle + |11\rangle \right) \times \frac{1}{2}\left(\langle00| + \langle01| + \langle10| + \langle11| \right) \left(a_{00}|00\rangle +a_{01}|01\rangle+a_{10}|10\rangle+a_{11}|11\rangle \right) \\ = & \frac{1}{2}\left(|00\rangle + |01\rangle + |10\rangle + |11\rangle \right) \times \frac{1}{2} \left(a_{00} +a_{01}+a_{10}+a_{11} \right) \\ = & \displaystyle{\left(\frac{1}{2^2}\sum_{k=0}^{2^2-1}a_k \right) \sum_{x=0}^{2^2-1}|x\rangle}\end{matrix}$$

This leads to a generalization: $$\displaystyle{2 |\Psi\rangle \langle\Psi||k\rangle_n = 2\cdot\left(\frac{1}{2^n}\sum_{k=0}^{2^n-1}a_k \right) \sum_{x=0}^{2^n-1}|x\rangle = \sum_{x=0}^{2^n-1} 2\langle a \rangle |x\rangle}$$ , where $\displaystyle{\langle a \rangle \equiv \frac{1}{2^n}\sum_{k=0}^{2^n-1}a_k}$ is the mean value of $a_k$’s. Finally, $$\begin{matrix}(2 |\Psi\rangle \langle\Psi| - I) |k\rangle_n & = & (2 |\Psi\rangle \langle\Psi| - I) \displaystyle{\sum_{k=0}^{2^n-1}} a_k |k\rangle\\ & = & \displaystyle{\sum_{k=0}^{2^n-1}} (2\langle a \rangle - a_k) |k\rangle\end{matrix}$$ Arithmetically, $2u-v$ inverses $v$ about $u$ (figure)

so that $2\langle a \rangle - a_k$ inverses $a_k$ about the average value of amplitudes. For this reason, operator $2 |\Psi\rangle \langle\Psi| - I$ is sometimes called as inversion about mean operator.