patternModerate
Universality of the Toffoli gate
Viewed 0 times
gatetheuniversalitytoffoli
Problem
Regarding the quantum Toffoli gate:
- is it classicaly universal, and if so, why?
- is it quantumly universal, and why?
Solution
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 your 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, for example, it cannot implement something that takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. In other words, it cannot create superposition.
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 your 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, for example, it cannot implement something that takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. In other words, it cannot create superposition.
Context
StackExchange Computer Science Q#289, answer score: 16
Revisions (0)
No revisions yet.