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:

  1. Am I right that non-Clifford gates increase time consumption (or complexity of quantum algorithm)?
  2. 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.
  • 2
    $\begingroup$ “non-Clifford gates are not known to be efficiently simulatable.” $\endgroup$ Feb 1, 2020 at 3:02
  • $\begingroup$ '...simulated on classical computer', with access to randomness? $\endgroup$ Apr 28 at 21:38
  • $\begingroup$ @QuestionEverything: Do you mean a true randomness or pseudo? $\endgroup$ Apr 29 at 6:16
  • $\begingroup$ the original paper only mentions 'randomness'... not sure whether is pseudo or not... $\endgroup$ Apr 30 at 2:40
  • $\begingroup$ If pseudo, then we can assume that the computer definitely has the access. Generator of true randomness are also available (even based on quantum processes), so we can assume even that. Does this somehow change efficiency of non-Clifford gates simulation? $\endgroup$ Apr 30 at 7:17

1 Answer 1

  1. Yes, you are correct. Non-Clifford gates cannot be transversely implemented, instead implementation generally requires distilling magic states or Toffoli states. In practice this requires significantly more spacetime volume than Clifford gates. For reference, see the introduction sections here and here.

  2. The natural expectation would be that no quantum gates can be simulated efficiently by classical computers since an n-qubit quantum circuit operates in a $2^n$-dimensional Hilbert space. The (arguably) surprising result is that circuits consisting only of Clifford gates can be simulated efficiently (by the Gottesman-Knill Theorem). It's a very natural situation that non-Clifford gates cannot be simulated efficiently because of the size of Hilbert space in which they operate. If both Clifford and non-Clifford gates could be simulated efficiently by classical computers, there would be no (or at least drastically reduced) motivation to build quantum computers.

  • 2
    $\begingroup$ Point 1 ist incorrect. Error correction codes with transversal non-Clifford gates exist. The correct statement is that all transversally implementable gate sets must be finite and thus non universal. However, gate sets different from the Clifford group are possible. $\endgroup$ Nov 24, 2023 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.