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 '20 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.

  • $\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$ – Tintin Sep 3 '20 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 '20 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$ – Tintin Sep 3 '20 at 11:34
  • $\begingroup$ I consider $ |i \rangle $ as the ‘first register‘ so I think the order is correct. $\endgroup$ – tsgeorgios Sep 3 '20 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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