# Constructing a Toffoli gate with qubit gates?

1. Feb 24, 2013

### randomafk

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:
http://i.minus.com/i1JWvF4bKP1N1.png [Broken]

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.

Last edited by a moderator: May 6, 2017
2. Feb 26, 2013

### McLaren Rulez

I think it's easier to look at input combinations of 00 01 10 and 11 for the first two qubits. You can easily see that only for 11 do you have V^2 acting on the target. 00 does nothing to the target qubit while 01 and 10 have V and V-dagger acting in succession which is an identity operation.

That verifies it, but it doesn't help you construct it. I'm not too sure how one would think of a systematic way to go from the circuit on the left to the one on the right.