Clifford gate

A Clifford gate is a unitary operation that normalizes the Pauli group: conjugating any Pauli operator by it produces another Pauli operator. Hadamard, phase, and controlled-$Z$ gates generate the Clifford operations.

A Clifford circuit is composed entirely of Clifford gates. It maps Pauli operators to Pauli operators in the Heisenberg picture and stabilizer states to stabilizer states in the Schrödinger picture.

The Gottesman--Knill theorem gives a classical polynomial-time simulation of quantum computations built from stabilizer-state preparation, Clifford gates, and adaptive Measurements of Pauli observables.

The extended Gottesman--Knill theorem allows arbitrary product-state inputs to a unitary Clifford circuit. Computational-basis output is weakly simulable for any number of measured qubits and strongly simulable for logarithmically many measured qubits.

A Clifford frame records a known Clifford transformation classically instead of applying it physically. Updating the frame changes the Pauli observables used for later measurements while preserving the represented quantum computation.

A local Clifford operation is a tensor product of one-qubit Clifford gates. On graph states, local Clifford operations implement graph transformations such as local complementation.

A strong classical simulation computes a quantum circuit's specified output probabilities in classical polynomial time to the requested polynomial precision. This is stronger than weak simulation, which only samples from the output distribution.

To compute a single-qubit output probability of a Clifford circuit, propagate its measured Pauli observable backward through the circuit. Every conjugation remains a tensor-product Pauli, whose expectation on a product state factors into efficiently computable one-qubit expectations.

For the binary phase representation of a Pauli string, these local rules implement $P\mapsto U^{†}PU$ for the Hadamard gate and the phase gate $S=\mathrm{diag}(1,i)$. In particular $S^{†}XS=-iXZ$, so the phase update differs in sign from forward conjugation. Use the old input bits, and reduce $s$ modulo four.

A weak classical simulation samples in classical polynomial time from the output distribution of a quantum circuit, exactly or within a prescribed small total-variation distance.