Strong classical simulation of a quantum circuit

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.