Question about a circuit from "Quantum Computing for Computer Scientists"

Question

I am trying to implement a basic quantum computing emulator. In the chapter on Grover's algorithm, we're shown the following circuit:

They demonstrate Grover's algorithm with a function $f$ that picks out $101$, i.e. $f(101)=1$ and $0$ otherwise. They start with $\psi_{1}=[1, 0, 0, 0, 0, 0, 0, 0]^{T}$. The Hadamard gate (specifically H tensored with itself $n$ times) gives $\psi_{2}=1/\sqrt8 [1, 1, 1, 1, 1, 1, 1, 1]^{T}$. This is as far as I've come. They don't show explicitly how to get to $\psi_{3}$, which should be $1/\sqrt8 [1, 1, 1, 1, 1, -1, 1, 1]^{T}$. I am not sure how to interpret the circuit.

My best guess was to take the tensor product of $|0 \rangle=|000 \rangle$ and $|1 \rangle = [0, 1]^{T}$, then apply $I_{2^{n}} \otimes H$, then $U_{f}$. However, I have two problems:

The book says that, at that stage in the calculation, $\psi_{3} = 1/\sqrt8 [1, 1, 1, 1, 1, -1, 1, 1]^{T}$, which has length $8$, instead of $16$. I don't know how to "extract" the "top" qubits. Furthermore, my answer is $1/4[1, 1..., 1]^{T}$, which doesn't suggest the correct answer (especially given the fact that every entry is $1/4$).

Am I misinterpreting this circuit? What is the correct way to go from $\psi_{2}$ to $\psi_{3}$, from a programmatic point of view?

Answer 1

Have you tried Quirk? It can handle things like extracting the tensor factor of intermediate states for you, so you get a sense of what you should be getting as the answer.

In general, the tensor factor may not exist because the extra qubit could be entangled with the part you're trying to extract. But if it's not entangled, which in this case it's not, then you just look at the subset of the state vector where the extra qubit is 0 and that's your answer (after normalizing) (or, if the part of the state vector where the extra qubit is 0 is all amplitudes zero, look at the subset where the extra qubit is 1).

To be more specific, what you do is group the state vector into parts keyed by the state of qubits you're not including. You then pick the part with the largest 2 norm as your reference part. This is the result you will return, normalized to have 2-norm of 1, if the state is not entangled. The state is not entangled if all the parts are parallel to each other. To verify lack of entanglement in a numerically stable way, you sum up the dot products of the reference part with all the parts (including itself). If the sum of dot products has a magnitude of 1, the state is not entangled. The sum's magnitude will get smaller as entanglement increases, though it won't necessarily get to zero.

Answer 2

As you have read, Grover's Algorithm consists of starting in an equal superposition and the applying two gates, $U_\omega$ and $U_s$, $\sqrt{n}$ times where $n$ is the number of elements.

You are looking on how to implement $U_\omega$ which gets from state $\psi_2$ to $\psi_3$. This is called a phase flipping oracle since it adds a phase of $e^{i\pi} = -1$ to the basis state which represents the correct element. The best way to do so is to apply an $X$ gate to a $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ to a separate allocated qubit, when you recognize that it is the correct basis states. This tutorial describes how do implement this gate for a graph coloring problem in Q#.

To answer some of your other questions :

• The state vector is of length 8 since there are 3 qubits which gives $2^3 = 8$ basis states.
• To implement $U_s$, here is a question which shows how to implement it in basic gates