I know that there are papers (cf. arXiv:quant-ph/0205115) out there which prove that the Toffoli gate by itself is not enough for universal quantum computation, but I haven't had the time to go through the whole proof. Could someone give me the crux of the proof or the intuition for this?
The Toffoli gate is just a permutation. If you start in a known basis state, application of a Toffoli just changes it into another basis state, one that you can easily calculate classically (after all, it’s a decision based on looking at 3 bit values). Repeating that doesn’t change anything.
To make it universal, you need to add something like Hadamard which introduces superposition.