3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You also speak of steps 2-4, just so we're talking about the same thing, but which source you're referring to exactly. (Although the algorithm is similar in process, what source do you refer to there). Just so that I can understand that :) $\endgroup$ – P_Gate Jan 25 at 17:30
  • $\begingroup$ Nielsen and Chuang :-) Steps 2 and 4 are applying the Hadamard transform. $\endgroup$ – Mariia Mykhailova Jan 25 at 18:57
2
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ Ok, I could partly understand your last calculation, but what does that say exactly? So S does not change any other state $\Psi$ but it changes a state $\phi$ that is orthogonal to $\Psi$, but what does that mean? How do I have to imagine that? $\endgroup$ – P_Gate Jan 25 at 17:27
  • $\begingroup$ define "imagine". You can visualize the reflections as, well, reflections, in the state space. You can find a picture with this representation for example in the wikipedia page en.wikipedia.org/wiki/… $\endgroup$ – glS Jan 25 at 17: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.