Stabilizer Circuits and Gottesman–Knill Simulation

Let $H_n=({\mathbb{C}}^2{)}^{\otimes n}$ be an ordered $n$-qubit register, let $\rho \in M_{2^n}(\mathbb{C})$ be a density operator, and let $M\in M_{2^n}(\mathbb{C})$ be a Hermitian Pauli observable with $M^2=I$. For $b\in \{0,1\}$ define

$P_b:=\frac{I+(-1{)}^{b}M}{2},p_b:=\mathrm{Tr}(\rho P_b),{\mathcal{I}}_b(\rho ):=P_b\rho P_b\mathrm{.}$

The outcome $b$ has probability $p_b$. Its conditional density operator is ${\rho }_b:={\mathcal{I}}_b(\rho )\mathrm{/}{p}_b$ when $p_b>0$; it is $\mathrm{\perp }$ (no assigned conditional density operator) when $p_b=0$. The branch map ${\mathcal{I}}_b$ is the projective measurement instrument for the $(-1{)}^b$ eigenspace of $M$. A non-Hermitian phase-aware Pauli is outside this definition. For $n\ge 1$, Hermiticity of $P(k,x,z)=i^k{X}^x{Z}^z$ means $k\equiv x\cdot z(\mathrm{m}\mathrm{o}\mathrm{d}2)$; in particular $Y=iXZ$ is admitted. For $n=0$, the admitted observables are $I_{H_0}$ and $-I_{H_0}$.

The hypotheses and meanings of density operator, Pauli observable, projective measurement, POVM outcome law, and instrument are the cited suppliers. The local projector calculation is Pauli measurement projectors and total probability ↗.

Ronald de Wolf, Quantum Computing: Lecture Notes, §20.2, PDF pp. 186–188, defines the two Pauli eigenspace projectors and their outcome probabilities: https://arxiv.org/pdf/1907.09415.

John Watrous, Understanding Quantum Information and Computation, Lesson 14, §14.1, printed pp. 405–407 (PDF pp. 411–413), treats a Hermitian Pauli tensor as a two-outcome observable: https://jhwatrous.github.io/UQIC.pdf.

Let $H$ be a nonzero finite-dimensional complex inner-product space, let $\rho$ be a density operator on $H$, and let $M$ be a Hermitian Pauli observable on $H$ with $M^2=I_H$. For $b\in \{0,1\}$ set

$P_b:=\frac{I_H+(-1{)}^{b}M}{2},p_b:=\mathrm{Tr}(\rho P_b)\mathrm{.}$

Then $P_0,P_1$ are complementary orthogonal projections and $p_0,p_1\ge 0$, with $p_0+p_1=1$.

The two projectors and the two-outcome probabilities are treated in de Wolf, §20.2, PDF pp. 186–188, and Watrous, Lesson 14 §14.1, printed pp. 405–407 (PDF pp. 411–413). The finite-dimensional trace manipulations above are proved locally from the cited matrix trace suppliers.

Let $V={\mathbb{F}}_2^{2n}$ have the standard symplectic form $\omega ((x,z),(x^{\mathrm{\prime }},z^{\mathrm{\prime }}))=x\cdot z^{\mathrm{\prime }}+z\cdot x^{\mathrm{\prime }}$. If $L\le V$ is isotropic and $r=\dim L$, then

$\dim L^{\perp }=2n-r\mathrm{.}$

Consequently $r\le n$, and if $r=n$ then

$L^{\perp }:=\{v\in V:\omega (v,\mathrm{\ell })=0\text{ for every }\mathrm{\ell }\in L\}=L\mathrm{.}$

The symplectic label space and its self-orthogonality are treated in de Wolf §20.1 and Aaronson–Gottesman §II. The dimension argument above is supplied locally from the current batch-15 symplectic-form definition; that supplier is present as a draft body and is not independently accepted.

For an ordered register of $n$ qubits, a stabilizer subgroup is an abelian subgroup $S$ of the Hermitian $n$-qubit Pauli operators such that $-I\mathrm{\notin }S$. The binary label of a phase-aware Pauli $P(k,x,z)$ is $(x,z)\in {\mathbb{F}}_2^{2n}$. Define the rank of $S$ by

