2

I am currently working on the Grover algorithm and have a few questions.

In the third step of the algorithm, a phase shift is performed on all states, except $|0\rangle$. My question is, why is the state $|0\rangle$ omitted here?

And then I would like to know how to show that the unitary operator corresponding to the phase shift in the Grover iteration is $2|0\rangle\langle0|-I$. I do not know how to show it exactly but my idea was: Lets say in this example: $2|0\rangle\langle0|-I=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$ For example, if I apply the $|0\rangle$ and $|1\rangle$ states now, then this results in: $\begin{pmatrix}1&0\\0&-1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}1\\0\end{pmatrix}$ And for the other state $|1\rangle$: $\begin{pmatrix}1&0\\0&-1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}=\begin{pmatrix}0\\-1\end{pmatrix}$ This means that on the state $|0\rangle$ the operator does not cause a phase shift, but already on the last one $|1\rangle$. But is that enough to show that the unitary operator corresponding to the phase shift in the Grover iteration is $2|0\rangle\langle0|-I$?

I hope that my question is understandable. Thanks for coming answers.

PS: If anyone still has good sources regarding the Grover algorithm, I would be very happy if they could send me a link to good documentation, just to dig deeper into the subject matter.

glS
  • 27,510
  • 7
  • 37
  • 125
P_Gate
  • 678
  • 3
  • 17

2 Answers2

4

The third step applies a phase shift to all states except $|0\rangle$ so that steps 2-4 taken together would perform inversion about mean. This is not the only possible choice for these steps; this question has an excellent answer detailing the logic behind this choice and several alternatives.


For the second part of the question, both operators are defined on all basis states, albeit in a different manner. You can just check that the effect of both definitions on all basis states is the same; this would mean that the operators are the same.

Mariia Mykhailova
  • 9,285
  • 1
  • 13
  • 40
2

The reason behind the choice of $\lvert 0^{\otimes n}\rangle$ as reference state, found in many basic treatments of Grover's algorithm, is best understood by considering the technique that generalizes it: the so-called quantum amplitude amplification.

The goal of amplitude amplification is a very generic one: given some initial state $\lvert\psi_{in}\rangle$, we want to transform it into a state that belongs to a given target subspace $\mathcal H_{target}$. The initial state $\lvert\psi_{in}\rangle$ is assumed to be known, but $\mathcal H_{target}$ needs not be (and can indeed be seen as the goal of the algorithm).

This is consistent with what you have in the special case of Grover's algorithm with $\lvert\psi_{in}\rangle=\lvert+,\cdots,+\rangle=H^{\otimes n}\lvert 0,\cdots, 0\rangle$ and $\mathcal H_{target}=\mathbb C\lvert \psi_{target}\rangle$ one-dimensional and encoding the state that we are trying to find, and given only indirectly via oracular access to a function $f$ such that $f(x)=1$ iff $x=\lvert\psi_{target}\rangle$, and $f(x)=0$ otherwise.

In the general amplitude amplification scheme, the way we get from the initial to the target space is via repeated application of a pair of two reflections, $-S_t S_i$, where $$S_i\equiv 2\lvert \psi_{in}\rangle\!\langle \psi_{in}\rvert-I, \\ S_t\equiv 2\lvert \psi_{t}\rangle\!\langle \psi_{t}\rvert-I,$$ and we used the notation $\lvert\psi_t\rangle\simeq\sum_{x\in\mathcal H_{target}}\lvert x\rangle$.

As it turns out, the product of two reflections amounts to a rotation in state space: $$\newcommand{\ketbra}[1]{\lvert #1\rangle\!\langle #1\rvert} R\equiv-S_t S_i=-4\ketbra{\psi_{in}}\psi_{t}\rangle\!\langle \psi_t\rvert +2(\ketbra{\psi_{in}}+\ketbra{\psi_t})-I,$$ which brings the initial state $\lvert\psi_{in}\rangle$ closer to the target, as long as the initial overlap is not too big to begin with: $$R\lvert\psi_{in}\rangle=(1-4\lvert\langle\psi_{in}\rvert\psi_{t}\rangle\rvert^2 )\lvert\psi_{in}\rangle+2\langle\psi_t\rvert\psi_{in}\rangle\lvert\psi_t\rangle,$$ $$\langle\psi_{in}\rvert R\lvert\psi_{in}\rangle=1-2\lvert\langle\psi_{in}\rvert\psi_{t}\rangle\rvert^2.$$ You can then verify how repeated applications of $R$ get you closer and closer to the target.

This shows how there is nothing special about the choice of $\lvert0\rangle$ often used: what is needed is a pair of reflections, one with respect to the initial state and the other with respect to the projector over the target state/space.

Why does the operator corresponding to the phase shift in Grover's algorithm correspond to $2\ketbra0-I$?

Let $\lvert\psi\rangle$ be any state, and define $S\equiv 2\ketbra\psi-I$. Then, $$S\lvert\psi\rangle=2\lvert\psi\rangle-\lvert\psi\rangle=\lvert\psi\rangle,$$ while for any $\lvert\phi\rangle$ such that $\langle\phi\rvert\psi\rangle=0$, $$S\lvert\phi\rangle=-\lvert\phi\rangle.$$

glS
  • 27,510
  • 7
  • 37
  • 125