2
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.