$\mathrm{rank}(S):={\dim }_{{\mathbb{F}}_2}\mathrm{span}\{(x,z):P(k,x,z)\in S\}\mathrm{.}$

The binary label convention and commutation form are supplied by the cited Pauli items. Stabilizer labels form an isotropic space of the same rank ↗ proves that this label span is isotropic, its dimension is independent of any generating set, and $\mathrm{\mid }S\mathrm{\mid }=2^{\mathrm{rank}(S)}$. Matrix multiplication gives the phase-aware Pauli group operation by Pauli product and adjoint. For $n=0$, the Pauli group is the empty-register convention of Pauli group on the empty register.

De Wolf §20.1, PDF pp. 185–186, and Watrous Lesson 14 §§14.1 and 14.3, printed pp. 403–404 and 415–416 (PDF pp. 409–410 and 421–422), describe commuting Pauli stabilizer groups, independence, and exclusion of $-I$: https://arxiv.org/pdf/1907.09415; https://jhwatrous.github.io/UQIC.pdf.

Let $H$ be a nonzero finite-dimensional complex inner-product space and let $M$ be a Hermitian Pauli observable on $H$ with $M^2=I_H$. Put $P_b=(I_H+(-1{)}^{b}M)\mathrm{/}2$ and define ${\mathcal{I}}_b(X)=P_{b}X{P}_b$ for $b\in \{0,1\}$. Then the maps $({\mathcal{I}}_0,{\mathcal{I}}_1)$ form a finite instrument from $H$ to $H$. For every density operator $\rho$ on $H$, the outcome weight of branch $b$ is $\mathrm{Tr}(\rho P_b)$.

Watrous Lesson 14 §14.1, PDF pp. 405–407, treats the two Pauli branches as a projective measurement; de Wolf §20.2, PDF pp. 186–188, gives their branch maps and probabilities. Complete positivity and trace preservation are verified locally from the block definition and the two projector identities.

Let $H$ be a nonzero finite-dimensional complex inner-product space, let $\rho$ be a density operator on $H$, and let $M$ be a Hermitian Pauli observable on $H$ with $M^2=I_H$. For $b\in \{0,1\}$ put $P_b=(I_H+(-1{)}^{b}M)\mathrm{/}2$ and $p_b=\mathrm{Tr}(\rho P_b)$. If $p_b>0$, then the normalized branch

${\rho }_b:=\frac{P_b\rho P_b}{p_b}$

is a density operator.

Watrous Lesson 14 §14.1, printed pp. 405–407 (PDF pp. 411–413), defines the projective conditional state; de Wolf §20.2, PDF pp. 186–188, gives the Pauli branch update. The positivity and trace-one check is proved locally.

Let $H$ be a nonzero finite-dimensional complex inner-product space, let $\rho$ be a density operator on $H$, and let $M$ be a Hermitian Pauli observable on $H$ with $M^2=I_H$. For $b\in \{0,1\}$ put $P_b=(I_H+(-1{)}^{b}M)\mathrm{/}2$ and $p_b=\mathrm{Tr}(\rho P_b)$. If $p_b=0$, then $P_b\rho P_b=0$. The outcome has probability zero and, under the conditional-state convention, has no normalized conditional state.

De Wolf §20.3, PDF pp. 187–188, separates deterministic outcomes from random outcomes; Watrous Lesson 14 §14.1, printed pp. 405–407 (PDF pp. 411–413), specifies the two projective branches. The zero-trace implication is proved locally using the finite spectral theorem.

Fix an ordered $n$-qubit register and a finite gate alphabet as in Finite circuit syntax and ordered wire labels. A finite adaptive Pauli-measurement circuit tree is a finite rooted tree whose leaves are terminal and whose nonterminal nodes are of one of these two types:

1. A gate node is labelled by a gate occurrence on the ordered register and has one successor. Its state update is conjugation by the global unitary assigned to that occurrence by Denotational semantics of a finite layered circuit.
2. A measurement node is labelled by a Hermitian Pauli observable $M$ and has two outgoing edges labelled $b=0,1$. On input density operator $\rho$, edge $b$ has weight $p_b=\mathrm{Tr}(\rho P_b)$ and unnormalized output $P_b\rho P_b$, where $P_b=(I+(-1{)}^{b}M)\mathrm{/}2$ as in Pauli measurement branch semantics. Its child state is $P_b\rho P_b\mathrm{/}{p}_b$ only if $p_b>0$; an edge of weight zero is impossible and has no conditional state.

