2
$\begingroup$

I have two gates here for the Grover diffusion operator. The first gate is completely understandable for me, so I implemented it myself after submitting some papers that I read. This is the first gate (understandable for me):

enter image description here

Recently, however, I have seen an implementation of the Grover algorithm in which the diffusion operator still uses the oracle qubit. My question is, what does this circuit do? And why does it work?

enter image description here

$\endgroup$
2
$\begingroup$

Let's take a look at the part of the diffusion operator between the columns of Hadamard gates. This part is supposed to perform a conditional phase shift, giving a phase of $-1$ to the state $|0...0\rangle$ and leaving the rest of the basis states unmodified.


For the first circuit, the bottom 3 wires are controls, wrapped in NOT gates, i.e., they are anti-controls: the operator applied on the 4th wire from the bottom only if each of the bottom 3 wires is in the $|0\rangle$ state. The operator performed on the 4th wire in this case is described by this circuit (two of the three NOT gates in the middle cancel right away):

enter image description here

Here are the transformations done by this circuit to a qubit in the starting state $\alpha |0\rangle + \beta |1\rangle$:

$$\alpha |0\rangle + \beta |1\rangle \xrightarrow{\oplus} \beta |0\rangle + \alpha |1\rangle \xrightarrow{\text{H}} \beta |+\rangle + \alpha |-\rangle \xrightarrow{\oplus} \beta |+\rangle - \alpha |-\rangle \xrightarrow{\text{H}} \beta |0\rangle - \alpha |1\rangle \xrightarrow{\oplus} -\alpha |0\rangle + \beta |1\rangle$$

This is exactly what we're looking for - a $-1$ phase applied to the $|0...0\rangle$ state.


For the second circuit, the bottom 3 wires are already anti-controls, so the circuit we need to apply to the top two wires is the following:

enter image description here

The transformation is the following:

$$(\alpha |0\rangle + \beta |1\rangle) \otimes |-\rangle = \frac{1}{\sqrt2} (\alpha |0\rangle |0\rangle - \alpha |0\rangle |1\rangle + \beta |1\rangle |0\rangle - \beta |1\rangle |1\rangle \xrightarrow{\text{CNOT}_0} $$

$$\frac{1}{\sqrt2} (\alpha |0\rangle \color{blue}{|1\rangle} - \alpha |0\rangle \color{blue}{|0\rangle} + \beta |1\rangle |0\rangle - \beta |1\rangle |1\rangle = (\color{blue}{-} \alpha |0\rangle + \beta |1\rangle) \otimes |-\rangle$$

This transformation applies the same conditional phase shift to the bottom wire and does not modify the $|-\rangle$ state of the top wire, so it turns out to be equivalent to the first circuit.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.