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$
3
  • $\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, 2019 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, 2019 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, 2019 at 11:01

1 Answer 1

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.

$\endgroup$
2
  • 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$ Dec 19, 2019 at 17:28
  • $\begingroup$ yes, your addition is absolutely correct here. thx $\endgroup$ Dec 21, 2019 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.