Construction of Phase Shift Operation used in Quantum Search

Question

In Chapter 6 of "Quantum Computation and Quantum Information" Textbook by Nielsen and Chuang, Box 6.1 gives a circuit example of Quantum Search Algorithm done on a two-bit sized search space.

The Quantum Search Algorithm consists of an initial Hadamard Transformation on the two-bit input(2 wires), followed by iterations of the Grover Algorithm which itself contains a conditional phase-shift circuit.

The phase shift operation, lets call it $S$, when written in matrix form is given by:

$$S= 2|00\rangle \langle 00|-I$$ so that $S|00\rangle=|00\rangle$, and $S|x\rangle=-|x\rangle$ for $x \neq 00$

The sequence of gate operation on the input qubits are as such:
(1) Apply $X$ gate on both the 1st and 2nd bit.
(2) Apply $H$ gate on the 1st bit.
(3) Apply C-NOT gate on the 1st bit with the 2nd bit as the control bit.
(4) Do (2).
(5) Do (1).

I tried to use $|00\rangle$ as the input state for the phase shift hoping to get back $|00\rangle$.
However I got -$|00\rangle$ after the phase shift if I work out the math for such a gate sequence. These are my steps:

(1) $X_2|0\rangle_2 \otimes X_1|0\rangle_1 =|1\rangle_2|1\rangle_1$

(2) $|1\rangle_2 \otimes H_1|1\rangle_1 = |1\rangle_2 \otimes (\frac{1}{\sqrt {2}} |0\rangle_1 - \frac{1}{\sqrt{2}}|1\rangle_1)$

(3) $|1\rangle_2 \otimes X_1(\frac{1}{\sqrt{2}} |0\rangle_1 - \frac{1}{\sqrt {2}}|1\rangle_1) =|1\rangle_2 \otimes (\frac{1}{\sqrt{2}} |1\rangle_1 - \frac{1}{\sqrt {2}}|0\rangle_1) $

(4) $|1\rangle_2 \otimes H_1(\frac{1}{\sqrt{2}} |1\rangle_1 - \frac{1}{\sqrt {2}}|0\rangle_1)$ $= |1\rangle_2 \otimes \left[\frac{1}{\sqrt{2}} (\frac{1}{\sqrt{2}} |0\rangle_1 - \frac{1}{\sqrt {2}}|1\rangle_1) - \frac{1}{\sqrt {2}}(\frac{1}{\sqrt{2}} |0\rangle_1 + \frac{1}{\sqrt {2}}|1\rangle_1)\right] = |1\rangle_2\otimes -|1\rangle_1 $

(5) $-X_2|1\rangle_2 \otimes X_1|1\rangle_1 =-|0\rangle_2|0\rangle_1$

Can someone find out whats my mistake?

Answer 1

You're right! Maybe this answer is still helpful / interesting for you.

There are several sources for the Grover algorithm and the phase shift. In Nielsen and Chuang, you'll find that the circuit does something different than what the authors actually say on the previous page. Nevertheless, that does not change the final result. I would like to clarify this a bit.

Before I start a big calculation, let's summarize what the Grover algorithm is all about. In the Grover algorithm, two elements are important. This is the oracle on the one hand and the conditional phase shift on the other hand.

I try to reduce the mathematical calculations to the minimum. Suppose we are looking for an element of four elements. The searched element is $|11\rangle$.

We start with a equal superposition over all states:

$$|\psi_0\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$$

The oracle negates the amplitude of the searched element. Important the oracle recognizes a solution for the search problem, so the oracle does the following:

$$|\psi_1\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$

Next, the Hadamard transform is used, as can be seen quite well on the circuit shown in Nielsen & Chuang.

$$|\psi_2\rangle=\frac{1}{2}(H|00\rangle+H|01\rangle+H|10\rangle-H|11\rangle)$$ $$=\frac{1}{4}(|00\rangle + |01\rangle + |10\rangle +|11\rangle \\ + |00\rangle - |01\rangle+|10\rangle-|11\rangle \\ +|00\rangle+|01\rangle-|10\rangle-|11\rangle \\ -|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$ $$=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$

Now the conditional phase shift is applied, which means: $|00\rangle\rightarrow|00\rangle, |x\rangle\rightarrow -|x\rangle$ therefore:

$$|\psi_3\rangle=\frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle)$$

The Hadamard-Transformation is to apply: $$H|\psi_3\rangle=\frac{1}{2}(H|00\rangle-H|01\rangle-H|10\rangle+H|11\rangle)$$

Now results in a calculation, which is very similar to the previous one, I abbreviate the times something and write only the result:

$$\frac{1}{4}(4|11\rangle)=|11\rangle$$

If you measure the register at this point you will see state $|11\rangle$ with 100% probability!

But lets get back to the circuit that you have analyzed. The quantum circuit does the following: $|00\rangle \rightarrow -|00\rangle, |x\rangle \rightarrow |x\rangle$ Now I apply this rule to this: $$|\psi_2\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$ I get: $$|\psi_3\rangle=\frac{1}{2}(-|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$ Now the Hadamard transformation has to be executed again: $$H|\psi_3\rangle=\frac{1}{2}(-H|00\rangle+H|01\rangle+H|10\rangle-H|11\rangle)$$ If one calculates this now, one gets the following: $$\frac{1}{4}(-4|11\rangle)=-|11\rangle$$

In summary, this means that the difference between the regulations is really just another sign. However, this does not matter in the measurement, since only the magnitude square of the amplitude plays a role.

In fact, this is a bit strange in Nielsen and Chuang. Since the circuit shown there actually implements the last rule. You have also recognized that correctly.

So in a nutshell: Whether this $|0\rangle\rightarrow|0\rangle, |x\rangle\rightarrow-|x\rangle$ or $|0\rangle\rightarrow-|0\rangle, |x\rangle\rightarrow|x\rangle$ (at the phase shift operator) here is used is "no matter". The difference is only the sign. Granted, if you look at Nielsen and Chuang's first pages on the Grover algorithm, then the real implementation is a bit confusing to the reader. But you analyzed the circuit absolutely correctly.