3
$\begingroup$

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?
$\endgroup$

1 Answer 1

4
$\begingroup$

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:

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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