Quantum Computing Asked on August 31, 2021
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:
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.
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.
Correct answer by Jonathan Trousdale on August 31, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP