I Why is the Phase Shift in Grover's Algorithm Applied to All Elements Except 0?

[Peter_Newman]

Hi everybody,

I've read some pages in Nielsens "Quantum Computing" book, it's very interesting, but especially at Grover's algorithm, there occurs a question for me. It is said that a phase shift is performed, which is defined as follows:

$|0\rangle \rightarrow |0\rangle \\ |x\rangle \rightarrow -|x\rangle \\ \text{for } x>0$

But now I'm wondering why the phase shift is applied to all elements except 0. Why is that, what effect does that have? I have already read something, but so far no one could answer me why you omit the 0.

I would be glad, if someone can tell me why this is how it does it.

 

[DrClaude]

Are you talking about the book by Nielsen and Chuang?

In any case, could you indicate precisely where this appears? It doesn't look like what I know about how oracles work.

 

[Peter_Newman]

Yes, I am talking about Nielsen and Chuang. I have here a link to a page where the same circuit from Nielsen and Chuang is displayed:
http://www.users.csbsju.edu/~lziegler/CS317I/GroversAlgorithm.html
Why does one apply the phase shift to all states except 0?

So first of all you apply the oracle that exactly tilts the state that is sought.
$$(-1)^{f(x)}|x\rangle$$
Then you applie the Hadamard transformation and the Grover Iterator and finally the Hadamard transformation agian. If I understand it correctly, then you can rewrite the expression as well:
$$H^{n}(2|0\rangle\langle0|-I)H^n=2|\psi\rangle\langle\psi|-I$$

I've seen somewhere that one can express that as a matrix (unfortunately I do not know exactly how to do that). But my guess is that if you do that in the matrix, you can directly see that the effects of this operation are just $$|0\rangle\rightarrow |0\rangle $$ $$|x\rangle \rightarrow -|x\rangle $$But it has to be said that this still does not answer the question why in all states except 0 the phase shift is applied ...

 

[cosmik debris]

I've seen somewhere that one can express that as a matrix (unfortunately I do not know exactly how to do that). But my guess is that if you do that in the matrix, you can directly see that the effects of this operation are just $$|0\rangle\rightarrow |0\rangle $$ $$|x\rangle \rightarrow -|x\rangle $$But it has to be said that this still does not answer the question why in all states except 0 the phase shift is applied ...

Aren't those two expressions just saying that all states other than the one picked out by the oracle are left alone and the one picked out is inverted?

Cheers

 

[DrClaude]

I've seen somewhere that one can express that as a matrix (unfortunately I do not know exactly how to do that). But my guess is that if you do that in the matrix, you can directly see that the effects of this operation are just $$|0\rangle\rightarrow |0\rangle $$ $$|x\rangle \rightarrow -|x\rangle $$

But that's not what the oracle does. As you started yourself, the oracle performs the operation
$$(-1)^{f(x)}|x\rangle$$
Notice the appearance of $f(x)$, not $x$. You will get
$$|0\rangle\rightarrow |0\rangle $$ $$|x\rangle \rightarrow -|x\rangle $$
only if $f(0) = 0$, $f(x\neq0) = 1$.

How the oracle works depends on the implementation. It simply needs to recognise the desired state, the one for which $f(x) = 0$. In the $| x \rangle$ basis, this is implemented as the matrix
$$
\begin{pmatrix}
-1 & 0 & \cdots \\
0 & -1 & 0 & \cdots \\
& & \ddots & \\
& & 0 & 1 & 0 & \cdots \\
& & & 0 & -1 & 0 & \cdots \\
& & & & & \ddots \\
\end{pmatrix}
$$
where the $1$ is in the row corresponding to the desired $|x\rangle$.