# What is the reasoning behind the Toffoli gate implementation?

I am studying quantum computing and came to the implementation of the Toffoli gate. I can't find anywhere what is the reasoning behing this derivation. What confuses me the most is the need of the gates in the control qubits. Why is this needed? The constrol qubits ahould not be changed throughout the sequence? Any reference on this?

• (A) The two control qubits (at the top) do revert back to their original state - the other $T$ and $T^\dagger$ gates move into and out of the right space, after/before the CNOT gates. These are (akin to) "uncomputation" steps. (B) For some more information see this question. (C) You can also explore circuits with Quirk here. Commented Feb 9, 2022 at 1:58
• Quirk circuit in detail here Commented Feb 9, 2022 at 1:58
• The answer here could be helpful: quantumcomputing.stackexchange.com/a/18277/9474 Commented Feb 9, 2022 at 10:29

If you look in Nielsen & Chuang, it does take all the key ingredients you need to get to the construction, you've just got to fill in a lot of detail. Your circuit diagram is their Figure 4.9. If you look at Figure 4.8 and use $$U=X$$, you'll get a construction for the toffoli. With a little bit of circuit manipulation, it comes out as the circuit you want.
As for the specific reason for a bunch of gates only on the control qubits, imagine I've actually managed to implement controlled-controlled-$$iX$$ instead of toffoli. How do I fix this? I need to apply a phase of $$-i$$ if and only if the two control qubits are both 1 (and the target qubit is irrelevant at that point). This is essentially what is going on with that last part of the circuit.