$\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?


1 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*}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.