Lemma 1 in the paper by Brassard, Hoyer, Tapp (1998) on Quantum counting

Question

In the paper by Brassard, Hoyer, Tapp (1998) on Quantum Counting we have the following expression for the state:

$$|Y\rangle =\sum_{i\in\mathbb{Z}}x_i|i\rangle |Y_i\rangle.$$

Now we have a quantum algorithm $\mathcal{A}$. Then we have the operator $S_0^{\phi}$ which changes the phase of the state by a factor of $\phi$ if and only the first register holds a zero. The paper goes into more detail about the setup.

Lemma 1 claims that

$$\mathcal{A}S_0^{\phi}\mathcal{A}^{-1}|Y\rangle=|Y\rangle-(1-\phi)\langle Y|\mathcal{A}|0\rangle ^*\mathcal{A}|0\rangle.$$

How is this lemma arising? What is the proof for that lemma?

Answer 1

First observe that

\begin{align*} S_0^{\phi} &= \phi \cdot |0 \rangle \langle 0| \otimes \mathbb{1} + |1 \rangle \langle 1| \otimes \mathbb{1} \\ &= \phi \cdot |0 \rangle \langle 0| \otimes \mathbb{1} + \Big(\mathbb{1} - |0 \rangle \langle 0|\Big) \otimes \mathbb{1} \\ &= \mathbb{1} \otimes \mathbb{1} - (1 - \phi) \cdot |0 \rangle \langle 0| \otimes \mathbb{1} \end{align*}

So it holds that

\begin{align*} \mathcal{A} S_0^{\phi} \mathcal{A}^{-1} |Y \rangle &= |Y \rangle - (1 - \phi) \cdot \mathcal{A} \Big(|0 \rangle \langle 0| \otimes \mathbb{1}\Big) \mathcal{A}^{-1}|Y \rangle \\ &= |Y \rangle - (1 - \phi) \cdot \mathcal{A} \Big(|0 \rangle \otimes \mathbb{1}\Big) \Big(\langle 0| \otimes \mathbb{1}\Big) \mathcal{A}^{-1}|Y \rangle \\ &= |Y \rangle - (1 - \phi) \cdot \mathcal{A} \Big(|0 \rangle \otimes \mathbb{1}\Big) \Big(\langle Y| \mathcal{A} \Big(|0 \rangle \otimes \mathbb{1}\Big)\Big)^{\dagger} \end{align*} and with an "abuse of notation" the two expressions are equal.

Answer 2

Given that $\mathcal{A}$ is a unitary matrix, $\mathcal{A}^{-1} = \mathcal{A}^*$ $$ \begin{aligned} \mathcal{A}S_{0}^{\phi}\mathcal{A}^{-1}|Y\rangle = & \mathcal{A}(I - (1-\phi)|0\rangle\langle0|)\mathcal{A}^{-1}|Y\rangle \\ =& |Y\rangle - (1-\phi)\mathcal{A}|0\rangle\langle0|\mathcal{A}^{-1}|Y\rangle\\ =& |Y\rangle - (1-\phi)\mathcal{A}|0\rangle\langle0|\mathcal{A}^{*}|Y\rangle \\ =& |Y\rangle - (1-\phi)\mathcal{A}|0\rangle\langle Y|\mathcal{A}|0\rangle^* \end{aligned} $$ That leads to the result.