Constructing a Toffoli gate with 2-and 1-qubit gates?

Question

I'm looking through Nielson's book on quantum computation and information and in part of it he says that any $C^2(U)$ gate can be constructed from two qubit and one qubit gates. I can't figure out how to do this, or how to verify it (fig 4.8 in his book) I've attached a photo of the diagram:

Also: Is there an easier way to do this than multipyling 8x8 matricies? Right now I represent the first gate as $ I_1 \otimes\begin{pmatrix} I & 0 \\ 0 & V \end{pmatrix}_{23}$

where $I$ is the identity matrix in for one qubit, and $V$ satisfies $V^2 = U$. $U$ is the unitary matrix being applied.

Answer 1

Generally, you can get pretty far in these problems thinking of the circuit like a classical computer problem. That is, think about what effect this circuit would have on the following 4 quibits:

$$ |00 \psi \rangle,|01 \psi \rangle,|10 \psi \rangle,|11 \psi \rangle$$

Now think about the action that the circuit will have on these states. For the first state, what gates will the circuit apply to the third quibit? It will apply no gates.

But what about the second state? The circuit will apply a V gate to Psi and then a V-dagger gate, undoing the first action.

If you examine all of these, you can see the action of the circuit.

Generally, however, you must be much more careful because quantum circuits work for all states, not just ones in the computational basis. However, even if your initial state is in a superposition of basis states, the effect of the circuit will be a to transform your initial state to a superposition of solutions.

If we asked what effect the above circuit will have on the state $$ |+0 \psi \rangle,$$ we could quickly see that it will be a superposition of the effect on states $$|00 \psi \rangle, and |10 \psi \rangle$$.

I appologize for my abuse of LaTeX. This if my first time with it.

Answer 2

Quantum gates act linearly, so the operation of these two circuits on any input qubits is a linear combination of their operation on the eight basis qubits $|000 \rangle,|001 \rangle, |010 \rangle \dots|111 \rangle$. To verify that these two circuits are equivalent, you only have to show that they have the same effect on those eight qubits.

I don't know of any way to come up with that circuit on my own, except by trial and error. I'm sure if you work with quantum logic long enough you start to develop an intuition of what sorts of things work better than others.