Skip to main content
1 of 2
Artem Kaznatcheev
  • 4.9k
  • 2
  • 27
  • 57

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.

Artem Kaznatcheev
  • 4.9k
  • 2
  • 27
  • 57