Gottesman-Knill Theorem

The Gottesman-Knill theorem is a theoretical result in quantum computing (QC) that statesthat an important subclass of quantum circuits, called stabilizer circuits can be simulatedefficiently. That is simulation of QC algorithms that use only these circuits can be run in polynomial time on a classical computer. Stabilizer circuits are circuits that use only gates from the Clifford group subset of quantum gates.

Formally stated

Theorem: A quantum circuit using only the followingelements can be simulated efficientlyon a classical computer:
# preparation of qubits in computational basis states,
# quantum gates from the Clifford group (Hadamard gates, Controlled NOT gates, Pauli gates), and
# measurements in the computational basis.

The Gottesman-Knill theorem shows that even some highly entangled states can be simulated efficiently. Several important types of QC algorithms use only Clifford gates, most importantly the standardalgorithms for entanglement purification and forquantum error correction. From a practical point of view, stabilizer circuits have been simulated in O(n log n) time using the graph state formalism.

References

*

* "Quantum Computation and Quantum Information", Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000