Stabilizer encoder by symplectic elimination

Inputs. An integer $n\ge 1$ and $r\le n$ ordered rows $P(k_i,x_i,z_i)=i^{k_i}{X}^{x_i}{Z}^{z_i}$ representing independent, pairwise-commuting signed Hermitian Pauli generators on the ordered $n$-qubit register.

Wire and factor indices. Tableau coordinates and circuit wire labels are $q=0,\dots ,n-1$. The one-based Pauli factor index corresponding to wire $q$ is $j=q+1$; factor $j$ occupies tensor position $j-1$. Thus a one-wire gate on circuit wire $q$ uses supplier factor index $q+1$, and a CNOT or SWAP on circuit wires $q,s$ uses supplier indices $q+1,s+1$. The stored coordinates $(x_{i,q},z_{i,q})$ use the same zero-based order.

Tableau updates. For a current row $P(k,x,z)$, all phase entries are updated modulo $4$ and binary entries modulo $2$. Conjugation by $H_q$ sends $(k,x_q,z_q)$ to $(k+2x_q{z}_q,z_q,x_q)$; by $S_q$ it sends these entries to $(k+x_q,x_q,z_q+x_q)$; by $S_q^{†}$ it sends them to $(k-x_q,x_q,z_q+x_q)$. Conjugation by $X_q$ adds $2z_q$ to $k$ and leaves the labels unchanged. Conjugation by ${\mathrm{SWAP}}_{q,s}$ interchanges $x_q$ with $x_s$ and $z_q$ with $z_s$ and leaves $k$ unchanged. For ${\mathrm{CNOT}}_{q\to s}$, update $x_s\leftarrow x_s+x_q$ and $z_q\leftarrow z_q+z_s$ and leave $k$ unchanged; all unmentioned binary coordinates are unchanged. Whenever a gate $U$ is appended to chronological $D$, replace every current row $R$ by $UR{U}^{†}$. For a row product $P(k,x,z)P(k^{\mathrm{\prime }},x^{\mathrm{\prime }},z^{\mathrm{\prime }})$, use the exact update $(k+k^{\mathrm{\prime }}+2(z\cdot x^{\mathrm{\prime }}),x+x^{\mathrm{\prime }},z+z^{\mathrm{\prime }})$.

Validity. If any row is not Hermitian, the binary labels are dependent, two rows fail to commute, or the generated subgroup contains $-I$, return INVALID. The independent commuting case with $r=0$ is valid.

Elementary gate alphabet. The output is a finite chronological list over $H,S,S^{†},X,{\mathrm{CNOT}}_{c\to t},{\mathrm{SWAP}}_{c,t}$. Here $H,S,X,\mathrm{CNOT},\mathrm{SWAP}$ have the exact matrices in the cited gate definitions; $S^{†}=\mathrm{diag}(1,-i)$ is explicitly admitted as one primitive gate of this algorithm. No inverse or controlled black-box access is assumed.

Procedure. Keep the current rows phase-aware, an invertible binary row-operation matrix $M\in GL(r,{\mathbb{F}}_2)$, and phase-aware input-combination rows $G_i$. Initially $M=I_r$, $G_i=g_i$ (the $i$th input row), and the chronological gate list $D$ is empty. The invariant is that current row $i$ is $D{G}_i{D}^{†}$ and $G_i={\prod }_{a=0}^{r-1}{g}_a^{M_{ia}}=P({\kappa }_i,{\bar{x}}_i,{\bar{z}}_i),{\bar{x}}_i={\sum }_{a=0}^{r-1}{M}_{ia}{x}_a,{\bar{z}}_i={\sum }_{a=0}^{r-1}{M}_{ia}{z}_a\mathrm{.}$ where sums in the binary labels are in ${\mathbb{F}}_2^n$ and the product is in increasing input-row order. The input generators commute and square to $I$, so this product is independent of order. Its phase exponent ${\kappa }_i\in \mathbb{Z}\mathrm{/}4\mathbb{Z}$ is the signed row-operation phase data. On a gate conjugation update the current tableau row and its phase, leaving $G_i$ and $M$ unchanged. On a row multiplication $i\leftarrow i+p$, update the current row by the exact phase-aware product, set $M_i\leftarrow M_i+M_p$ over ${\mathbb{F}}_2$, and set $G_i\leftarrow G_i{G}_p$ using the exact Pauli product rule (thereby updating ${\kappa }_i$). A row interchange swaps the corresponding rows of the current tableau, $M$, and $G$.

For each pivot position $j=0,\dots ,r-1$:

1. Among rows $j,\dots ,r-1$, take the first row that is not identity on the unused wires, and let its row index be $s$. If $s\mathrm{\ne }j$, interchange the complete current rows $s$ and $j$ and interchange the corresponding rows of $M$ and $G$, including the phase entry of $G$. This row interchange is not a circuit gate. Take the first unused wire $q$ of the pivot row $j$ with nonzero Pauli label. If $q\mathrm{\ne }j$, append the circuit gate ${\mathrm{SWAP}}_{j,q}$ to $D$ and conjugate every current row by it.
2. On pivot wire $j$ and each later unused wire, normalize the pivot row's local factor: apply $H$ to turn $X$ into $Z$; apply $S^{†}$ followed by $H$ to turn $Y$ into $Z$; leave $Z$ and $I$ unchanged. Append each gate and update every row, including its phase.
3. For each later wire $q$ where the pivot row has a $Z$, append ${\mathrm{CNOT}}_{q\to j}$ and update every row. The pivot becomes either $+Z_j$ or $-Z_j$.
4. If the pivot is $-Z_j$, append $X_j$ and update every row, making it $+Z_j$. For each remaining row with a $Z_j$ factor, multiply that row by the pivot row and update the binary row-operation matrix to clear $Z_j$.

For $r=0$, return the empty gate list, empty $M$ and $\kappa$, and the unchanged logical register. On a valid input with $r>0$, return $D$, its reversed adjoint list $D^{†}$ as the encoder, and the signed row-operation data $(M,\kappa )$, with the associated $G_i$ defined by the invariant above. The returned checks satisfy $D{G}_i{D}^{†}=+Z_i$ for $i=0,\dots ,r-1$. The logical label basis is the ordered computational basis on the remaining $n-r$ wires, prefixed by $\mathrm{\mid }{0}^r⟩$.

The procedure uses only finite tableau rows, deterministic first-pivot choices, and the declared gate list. Each appended gate can be read as a one-occurrence layer in Finite circuit syntax and ordered wire labels; the chronological gate list then denotes the product specified in Denotational semantics of a finite layered circuit. The algorithm explicitly lists $S^{†}$ as a primitive gate with its matrix and assumes no inverse-query access.