3

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

glS
  • 24,708
  • 5
  • 34
  • 108
  • 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)$ – DaftWullie Mar 26 '19 at 09:48
  • 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? –  Mar 26 '19 at 09:52
  • 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. – DaftWullie Mar 26 '19 at 11:01

1 Answers1

1

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.

Alexey Krugovets
  • 160
  • 10
  • 1
    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 https://quantumcomputing.stackexchange.com/questions/5973/counting-in-q-number-of-solutions for an example of quantum counting) – Mariia Mykhailova Dec 19 '19 at 17:28
  • yes, your addition is absolutely correct here. thx – Alexey Krugovets Dec 21 '19 at 17:28