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?

  • $\begingroup$ Have you studied Grover's search at all? $\endgroup$
    – DaftWullie
    Sep 3, 2020 at 6:32

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$
    – user823
    Sep 3, 2020 at 10:54
  • $\begingroup$ I agree that it seems a bit inaccurate. You are right, I write $ \mathbb{1} $ as the identity operator on the corresponding subsystem. $\endgroup$
    – tsgeorgios
    Sep 3, 2020 at 11:29
  • $\begingroup$ 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$. $\endgroup$
    – user823
    Sep 3, 2020 at 11:34
  • $\begingroup$ I consider $ |i \rangle $ as the ‘first register‘ so I think the order is correct. $\endgroup$
    – tsgeorgios
    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.


Your Answer

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

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