Understanding implemetation of the Toffoli gate using other gates

Question

I have a system with three qubits as input and I want to demonstrate this equality:

where the left part of the equal is the circuit representation of the Toffoli gate where the first two lines are the control qubits and the third one is the target. On the right side we have the CNOT gate whose matrix representation is

$$ CNOT=\left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{array}\right)$$

T,S and H are the $\dfrac{\pi}{8}$ gate,phase gate and Hadamard gate, respectively, represented by the matrixes

$$H=\dfrac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1\\ 1 & -1 \end{array}\right), S=\left(\begin{array}{cc} 1 & 0\\ 0 & i \end{array}\right), T=\left(\begin{array}{cc} 1 & 0\\ 0 & exp(i\pi/4) \end{array}\right)$$

The Toffoli gate is supposed to do this

My problem is that I don't know how, given some input, for example, the three qubits in the state |1>, the circuit acts on the input. For example, in the second control qubit there is a CNOT gate, so what I have to do is calculate the direct sum of |1> and the qubit which is below it once it has passed through the H gate? This is, before the target qubit reach $T^{\dagger}$, we have the state $|1>|1\oplus H|1>>=-\dfrac{1}{\sqrt{2}}|1>(|0>-|1>)$

Is this correct?

Answer 1

When applying quantum operations you always:

• Simplify everything down to individual self-contained cases.
• Apply the operation separately to each case.
• Recombine the answers.

So, in the case of applying a CNOT to the state $|1\rangle \otimes (H \cdot |1\rangle)$, you:

• Simplify things. We don't want that $H$ in the way. Apply it. The state is $|1\rangle \otimes (\frac{1}{\sqrt 2}|0\rangle - \frac{1}{\sqrt 2}|1\rangle)$.
• Separate things. Distribute the tensor product over the subtraction. The state is $\frac{1}{\sqrt 2}|1\rangle \otimes |0\rangle - \frac{1}{\sqrt 2}|1\rangle \otimes |1\rangle$. Or, for short, just $\frac{1}{\sqrt 2}|10\rangle - \frac{1}{\sqrt 2}|11\rangle$.
• Apply the operation separately to each case. If the second bit is our control, then in $|10\rangle$ the control isn't satisfied and nothing happens while in $|11\rangle$ the control is satisfied and we toggled to $|01\rangle$. Apply that to each part of $\frac{1}{\sqrt 2}|10\rangle - \frac{1}{\sqrt 2}|11\rangle$ and you end up with $\frac{1}{\sqrt 2}|10\rangle - \frac{1}{\sqrt 2}|01\rangle$.
• None of our output cases overlapped when being added together, so there's no need to combine anything.

You might get a sense of this by adding state displays to Quirk while it cycles through the inputs into your Toffoli circuit.