# Computing of the action of the amplification operator $\mathbf Q$ over $|\Psi_i\rangle$ in the quantum amplitude amplification algorithm


Given the state $|\Psi\rangle\equiv\A|0\rangle$, the authors define the states $|\Psi_i\rangle$, for $i=0,1$, as $$|\Psi_i\rangle\equiv\Pi_i|\Psi\rangle=\Pi_i\A|0\rangle.$$

The first lemma in the paper, at the end of page 5, states that \begin{align} \Q|\Psi_1\rangle&=(1-2a)|\Psi_1\rangle-2a|\Psi_0\rangle, \\ \Q|\Psi_0\rangle&=2(1-a)|\Psi_1\rangle+(1-2a)|\Psi_0\rangle, \end{align} where $a=\langle\Psi_1|\Psi_1\rangle$.

The action of $\Q$ over $|\Psi_i\rangle$ does not seem obvious. For example, $$\Q|\Psi_0\rangle=-\A\S_0\A^{-1}\S_\chi|\Psi_0\rangle =-\A\S_0\A^{-1}|\Psi_0\rangle,$$ but then already $\A^{-1}$ acts nontrivially on $|\Psi_0\rangle$.

How is $\Q|\Psi_i\rangle$ computed?

The trick here is to not calculate $\mathcal{A}^{-1}|\Psi\rangle$ at all, because it's insufficiently defined! Instead, look at $$\mathcal{A}(\mathbb{I}-2|0\rangle\langle 0|)\mathcal{A}^{-1}=\mathbb{I}-2\mathcal{A}|0\rangle\langle 0|\mathcal{A}^{-1}$$ by the fact that $\mathcal{A}$ is unitary. Now, by definition, $$\mathcal{A}|0\rangle=|\Psi_0\rangle+|\Psi_1\rangle$$ Thus, we have $$\mathcal{A}(\mathbb{I}-|0\rangle\langle 0|)\mathcal{A}^{-1}=\mathbb{I}-2(|\Psi_0\rangle+|\Psi_1\rangle)(\langle\Psi_0|+\langle\Psi_1|).$$ Now you can calculate the effect of this on any input state. Just remember that the states $|\Psi_0\rangle$ and $|\Psi_1\rangle$ are not normalised.