The observed measurement transcript is the ordered list of measurement-edge labels on a root-to-leaf path. The tree itself specifies every later instruction from that observed history, so its classical control is deterministic. A path whose edges all have positive weights has probability equal to their product. A path passing through a zero-weight edge has probability zero, and its descendants are not evaluated because no conditional state is assigned. A leaf outputs its terminal state; a ray is assigned only on a positive-probability path whose input and gate/measurement updates remain pure.

The complementary-projector and total-probability facts for each measurement node are supplied by Pauli measurement projectors and total probability. This definition does not identify an instrument with a POVM or require uniqueness of such a POVM.

De Wolf §20.3, PDF pp. 187–188, defines measurement-controlled Clifford circuits with feed-forward from earlier outcomes. Watrous Lesson 14 §14.1, printed pp. 405–407 (PDF pp. 411–413), defines the two Pauli measurement branches. The local tree fixes the finite branch and zero-probability conventions used here.

Let $S$ be a rank-$n$ stabilizer subgroup on an ordered $n$-qubit register $H_n=({\mathbb{C}}^2{)}^{\otimes n}$. A pure stabilizer state is the unique ray in the common $+1$ fixed space

$\mathcal{C}(S):=\{\psi \in H_n:g\psi =\psi \text{ for every }g\in S\}\mathrm{.}$

The cited projector-rank theorem proves that this common space is nonzero and one-dimensional, so the ray is well defined. A normalized representative may be used for probabilities, but the state itself is the ray, not a chosen vector.

De Wolf §20.1, PDF p. 185, and Watrous Lesson 14 §14.3, printed pp. 415–416 (PDF pp. 421–422), define a stabilizer state from a full-rank commuting Pauli subgroup and its common $+1$ eigenspace: https://arxiv.org/pdf/1907.09415; https://jhwatrous.github.io/UQIC.pdf.

Let $S$ be a stabilizer subgroup on $n\ge 0$ qubits and let $\lambda (P(k,x,z))=(x,z)$. Then $\lambda {\mathrm{\mid }}_S$ is injective, its image $L$ is an isotropic ${\mathbb{F}}_2$-subspace, the rank ${\dim }_{{\mathbb{F}}_2}L$ depends only on $S$ and not on a generating list, and $\mathrm{\mid }S\mathrm{\mid }=2^{{\dim }_{{\mathbb{F}}_2}L}$.

De Wolf §20.1, PDF pp. 185–186, describes the finite Pauli group, commuting independent stabilizers, and the rank-$n$ state condition. Aaronson–Gottesman §II, PDF pp. 2–4, gives the binary phase-aware Pauli row representation. The current batch-15 label-quotient and commutator supplier bodies are listed in the Facts & Assumptions above; this draft does not claim their independent acceptance.

For a stabilizer subgroup $S$ on $n$ qubits, the finite operator average

${\mathrm{\Pi }}_S:=\frac{1}{\mathrm{\mid }S\mathrm{\mid }}{\sum }_{g\in S}g$

is self-adjoint and idempotent, and its image is exactly the common $+1$ fixed space $\mathcal{C}(S)$. If this image is the span of a unit vector $\psi$, then ${\mathrm{\Pi }}_S=\mathrm{\mid }\psi ⟩⟨\psi \mathrm{\mid }$ under the root-linear-first Dirac convention.

Watrous Lesson 14 §14.3, printed pp. 420–421 (PDF pp. 426–427), derives the stabilizer average as the code-space projector. De Wolf §20.3, PDF pp. 187–188, treats the rank-$n$ stabilizer projector. The group-average proof above supplies the full multiplication count locally.

