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 $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ for example. In other words, it cannot create superposition.

Best Answer from StackOverflow

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