Quantum Computing Asked on December 30, 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:**

- 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.*

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.

Answered by Jonathan Trousdale on December 30, 2021

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP