3
$\begingroup$

In the chapter about the Grover algorithm, it is suggested that the gate which executes the phase shift is given in the following form:

enter image description here

Now I have looked at this gate in detail and come to the conclusion that this "only" negates the state $|00\rangle$, but not all others, this can be shown for different inputs $|00\rangle$, $|01\rangle$, $|10\rangle$, $|11\rangle$ (the gate changes only $|00\rangle$ to -$|00\rangle$) or see here. I'm sorry, because in the chapter it says a few pages earlier: $|x\rangle$ becomes $-|x\rangle$ and $|0\rangle$ remains to $|0\rangle$ (picture left section). But that does not correspond to the circuit (picture right section). That's why I ask myself, what is right now? I want to do this a bit further, we say the Grover operator is:

$$H^{\otimes n}(2|0\rangle\langle 0|-I)H^{\otimes n}$$

That means I have several Hadamard transformations before and then do the phase shift, followed by Hadamard transformations. I think that you can see this in $(2|0\rangle\langle 0|-I)$ (matrix with 1 in the first row, all other rows -1), that $|x\rangle$ becomes $-|x\rangle$ and $|0\rangle$ stays $|0\rangle$. But that does not correspond to the circuit (picture right).

$\endgroup$
  • $\begingroup$ An overall minus sign (global phase), makes no difference no the final outcome. So it doesn't matter if you make $(2|0\rangle\langle 0|-I)$ or $-(2|0\rangle\langle 0|-I)$ $\endgroup$ – DaftWullie Mar 26 '19 at 9:48
  • $\begingroup$ I almost thought so. So that means, if I would use the loop in the form (top right), then probably my solution amplitude would be negative, right? But that does not make any difference because a minus in front of the state does not change, because the measurement is calculated in the amount $| \alpha |^2$, ok? $\endgroup$ – user4961 Mar 26 '19 at 9:52
  • $\begingroup$ Yes, exactly. Indeed, given you'll be repeating this operation, if you happen to repeat it an even number of times, the sign would disappear anyway. $\endgroup$ – DaftWullie Mar 26 '19 at 11:01
1
$\begingroup$

You are absolutely right. The picture in the right section correspond to the picture in the left section up to the unimportant global phase factor (-1). This fact mentioned in the Exercise 6.6.

The Box 6.1 use only one Grover iteration, so that $|ψ\rangle$ after this Grover iteration will be rotated to the (-$|x\rangle$) instead of $|x\rangle$ as in the general Grover algorithm. But this does not has any impact to the final result because the probability to find an $|x\rangle$ use the amplitude squire.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ As a note, the global phase factor is unimportant if one uses the iteration in Grover algorithm itself. If used as a building block for other algorithms, that extra -1 can pop out unexpectedly and cause a nice long debugging session... (see quantumcomputing.stackexchange.com/questions/5973/… for an example of quantum counting) $\endgroup$ – Mariia Mykhailova Dec 19 '19 at 17:28
  • $\begingroup$ yes, your addition is absolutely correct here. thx $\endgroup$ – Alexey Krugovets Dec 21 '19 at 17:28

Your Answer

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