Gottesman-Knill Theorem | Efficient Classical Clifford Simulation
Quick Technical Answer:
The Gottesman-Knill theorem proves that any quantum circuit composed exclusively of Clifford group operations (H, S, CNOT), initialized in computational basis states, and measured in the Pauli-Z basis can be simulated in polynomial time O(n²) on classical computers.
Formula / Unitary:
\mathcal{C}_n = \{ U \in U(2^n) \mid U P U^\dagger \in \mathcal{P}_n \}, \quad \text{Sim Time} = O(n^2)
Simulate this in Itachi Quantum Studio
Inspect state amplitudes, 3D Bloch sphere vector, and OpenQASM code live.
Frequently Asked Questions
What is required to make a Clifford circuit universal and classically intractable?
Adding any single non-Clifford gate (such as the T gate or Toffoli gate) immediately breaks the Gottesman-Knill conditions and elevates the computational power to universal BQP.