# Tag Info

### Twirling Quantum Channels: Pauli and Clifford Twirling

Definitions Denoting the Haar measure of some function $f\left(x\right)$ over $d$-dimensional unitaries as $\int_{\mathrm U\left(d\right)}f\left(x\right)d\mu\left(x\right)$, twirling some arbitrary ...
• 3,397
Accepted

### Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

To my mind, this theorem is not very well stated in this form, if taken out of context. Where it says "phase gates", this may be misleading. It means specifically just $S=\sqrt{Z}$ and not what I ...
• 46.1k
Accepted

### Why are non-Clifford gates more complex than Clifford gates?

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 ...
• 3,167

### Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

Another way to think about this: To simulate what goes on in a quantum computer we have to do a lot of matrix math using $(2^N \times 2^N)$ matrices$^1$, and the action of (most) of the clifford gates ...
• 4,527
Accepted

### Is it possible to construct Grover search from Clifford gates only?

The diffusion operator is a multi controlled not operation (modulo some hadamards). It's not a Clifford operation. Also any useful oracle you'd use with Grover's algorithm won't be Clifford operations ...
• 21.8k
Accepted

### Gottesman Knill theorem: why $O(n^2)$ classical operation to keep track of a Clifford gate

You can pretty easily prove by counting that specifying a stabilizer operation or a stabilizer state requires $\Omega(n^2)$ bits. If you're not tracking some of those bits, your simulator is ...
• 21.8k