Exact Gottesman–Knill simulation with measurement

Before the first instruction, [F5] gives a tableau for the exact input state and transcript. This establishes the simulation invariant at prefix length zero.

A gate updates at most $2n$ rows, each with $O(n)$ bits. A measurement tests at most $n$ symplectic pairings, each in $O(n)$ bit operations. In its random case it updates at most $n$ rows by an $O(n)$ Pauli product each. In its deterministic case Gaussian elimination on a $2n$-by-$n$ binary system uses $O(n^3)$ bit operations, and multiplying at most $n$ selected rows uses $O(n^2)$. Thus every quantum instruction costs $O((n+1{)}^3)$. Initializing and writing the $n$ signed rows each takes $O((n+1{)}^2)$ bit operations because each row stores $2n+O(1)$ bits; writing the transcript takes $O(T)$. Summing instruction costs over $T$ steps, then adding initialization, output, and $C_{\mathrm{c}\mathrm{l}}$ gives $O((n+1{)}^2+T(n+1{)}^3+C_{\mathrm{c}\mathrm{l}})$. The tableau has $O((n+1{)}^2)$ bits, elimination scratch has $O((n+1{)}^2)$ bits, and the output transcript has at most $T$ bits. The register width and controller charge use the accounting in [F4]; gate and measurement instructions are counted in $T$ and charged by the bit-operation bounds just proved.

Suppose the invariant holds after a prefix of $k$ instructions. If the next instruction is a Clifford generator, [F6] conjugates every stabilizer row by the same unitary as the circuit, whose action is ordered by [F2]. If it is a Pauli measurement, [F3] supplies the finite instrument-history branch and [F7] gives its probability and updated tableau; [F8] samples a fair bit exactly in the random case and computes the signed bit in the deterministic case. Equal transcripts therefore select the same next child by [F3]. Thus the conditional transition laws agree after instruction $k+1$. A terminated branch remains in the same final state. Each simulator iteration advances to a child of the finite tree, so it reaches a leaf after at most $T$ quantum instructions. Induction through that path proves equality of the complete transcript and final ray distributions.

If $n=0$, no wire gate is admissible and [F9] makes every valid Pauli observable $I$ or $-I$. Its label is the unique zero vector, so the empty row product determines the sign and each measurement is deterministic; the tableau uses constant space. The uniform $(n+1)$ bounds therefore include this boundary.