Motivation
An arbitrary state of many qubits requires exponentially many amplitudes to write down. Some states have a shorter description: specify commuting observables whose values are all known, and let those equations determine the state. For example, the Bell state is the unique state with eigenvalue one for both and . This description retains its correlations without listing four amplitudes, and the same idea scales to many qubits.
A short description is useful for simulation only if it can be updated efficiently. We must show how gates transform the equations, how a measurement changes them, and how its probability is obtained. Signs matter throughout. The operators and have the same pattern of nonidentity tensor factors but opposite measurement meanings.
We develop a generator-only tableau with an explicit four-valued phase. It is slightly different from the common sign-bit convention, so every update is derived from its stated operator order. The resulting algorithm proves an exact simulation statement for computational-basis inputs, specified Clifford gates and Pauli measurements. It does not simulate an arbitrary quantum circuit, nor does it write down an exponentially long probability table.
Definitions
Let
Definition 4.1.1
(Pauli row encoding)
For binary vectors and , encode a Pauli by
The order is all factors before all factors. In particular the single-qubit row represents , while represents . Add binary coordinates modulo two, written ; add phase exponents modulo four. Dot products inside phase formulas mean integer sums before the indicated modular reduction.
Definition 4.1.2
(Stabilizer state)
A pure stabilizer state is specified by commuting independent Hermitian Pauli generators , with no in the generated group. Independence means their binary row vectors have rank ; this superscript labels a generator, while a subscript labels a qubit coordinate. The state is the normalized common eigenvector, unique up to global phase. To check uniqueness, expand the projector . Independence makes every nonempty product a nonidentity Pauli and hence trace zero. The projector has trace one and therefore rank one.
Definition 4.1.3
(Tableau and Clifford conjugation)
The tableau here is simply these rows, each containing binary coordinates and a two-bit phase. A Clifford unitary conjugates the Pauli group to itself. We use
and controlled-NOT, defined by . If the state changes by , a stabilizer changes by . Measuring a Hermitian Pauli means the two projectors with outcomes .
Theorem/Proposition
Theorem 4.1.4
(Pauli arithmetic with its phase retained)
The product rule is
Two rows commute exactly when modulo two. A row is Hermitian exactly when modulo two.
Theorem 4.1.5
(Conjugation updates in this convention)
Apply the following rule to every generator row. All coordinates on the right are the old values, and unspecified entries are unchanged:
These gates are Clifford, and conjugated rows specify the evolved state. The absence of a CNOT phase update belongs to this ordered--then- convention; it is not a rule for every tableau convention.
Theorem 4.1.6
(Pauli measurement on a pure stabilizer state)
If some generator anticommutes with , both outcomes have probability . Choose such a pivot . For each other generator anticommuting with , replace it by , using the original pivot and the phase-correct product rule. Leave the other rows unchanged, then replace the pivot by for the sampled outcome . These rows describe the normalized measured state.
If every generator commutes with , solve over for a product of generators with the same binary coordinates as . The actual signed product is either or . The corresponding outcome is respectively or , with certainty, and the state is unchanged.
Theorem 4.1.7
(The simulation statement proved here)
Starting with a computational-basis product state, a circuit of , controlled-NOT and encoded Hermitian Pauli measurements can be sampled exactly using bits of storage and polynomial classical time. A generator-only implementation takes per listed gate and at most per measurement using binary Gaussian elimination. Adaptive gate choices remain covered when their classical control is computable in polynomial time from the previous outcomes.
This is a constructive Gottesman–Knill statement for the specified ideal circuit model. We prove the update invariants and sampling probabilities below. We do not prove that every abstract Clifford unitary can be synthesized from this gate set, the faster destabilizer-tableau algorithms, arbitrary mixed/noisy inputs, or simulation after unrestricted non-Clifford gates. Efficiently sampling a record is also different from printing all possible records.
Proof sketch or proof idea
Proof
(Signs from reordering Pauli factors)
The only sign needed for multiplication comes from moving past . Each overlapping pair contributes a minus sign, yielding . Reversing the factors gives the commutation test. Taking the adjoint reverses and conjugates its phase, so Hermiticity requires , exactly the stated parity condition. Multiplying commuting stabilizer rows preserves Hermiticity; multiplying arbitrary anticommuting rows need not.
Proof
(Verifying the single-qubit and CNOT updates)
For the gates, direct matrix multiplication gives , , and . Hadamard therefore reverses the local order of an and a and contributes to the phase. The phase gate contributes and adds the old bit to the bit. This proves both single-qubit rules, including their signs when the local factor is .
Checking controlled-NOT on basis states gives
All transformed factors can still be placed before all transformed factors without crossing an and a : they already arrive in that order. Hence the binary updates need no change of . Unitary conjugation preserves products, commutation and the common eigenspace, so it preserves the tableau's state meaning.
Proof
(Random measurement outcome and the new generators)
For a random measurement, the anticommuting pivot gives
The two projector probabilities are therefore equal. The normalized branch is . Each unchanged commuting generator stabilizes this branch. Each product of two anticommuting generators commutes with and also stabilizes it. Finally has eigenvalue one on the selected branch. The modified nonpivot rows remain independent and span an -dimensional subspace of the old binary row space. The measurement vector is not in that space, since it anticommutes with the old pivot whereas every old row-space vector commutes with the old pivot. Adding the measurement row restores rank . The branch is nonzero, so the new group cannot contain . Thus the rows specify exactly the normalized branch, not merely some constraints it satisfies.
Proof X-ray
Clear with the old pivot before replacing it
The product of two old rows anticommuting with the measurement commutes with it. That is the cancellation the update needs. Replacing the pivot first destroys this argument: multiplying an anticommuting row by the new measurement row can produce an anti-Hermitian operator. Save the original pivot, perform all clearings with the exact Pauli product, and only then install the signed measured observable.
Proof
(Deterministic measurement by maximality)
The deterministic case uses maximality, not just a commutation slogan. Let be the old binary row space with the bilinear form
The form is nondegenerate: pairing with the coordinate and vectors detects every coordinate. Therefore its orthogonal complement has dimension . Commutation gives , and equal dimensions give equality. A measurement commuting with every row consequently lies in . Binary elimination finds its coefficients. Multiplying the signed rows then determines whether the result is or ; Hermiticity excludes a phase difference of . This proves the deterministic probability and explains why the phases cannot be discarded after elimination.
Concept lensStructural
Stabilizer states as maximal isotropic subspaces
Ignore signs for a moment. The binary rows lie in with the form above, and independent commuting generators span a subspace with , a maximal isotropic subspace. A stabilizer state is such a subspace together with a choice of signs. For there are three subspaces, , , , and two sign choices each: six states. For there are fifteen subspaces and sixty states.
Proof
(Storage, running time and exact sampling)
For a basis input , initialize the rows as . The representation uses bits. Each listed gate touches only a fixed number of entries per row. Testing a measurement against all rows and clearing a random case take bit operations. A deterministic membership problem can be solved by ordinary binary elimination in operations, followed by phase-correct multiplication. Each random branch uses a fair coin. Since its conditional probability and new state match quantum measurement, induction and the probability chain rule prove exact sampling of the entire record. No enumeration of branches is required.
The faster algorithm of Aaronson and Gottesman keeps additional rows to avoid this elimination step. That refinement and its stronger performance bound are not proved here; our explicit generator-only algorithm already establishes polynomial simulation for the stated model.
Worked examples
Worked example 4.1.8
(A single-qubit sign survives three gates)
Start with , stabilized by , whose row is . Apply , then , then . The rows become
They represent . Hence the final state has a certain outcome when is measured. Keeping only the final binary pair would miss this sign. The sign of a stabilizer equation specifies an eigenvalue; it is not the irrelevant overall phase of a state vector.
Worked example 4.1.9
(Why an unchanged canonical phase can still mean minus YY)
Conjugate by controlled-NOT from qubit one to qubit two. Its row has , and . After the update both binary vectors are and the phase remains zero. The resulting operator is
There is no contradiction with the phase rule. Converting the canonical ordered product into local factors supplies two factors of . A convention that stores a sign in front of local labels must account for that conversion in a different place.
Worked example 4.1.10
(Bell correlations and a genuinely random first measurement)
From , apply and controlled-NOT. The initial generators become . Their product is , so measuring is deterministic with outcome .
Measuring instead anticommutes with the first generator. Each outcome has probability , and the new generators are . Their product is , so a subsequent measurement certainly has the same outcome. The branches are and . A classical sampler captures this correlation exactly; efficient stabilizer simulation does not imply the absence of entanglement.
Counterexample mode
A non-Clifford phase breaks the Pauli update
For ,
which is not a Pauli operator. The state has and expectations and expectation zero, so no nonidentity single-qubit Pauli has it as an eigenstate. Our one-row pure-state representation is not closed under this gate. This failure of the representation is not a proof that every circuit containing is classically hard; for example .
A second counterexample concerns the deterministic case rather than the gate set.
Counterexample mode
Commutation is insufficient for an incomplete code description
The single generator on two qubits specifies a code space, not a pure state. Both and the Bell state lie in it. The observable commutes with that generator, but has a certain positive outcome on the first state and uniform outcomes on the second. The deterministic-case proof required independent generators and maximal binary row space. It cannot be applied to fewer generators while ignoring the unresolved logical state.
Common mistakes
Common mistake
(Wrong conjugation direction or stale coordinates)
Use when evolving the state by . The reverse conjugation answers a different question. In the binary rules, use old coordinates on every right-hand side, then store the new row. Mixing sequentially overwritten coordinates can change the result even when the formula is correct.
Common mistake
(A generator's sign is not a global phase)
Do not identify a sum of Paulis with one Pauli, and do not confuse a generator's sign with a state's global phase. Binary elimination determines a product's support pattern, but its actual phase determines the eigenvalue. Copying phase formulas between tableau conventions without translating their represented operators is particularly unsafe.
Common mistake
(A gate outside the model does not prove hardness)
The simulator assumes ideal operations and a stabilizer input with fully specified state. It proves neither general fault tolerance nor a noise threshold. It also establishes no hardness conclusion merely from the presence of a gate outside the model. A compact representation can cease to apply without the resulting circuit automatically becoming difficult in every instance.
Summary
Pauli rows combine binary support with a phase that must survive both multiplication and conjugation. The listed Clifford gates preserve this representation. Pauli measurement is either uniform, with a pivot replacement, or deterministic, with a signed membership calculation using maximality. These facts yield an exact polynomial-time sampler for the specified ideal circuit model, while leaving synthesis, optimized tableaux and broader input/noise models outside the proved result.
Exercises
Quick check
(Compute and using the canonical product rule. Why would these products be unsuitable as Hermitian stabilizer generators without correcting their phase?)
Encode as .
Solution · Answer
Anticommuting products carry imaginary phases. For , the phase is , and the binary pair is , so . In the reverse order the crossing contribution is zero, so . Both are anti-Hermitian, consistent with multiplying these two anticommuting Hermitian operators. Stabilizer row replacement uses commuting generators, whose product remains Hermitian.
Quick check
(Start with , apply then , and measure . Give the probabilities and the new generator in each branch. What happens if is measured again?)
The premeasurement generator is .
Solution · Answer
The measurement is random once, then certain. The gates give generator . It anticommutes with , so each outcome has probability . Outcome replaces the sole generator by . The new state is therefore an eigenstate with eigenvalue , so an immediate repeated measurement has the same outcome with certainty.
Quick check
(For the Bell generators and , measure using the first generator as pivot. Both old rows anticommute with the measurement. Give the new generators and probabilities.)
Clear the second row with the original pivot before replacing it.
Solution · Answer
Clearing two anticommuting rows: the second row becomes . The new pivot is , with each having probability . These two new generators commute and are independent. The product row has canonical phase zero and both binary vectors ; reading that row as positive would be a sign error.
Quick check
(A three-qubit state has generators , and . Measure , then . Derive their correlation by generator products rather than by writing the state vector.)
The first outcome determines a new signed generator.
Solution · Answer
The three bits share one outcome. The measurement anticommutes with , so each outcome has probability . The two old -pair generators commute with it and remain. The new generator , multiplied by , gives ; multiplying again by gives . Thus the later outcome is certainly . The algebra tracks the correlation using three rows rather than eight amplitudes.