Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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):
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?
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):
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:
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.
