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

Question

$\newcommand{\Q}{\mathbf{Q}}\newcommand{\S}{\mathbf{S}}\newcommand{\A}{{\mathcal A}}\newcommand{\H}{\mathcal H}$In the quantum amplitude amplification algorithm, as explained in Brassard et al. 2000 (quant-ph/0005055), the unitary performing the amplification is defined as (using the notation found in pag 5 of the above paper): $$\Q=-\A\S_0\A^{-1}\S_\chi,$$ where $\A$ is a unitary, $\chi:\mathbb Z\to\{0,1\}$ is a Boolean function, and $\S_\chi$ and $\S_0$ are unitaries defined as $$\S_\chi\equiv I-2\Pi_1,\quad \S_0\equiv I-|0\rangle\langle0|,$$ where $\Pi_i$ is the projector over the states $|x\rangle$ for which $\chi(x)=i$: $$\Pi_i\equiv\Pi_{\chi(x)=i}\equiv\sum_{x:\,\chi(x)=i}|x\rangle\langle x|.$$

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?

Answer 1

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.

Hence, \begin{align*} Q|\Psi_0\rangle&=-\left(\mathbb{I}-2(|\Psi_0\rangle+|\Psi_1\rangle)(\langle\Psi_0|+\langle\Psi_1|)\right)|\Psi_0\rangle \\ &=-\left(|\Psi_0\rangle-2(|\Psi_0\rangle+|\Psi_1\rangle)(1-a)\right) \\ &=2(1-a)|\Psi_1\rangle+(1-2a)|\Psi_0\rangle \end{align*}