Universality of the Toffoli gate

Problem Detail: Regarding the quantum Toffoli gate:

  1. is it classicaly universal, and if so, why?
  2. is it quantumly universal, and why?
Asked By : Ran G.

Answered By : Artem Kaznatcheev

Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like $P = BQP$). To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary $epsilon$ and target unitary $U$ there is some way to apply a finite number of you quantum gates to get a unitary $U'$ such that $||U – U'|| < epsilon$. Toffoli by itself is clearly not universal under this definition since it always takes basis states to basis states, and thus can not implement something that takes $|0rangle rightarrow frac{1}{sqrt{2}}(|0rangle + |1rangle)$ for example. In other words, it cannot create superposition.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/289