The Stabilizer Tableau

A stabilizer tableau stores a stabilizer state as a binary matrix, letting Clifford operations and measurements be simulated in polynomial time.

Representing a state by its stabilizers

A stabilizer state on n qubits is uniquely specified by n independent commuting Pauli operators that fix it. The stabilizer tableau records these operators as rows of a binary matrix. Each row holds 2n bits, an x-block and a z-block encoding the X and Z content of that Pauli, plus one sign bit for the +-1 phase. The full tableau, following Aaronson and Gottesman, also tracks n destabilizer rows to make measurement updates efficient.

Updating under Clifford gates

Clifford gates map Paulis to Paulis, so their effect on the tableau is a fixed linear update of the bits. A Hadamard on qubit q swaps that qubit's x and z columns; a phase gate S adds one column into another; a CNOT copies bits between control and target columns. Each update touches O(n) bits, so applying a Clifford gate costs O(n) time. This is the computational heart of the Gottesman-Knill theorem.

• Rows are stabilizer generators; each is 2n bits plus a sign bit.
• Clifford gates act as simple column operations on the tableau.
• Gate update: O(n); measurement update: O(n^2) in the worst case.
• Destabilizer rows make measurement outcomes fast to compute.

# Sketch: Hadamard on qubit q swaps x and z bits of column q
for row in tableau.rows:
    row.x[q], row.z[q] = row.z[q], row.x[q]
    row.sign ^= row.x[q] & row.z[q]

Measurement and uses

Measuring a qubit in the computational basis is also efficient: check whether the measured Pauli commutes with all stabilizers (a deterministic outcome) or anticommutes with some (a random outcome, followed by a row update). Either way the cost is polynomial. Tableaus power fast stabilizer simulators used to estimate logical error rates, to test decoders on large codes, and to verify circuit constructions.

The tableau is the concrete data structure behind the stabilizer formalism: it turns abstract commutation relations into bit operations, which is why researchers can simulate distance-30 surface codes on a laptop even though the underlying Hilbert space is astronomically large.