# Implementing the reflection in Grover's algorithm with $\{\mathtt{CNOT}, H, X\}$

Suppose we have a boolean function $$f : \{0, \cdots, N - 1\} \to \{0, 1\}$$ and want to determine $$x$$ such that $$f(x) = 1$$ given a reduced quantum oracle $$V_f$$ defined by $$V_f | x\rangle := (-1)^{f(x)} |x\rangle \quad \forall x \in \\{0, \cdots, N-1\\}$$ Furthermore, suppose the number of $$x$$ such that $$f(x) = 1$$ is $$S \ll N$$. The description I have of Grover's search algorithm is given by

1. Prepare the system in the Fourier basis state $$e_0 = \frac{1}{\sqrt N} \sum^{N-1}_{x = 0} |x\rangle$$
2. Apply the reduced oracle $$V_f$$
3. Apply the gate $$W := 2 |e_0\rangle \langle e_0 | - I$$
4. Repeat steps 2 and 3 $$K$$ times, where $$K$$ is the closest integer to $$\frac \pi 4 \sqrt{\frac N S} - \frac 1 2$$.
5. Measure the system in the computational basis

I am trying to understand how to implement the gate $$W$$ with gates from the set $$\{\mathtt{CNOT}, X, H\}$$ in the case where $$N = 4$$. In this case, $$|e_0\rangle$$ is $$|+\rangle \otimes |+\rangle$$. I have a hint that says to consider the action of $$(I \otimes H)(\mathtt{CNOT})(I \otimes H)$$ but after trying this on $$|0\rangle \otimes |0\rangle$$ and trying to put in $$I \otimes X$$ or $$X \otimes X$$ in various places, I still can't get anywhere. My questions are then:

• How can $$W$$ be found this way?
• When answering questions related to finding the composition of gates from a gate set that implement a specific gate, it feels a lot like I'm reaching around in the dark and just performing blind symbolic manipulation until spotting a combination that works. For finding $$W$$ in particular, am I missing a more conceptual understanding that would at least give me a rough idea on how to start, e.g. related to the Bloch sphere?

First, consider that to prepare the equal superposition state $$|s\rangle$$ (which you call $$e_0$$) from the all zero state $$|0\rangle^{\otimes n}$$ all you need to do is apply a Hadamard gate to each of the $$n$$ qubits:

\begin{aligned} |s\rangle &= H^{\otimes n} |0\rangle^{\otimes n} \\ \\ |s\rangle &= \frac{1}{\sqrt{N}} \sum_{x = 0}^{N -1} |x\rangle, \end{aligned}

with $$N = 2^n$$.

Since, the Grover diffusion operator $$U_s$$ (which you call $$W$$) is given by this expression:

$$U_s = 2 |s\rangle \langle s| - I,$$

you can replace $$|s\rangle$$ (and $$\langle s|$$) resulting in:

$$U_s = 2 \, H |0\rangle \langle 0| H - I.$$

Here I have omitted the $$^{\otimes n}$$ in both the Hadamard gates and all-zero states to make the expression cleaner, but these are still for a system of $$n$$ qubits (same for the identity operator $$I$$).

Notice that since $$H H = I$$, we can sandwich the identity in the expression above without changing the result:

\begin{aligned} U_s &= 2 \, H |0\rangle \langle 0| H - H \, I \, H \\ \\ U_s &= H \left ( 2 |0\rangle \langle 0| - I \right) H \end{aligned}

Next, consider the matrix representation of the expression in between the $$H$$ gates above:

\begin{aligned} 2 |0\rangle \langle 0| - I = & \, \begin{bmatrix} 2 & 0 & \dots & 0 \\ 0 & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 0 \end{bmatrix} - \begin{bmatrix} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \end{bmatrix} \\ \\ 2 |0\rangle \langle 0| - I = & \, \begin{bmatrix} 1 & 0 & \dots & 0 \\ 0 & -1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & -1 \end{bmatrix} \\ \\ 2 |0\rangle \langle 0| - I = -1 & \, \begin{bmatrix} -1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \end{bmatrix} \\ \\ \end{aligned}

This last matrix corresponds to a gate that inverts the phase of the all-zeros state, and the pre-factor of $$-1$$ is simply associated with a global phase we can ignore. To construct this gate, you can first flip all bits with an $$X$$ gate, apply a multi-controlled $$Z$$ gate on all qubits $$\text{MC}Z$$, and then flip the bits back with another $$X$$:

$$2 |0\rangle \langle 0| - I = X \, \text{MC}Z \, X .$$

Replacing in $$U_s$$ you get the following sequence of gates.

$$U_s = H \, X \, \text{MC}Z \, X \, H,$$

where, again, all of these are being applied to all qubits.

You can construct the $$\text{MC}Z$$ gate with a $$\text{MC}X$$ where you apply $$H$$ gates before and after the target qubit (since $$Z = \,H \,X \,H$$). Here's a circuit diagram of how $$U_s$$ would look like for $$4$$ qubits:

Finally, if you really need to implement the $$\text{MC}X$$ gate out of just $$\text{C}X$$ gates, you can follow the techniques described in section 7 of the Elementary gates for quantum computation paper. But in the particular case of $$N = 4$$ (i.e., 2 qubits), the $$\text{MC}X$$ gate is just a $$\text{C}X$$ gate.