There are two groups of quantum gates - Clifford gates and non-Clifford gates.
Representatives of Clifford gates are Pauli matrices $I$, $X$, $Y$ and $Z$, Hadamard gate $H$, $S$ gate and $CNOT$ gate. Non-Clifford gate is for example $T$ gate and Toffoli gate (because its implementation comprise $T$ gates).
While Clifford gates can be simulated on classical computer efficiently (i.e. in polynomial time), non-Clifford gates cannot. Moreover (if my understanding is correct), non-Clifford gates increase time consumption of a quantum algorithm far more than Clifford gates.
My questions are these:
- Am I right that non-Clifford gates increase time consumption (or complexity of quantum algorithm)?
- Why non-Clifford gates cannot be simulated efficiently? This is confusing for me, because $S$ and $T$ gates are both rotations with only different angle.