For $n\ge 0$, $x,z\in {\mathbb{F}}_2^n$, and $k\in \mathbb{Z}\mathrm{/}4$, write $P(k,x,z)=i^k{X}^x{Z}^z$, with the fixed tensor order and $X^x={⨂}_{j<n}{X}^{x_j}$, $Z^z={⨂}_{j<n}{Z}^{z_j}$. A row $(k,x,z)$ is Hermitian when $k\equiv x\cdot z(\mathrm{m}\mathrm{o}\mathrm{d}2)$; it stores the exact Pauli phase as well as its binary label $(x,z)$.

For $n=0$, use the scalar Pauli convention of Pauli group on the empty register; the generator list is empty.

A generator tableau is an ordered list of $n$ Hermitian rows whose Pauli operators commute, have linearly independent labels, and generate a subgroup not containing $-I$. It represents the unique common $+1$ ray when the rows stabilize a pure state. An extended tableau also stores Hermitian destabilizer rows $d_1,\dots ,d_n$ and stabilizer rows $s_1,\dots ,s_n$ with

$\omega (d_i,s_j)={\delta }_{ij},\omega (d_i,d_j)=0,\omega (s_i,s_j)=0.$

The exact phase and symplectic conventions are those of the cited Pauli suppliers. The generator-only simulator uses the $s_j$ rows; the extended pairing is retained as a second representation invariant.

Aaronson–Gottesman §III, PDF pp. 3–5, defines the phase-bit tableau and its destabilizer/stabilizer pairing. De Wolf §20.3, PDF pp. 187–188, gives the generator-only stabilizer representation used by the simulator: https://arxiv.org/pdf/quant-ph/0406196; https://arxiv.org/pdf/1907.09415.

Let $\rho =\mathrm{\mid }\psi ⟩⟨\psi \mathrm{\mid }$ be a pure stabilizer state density operator, and let $M$ be a Hermitian Pauli observable that anticommutes with one of its stabilizer generators. Then $\mathrm{Tr}(P_0\rho )=\mathrm{Tr}(P_1\rho )=1\mathrm{/}2$.

De Wolf §20.3, PDF p. 188, proves equality of the two outcome probabilities by conjugating with an anticommuting stabilizer. Aaronson–Gottesman §III, PDF pp. 4–5, gives the corresponding tableau measurement case.

For $n\ge 0$ and a bit string $x=(x_0,\dots ,x_{n-1})\in {\mathbb{F}}_2^n$, the basis state $\mathrm{\mid }x⟩$ has rows indexed by $a=1,\dots ,n$ given by $s_{j+1}=(-1{)}^{x_j}{Z}_{j+1}$ and $d_{j+1}=X_{j+1}$ for each $0\le j<n$. Their labels satisfy the extended tableau pairing conditions.

Aaronson–Gottesman §III, PDF pp. 3–4, gives the identity tableau for computational-basis input. De Wolf §20.1, PDF p. 185, notes that every basis state is a stabilizer state: https://arxiv.org/pdf/quant-ph/0406196; https://arxiv.org/pdf/1907.09415.

Write a Hermitian row as $P(k,x,z)=i^k{X}^x{Z}^z$, with $k\in \mathbb{Z}\mathrm{/}4$. In this lemma's formulas, label coordinates are numbered by Pauli wires $a=1,\dots ,n$ in tensor order: the coordinate denoted $x_a$ (respectively $z_a$) here is the coordinate denoted $x_{a-1}$ (respectively $z_{a-1}$) in Phase-aware stabilizer tableau. This reindexing changes no operator or phase. For wire $a$ with $1\le a\le n$, conjugation by $H_a$, $S_a$, and $S_a^{†}$ updates the row by, respectively,

$H_a:(k,x_a,z_a)\mapsto (k+2x_a{z}_a,z_a,x_a),$ $S_a:(k,x_a,z_a)\mapsto (k+x_a,x_a,z_a\oplus x_a),$ $S_a^{†}:(k,x_a,z_a)\mapsto (k-x_a,x_a,z_a\oplus x_a)\mathrm{.}$

For distinct wires $c,t$, ${\mathrm{CNOT}}_{c\to t}$ updates $x_t\mapsto x_t\oplus x_c$, $z_c\mapsto z_c\oplus z_t$, with all other label coordinates and $k$ unchanged. Applying these conjugations to every row preserves the generator tableau and, when present, the extended pairing invariant.