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

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?

• Have you studied Grover's search at all? Sep 3, 2020 at 6:32

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.

• Thanks a lot for your help. You mention an "abuse of notation". I believe that the statement in the original paper looks a bit inaccurate. It seems to me that $|0\rangle$ should be rather stated as $|0\rangle\otimes 1$. Furthermore, in your answer, I realize that you are relating the term $1$ in terms of matrix notation to the identity matrix in the corresponding dimension. Sep 3, 2020 at 10:54
• I agree that it seems a bit inaccurate. You are right, I write $\mathbb{1}$ as the identity operator on the corresponding subsystem. Sep 3, 2020 at 11:29
• Another thing I asked myself is whether the ordering in the Kronecker product would have to be reversed in the answer, because we have $|Y\rangle=\sum_{i\in\mathbb{Z}}x_i|i\rangle |Y_i\rangle$ and not $|Y\rangle=\sum_{i\in\mathbb{Z}}x_i|Y_i\rangle |i\rangle$. Sep 3, 2020 at 11:34
• I consider $|i \rangle$ as the ‘first register‘ so I think the order is correct. Sep 3, 2020 at 11:42

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.