An Explicit Proper Code and Universal Fault-Tolerant Gadgets

Take $m=49$, the code $Q=\mathrm{im}W$, effective spread budget $\mathrm{\ell }=1$, and declared capacity $d=2$. Choose the decoded recovery to be the zero-fault circuit $C$ of [F2], followed by the inverse of [F3]'s bare Clifford encoder and discard of its other $48$ coordinates. This is an actual finite circuit: $C$ is code valued, and the inverse encoder extracts its one logical input with all other encoder coordinates reset to zero. By [F1] and [F2] it corrects the entire weight-four error span and hence every located weight-two channel required by the contract. The same recovery tensorized across live blocks corrects the whole joint error span: expand each joint Kraus operator as a sum of tensor products of local error operators and apply the one-block scalar recovery identities to every pair of terms. The resulting coefficients are scalars on every logical factor, although their fault-memory actions may be correlated. Thus the external reference is unchanged. The numerical conditions $49\ge 2d+1$ and $d\ge 2\mathrm{\ell }$ hold, and the integers $q\ge 1$ with $2q\mathrm{\ell }\le d$ consist exactly of $q=1$. This is a nonvacuous sparse-fault contract.

Declare the finite physical alphabet to consist of $H,S,S^{\ast },T,T^{\ast },X,P,P^{\ast }$, CNOT, Toffoli, zero preparation, computational-basis measurement with a classical output register, reset, discard and idle. Classical registers are computational-basis registers; their reversible Boolean gates are the restrictions of $X,$ CNOT and Toffoli. No Boolean computation or control signal is noiseless. Every operation in the supplier circuits is in this alphabet: their controlled $X$ is CNOT, their doubly controlled $X$ is Toffoli, their controlled $Z$ is $H$–Toffoli–$H$ with the indicated two controls, their controlled $S$ has the explicit five-gate Clifford+$T$ decomposition in [F3], and their conditional swaps use two CNOTs and one Toffoli. Source locations include all preparations, measured raw bits, scratch workspaces and idles.

Define protected elementary unitary templates as follows. Begin every template by applying the finite circuit $C$ separately to every input block, before that block interacts with another input. For $H,S,S^{\ast }$ use their $49$-coordinate transversal core. For $X$ use the explicit weight-nine logical Pauli core, with idles on the other coordinates. For $P,P^{\ast }$ use [F5]'s scalar core; for CNOT use the transversal two-block core. Append one copy of $C$ to every output block. For $T$ use [F3]'s injection core between that input refresh and output correction. For $T^{\ast }$ use that same injection, then transversal $S^{\ast }$, then output correction, since $S^{\ast }T=T^{\ast }$. These occurrences of $C$ are its explicitly expanded finite physical circuit, not an in-place recursive call. All templates are exact on fault-free encoded inputs. If the one fault occurs in an input correction, [F2] leaves at most one residual on that block while other input corrections are ideal; the fault-free core propagates this within its supported error budget and the output corrections are ideal. If the fault occurs in a one-block transversal, scalar or Pauli core, the input weight one plus that location gives at most two errors, corrected by the fault-free suffix. If it occurs in the suffix, its input has weight at most one and [F2] leaves at most one residual.

Here is an exact finite Toffoli core over the other gates. For computational bits $x,y,z$ the integer identity $4xyz=x+y+z-(x\oplus y)-(x\oplus z)-(y\oplus z)+(x\oplus y\oplus z)$ follows by expanding $a\oplus b=a+b-2ab$. Apply $T$ to the three original bits; compute their three pair parities into fresh zero registers, apply $T^{\ast }$ to each and uncompute; compute their triple parity into a fourth zero register, apply $T$ and uncompute. The net basis phase is $(-1{)}^{xyz}$ and scratch returns to zero. Conjugate by $H$ on the third original coordinate to obtain exact Toffoli, without a scalar-phase discrepancy. There are $27$ unitary elementary gates, four scratch preparations and four scratch discards.

For CNOT, two input blocks with one error each can give the union of two coordinate labels in either output. A faulty core location adds at most one more label per block, for a total of three. In that case every suffix correction is fault free and [F2] corrects through weight four. If the fault is in a suffix correction, the core is fault free and produces at most two errors per output; the faulty suffix therefore satisfies precisely [F2]'s weight-two input contract. Other suffixes are ideal. Hence the protected CNOT template has at most one residual per block. For $T$ and $T^{\ast }$, [F3] gives at most two errors when the fault is in the core, so ideal suffix correction removes them. If the fault is in suffix correction, the injection is noiseless and propagates an incoming one-coordinate error to one-coordinate error; transversal $S^{\ast }$ preserves that support. Again [F2] applies. Every protected elementary unitary therefore takes joint weight-one inputs and one fault to joint weight-one outputs, stronger than the required weight-two computation bound. These are joint Kraus-sector assertions, so correlated faults and arbitrary finite references are covered by the suppliers' termwise proofs.

Use [F4]'s verified zero and plus preparations, reset and encoded-classical readout, and [F3]'s verified magic preparation. Append $C$ to their live encoded output blocks. A fault in a preparation core leaves weight one, corrected by an ideal suffix; a suffix fault has a clean admitted input and leaves weight one. Prepend $C$ to readout's encoded input as well. A fault there leaves at most one error for the ideal readout core; a fault in the core or suffix has the stated bounds by [F4] and [F2]. Readout thus preserves the logical measurement instrument and emits an encoded classical block with at most one error. In particular the final correction/control bit is protected: recursive replacement of a computational-basis measurement emits $W\mathrm{\mid }m⟩$ in a new block. Subsequent classical NOT, CNOT and Toffoli use the same coherent encoded unitary templates on these basis states. Discard is the ordinary trace channel; a trace-preserving fault confined to discarded registers cannot change the retained external reference. An encoded idle template is input $C$, a layer of $49$ physical idles, and output $C$. Besides its weight-one invariant on admitted inputs, this template attracts arbitrary inputs into the weight-one code sector with an unspecified resulting logical map: use [F2]'s arbitrary-input attraction for the faulty correction, and its ideal arbitrary-input action for the others. This local input refresh is included even for classical registers.

For completeness specify the recursive domains, rather than treating an arbitrary bad child's output as encoded. Put $V_0=I$, $V_r=V_{r-1}^{\otimes 49}W$. Let ${\mathcal{E}}_{1;s}$ be the usual weight-$s$ operator span. For $r\ge 2$, let ${\mathcal{E}}_{r;s}$ be the span of tensor operators on the $49$ child blocks for which at most $s$ child factors are unrestricted and every other factor belongs to ${\mathcal{E}}_{r-1;1}$. This is the hierarchical error sector; all formulas use its joint tensor version across live blocks. For the base scalar identities, list all phase-free weight-at-most-four Pauli errors $P_a$. Each is unitary, so $P_a\mathrm{/}\sqrt{M}$, where $M$ is their number, form a trace-preserving Kraus family. The fixed recovery corrects that actual channel by [F1]. By [F8], each recovery Kraus map satisfies $R_l{P}_{a}W=c_{la}I$, and linearity extends this to the entire error span. A fixed recursive decoded recovery $D_r$ corrects ${\mathcal{E}}_{r;s}$ for $s\le 4$: take the declared $D_1$, apply $D_{r-1}$ in every child while retaining its private recovery-syndrome register, and then apply $D_1$ to the $49$ logical outputs. By induction a good child factor becomes scalar identity on its logical factor, with its syndrome coefficient retained. An unrestricted factor becomes an arbitrary one-qubit map, hence a Pauli linear combination at that outer coordinate. The outer recovery therefore sees at most $s$ erroneous coordinates and corrects them by [F1]. Expanding every pair of Kraus terms proves the same assertion for coherent sums and correlations, not merely tensor product channels.

Implement step 1.4 on encoded blocks using the protected elementary templates and verified zero scratch preparations, first refreshing the three original inputs separately by $C$. After each elementary stage apply $C$ to every live block of this at-most-seven-block construction, including untouched scratch and input blocks. This supplies a fixed finite Toffoli template. To verify its one-fault branch, induct over its finitely many stages. A fault in the active core produces at most three errors per block by step 2.1; all following corrections in that stage are ideal and correct them. A fault in a correction sees at most two errors from the fault-free core and leaves at most one residual. An idle fault on another live block occurs either before its ideal correction, when at most three errors are removed, or after that correction, when its now-clean state receives one error. A fault in scratch preparation has [F4]'s one-coordinate bound. Thus every stage ends in the correct ideal joint logical state with at most one error per block, and later stages obey the same invariant. The Pauli-basis argument in [F2] and [F3] applies jointly, retaining fault memory and the external reference. This proves the Toffoli contract without assuming a fault-tolerant Toffoli supplier in its own proof. Its native physical Toffoli locations occur only inside finite lower-level templates, not as an unproved logical gate.

The arbitrary unknown-input encoder is the exact finite linear encoder of [F3]; its zero-fault action is $W$ with the reference retained. The quantitative noisy-input contract starts on already encoded sectors or protected prescribed preparations, as stipulated in [F6]. This boundary is necessary: a circuit encoding every unknown $\sigma$ as $W\sigma W^{\ast }$ receives exactly the same physical input in a fault-free run on $X\rho X$ as in a run on $\rho$ with an initial $X$ fault. It cannot output both $W\rho W^{\ast }$ and $WX\rho X{W}^{\ast }$; taking $\rho =\mathrm{\mid }0⟩⟨0\mathrm{\mid }$ contradicts orthogonality of the isometry's two encoded basis states. Every use of the bare encoder inside a prescribed-state factory is nevertheless an ordinary counted faulty location, and [F3] and [F4] verify all its arbitrary faulty outputs by the subsequent rank-one checks and fallback construction. The inverse quantum-code conversion in the declared decoded recovery is likewise an ideal decoding boundary; physical readout inside a noisy computation instead uses step 2.2's protected encoded-classical instrument. Error correction itself is the unmodified $C$, whose fault-free action on every arbitrary input is code valued by [F2]. Its finite syndrome-measurement family consists of the $48$ explicit check circuits of [F2]: on weight-one input, one fault adds at most one data coordinate error, so each has the required weight-two computation output sector while revealing only an error syndrome, not the logical state.

All templates just specified are finite lists over the one declared physical alphabet. In particular the Toffoli template is a finite list containing native physical Toffolis inside its verified correction and preparation circuits; it does not recursively expand those native locations at the same level. At replacement level $r+1$, replace each listed elementary location by its already specified template at level $r$, with the same wire order. This is a simultaneous finite induction on $r$, starting at the elementary physical locations at level zero. Each measurement replacement emits its encoded public classical record; each private cat, selector and syndrome register remains private until its declared discard. Thus fault-free encoded-instrument composition preserves the actual controls and every branch probability, not merely the final unconditioned channel. The local one-fault proofs quantify over arbitrary maps on the full registers of a faulty elementary child, including correlated memory, as required by [F6]. Higher-level sparse correctness uses those explicit stage contracts; alphabet closure does not identify a good noisy child with a physical ideal gate. This establishes finite recursive replacement for every noisy classical operation, initialization, measurement, reset and scheduled idle. No additional unlisted ideal decoder is inserted into any faulty circuit.

One conservative numerical bound is $a=2^{300}$ child locations per template, common depth $2^{230}$, and at most $2^{24}$ live physical registers. Each supplier core or correction has an explicitly listed finite body using fewer than $2^{240}$ locations and $2^{210}$ depth, including its internal idles and scratch, and fewer than $2^{20}$ live registers. Protected elementary templates contain at most seven such core/correction bodies. In every compound template, including the Toffoli construction, compose these unpadded bodies and the required interstage idles first; do not insert a constituent's common-depth padding between stages. The Toffoli template has fewer than $64$ stages, each containing a protected core body and at most seven further block-correction bodies; their total is below $2^{250}$ listed locations and $2^{220}$ layers. Its additional idles on its other at-most-seven blocks add fewer than $7\cdot 49\cdot 2^{220}<2^{230}$ locations. The union of simultaneously live supplier workspaces is smaller than $2^{24}$. After each complete template has been composed, append a single physical-identity padding suffix on its retained registers to bring its depth to exactly $2^{230}$. If the sole fault is in this outer padding, the preceding unpadded body is ideal and has already corrected its admitted input, so padding adds at most one error; if the fault is earlier, the padding is ideal. This applies to the Toffoli only after all its stages, not at their intermediate boundaries. Padding adds at most $2^{24}\cdot 2^{230}=2^{254}$ locations, still below the common $a$. At a global layer, other live logical blocks use their own complete padded idle templates; their count belongs to those separate circuit locations and does not inflate one active template's child bound with the total computation width. Bare encoding is an ideal boundary circuit smaller than these templates. These statements specify the common timing and every idle without a width-dependent child constant.

The locality certificate for substitution is as follows. At a fixed physical fault pattern, each elementary location acts on its declared data ports and any fault memory allowed by [F6]. Here is an explicit factorization of a correctable block edge with encoding $V$. For a finite error basis $E_a$, step 2.3 gives scalar Gram equations $V^{\ast }{E}_a^{\ast }{E}_{b}V=c_{ab}I$: applying each recovery Kraus operator to $E_{a}V$ gives a scalar multiple of identity, and summing their pairwise products gives this equation. Diagonalize the finite positive matrix $(c_{ab})$ and discard its zero eigenvalues. The normalized transformed errors $F_{j}V$ then satisfy $(F_{j}V{)}^{\ast }(F_{k}V)={\delta }_{jk}I$, so $J(\mathrm{\mid }\psi ⟩\otimes \mathrm{\mid }j⟩)=F_{j}V\mathrm{\mid }\psi ⟩$ is an isometry identifying the whole correctable range with logical register times a syndrome register. The termwise sector identities make each good-child Kraus map on this range $J_{\mathrm{o}\mathrm{u}\mathrm{t}}(g\otimes B)J_{\mathrm{i}\mathrm{n}}^{\ast }$; for a measurement retain its logical outcome Kraus operator and public outcome port in place of $g$. Trace preservation holds on this entire admitted domain. This is the required CP factorization, not an asserted full-space extension. Private cat, verifier, selector and truth-table registers are freshly prepared and discarded at their listed boundaries. Only listed data ports and public classical-result ports cross a template boundary. Recovery-syndrome registers introduced for comparison in step 2.3 remain attached to their corresponding physical block edge; they are not an additional globally shared register coupling unrelated locations. A good lower child, on its admitted encoded input, consequently factors its ideal logical channel or instrument and its attached syndrome maps by the termwise identities already proved. Public measurement records remain explicit encoded classical ports. The coefficient $B$ may act on shared fault memory; it is not assumed to commute with another location's coefficient.

Keep that memory order by expanding the finite Kraus products before making a substitution. Fix a complete instrument outcome and Kraus index at every location, and choose bases on the attached syndrome and private registers. In the logical/syndrome coordinates of step 5.2, each good map on admitted inputs has its ideal logical Kraus operator as data factor. A good input refresh on an unrestricted port has admitted output by the stipulated attraction property, so its Kraus operator can instead be expanded into arbitrary maps from that physical input to the logical output, with syndrome/memory coefficients. The marked map has the analogous unrestricted local matrix expansion. Thus write each typed factor as $K_t={\sum }_{\alpha }{A}_{t\alpha }\otimes B_{t\alpha }$, where $A_{t\alpha }$ acts only on its declared data ports and $B_{t\alpha }$ on the syndrome/private registers and shared memory. Expanding the chronological product gives $K_N\cdots K_1={\sum }_{{\alpha }_1,\dots ,{\alpha }_N}(A_{N{\alpha }_N}\cdots A_{1{\alpha }_1})\otimes (B_{N{\alpha }_N}\cdots B_{1{\alpha }_1})$, with the edge isometries understood. No $B$ factors are permuted. Equivalently, contract the internal syndrome basis indices while leaving their memory coefficients in this order. This is a finite linear expansion of each actual Kraus operator; its summands are not separate probabilistic branches.

A marked output need not be admitted. Before its next interaction, however, the next good template applies its separate input correction on that port. In each data-factor product of step 6.1, move only this refresh's data factor backward along the unused output wire: intervening data factors have disjoint ports, so their tensor products commute. Absorb it into the marked data factor without changing that factor's input or output port labels. Do this separately for each marked output; a port with no subsequent use remains unrestricted at the output or is discarded. On admitted predecessor inputs a good refresh has logical factor $I$. No syndrome/memory operation has moved, and the chronological coefficient product from step 6.1 is retained. The one-location proofs in [F2]–[F4] are linear Kraus identities for arbitrary local matrices: any such matrix can be scaled to a contraction and completed to a local CPTP Kraus family. They therefore apply to every absorbed data term, with its ordered memory coefficient, and then to their coherent sum. This proves precisely the local Kraus-span absorption required by [F7]. It does not identify the complete circuit with a single relocated CPTP fault. Complete positivity, trace preservation and actual outcome probabilities come from the unchanged original circuit after reassembling each Kraus operator and summing its branches, not from treating expansion terms as channels. The remaining unrestricted output ports must still be counted in the residual support, as checked below.

Here is the finite correction experiment required by [F7], with $b=1,d=2$ and a lower admitted port span $\mathcal{T}$. Its edge types are the logical qubit times its attached syndrome on every admitted data, cat, raw-bit and workspace port; before first use a not-yet-admitted port instead has its unrestricted physical type. The initial $49$ idle replacements in $C$ attract arbitrary input ports into their admitted ranges. With no marked replacement this converts ${\mathcal{H}}_s(\mathcal{T})$ input, $s\le 4$, to at most $s$ arbitrary outer-coordinate errors; every subsequent good replacement acts on the admitted logical/syndrome types of step 5.2. The zero-fault four-round argument of [F2] corrects these and leaves ${\mathcal{H}}_0(\mathcal{T})$. For arbitrary input it likewise projects onto a full outer syndrome and returns ${\mathcal{H}}_0(\mathcal{T})$, without preserving any initial logical interpretation. With one marked prefix idle, its output is refreshed at its first subsequent use and is one arbitrary outer-coordinate error. Input budget two then gives at most three such errors, corrected by the otherwise ideal outer four-error recovery. If that coordinate is never used again, it is itself the one unrestricted output factor.

For a mark later in $C$, use step 7.1 to absorb the first subsequent good refresh data factors on its output ports termwise, retaining every memory coefficient in chronological order. All other data factors have their ideal admitted logical action, so the linear finite case analysis of [F2] applies to each resulting local matrix term. A cat-preparation mark is followed by the parity verifications, whose accepted logical cat factors give $\alpha I+\beta g$; faulty verifier or enabled-interaction ports affect at most their matching data coordinate. A raw-verification copy can corrupt its source bit and one target workspace, but every other acceptance workspace still has a correct majority triple. A final raw-syndrome copy can corrupt one source bit and one target decoder; the other decoders still select a true equal syndrome pair. Internal selector/decoder faults have only their designated data coordinate. These exhaust the raw/shared ports, and all remaining private cat and scratch outputs are discarded. Consequently every still-inadmissible retained data output is on the same coordinate as the one-coordinate residual already counted in [F2]; a mark with no subsequent use is a last data interaction, correction or idle on that coordinate. There is no second unrestricted data factor to add. Thus correction maps ${\mathcal{H}}_2(\mathcal{T})$ to ${\mathcal{H}}_1(\mathcal{T})$ with its original logical state, and arbitrary input into the same residual range with unspecified logical state. Full branch sums remain trace preserving; public logical readout ports are retained.

Next apply this finite correction result to the leading and trailing corrections in the protected templates. Their cores have exactly the transversal, Pauli/scalar, injection and stagewise Toffoli cases in steps 1.3–3.1: a mark in a leading correction leaves one outer error, a mark in a core adds only its listed coordinate supports, and an ideal suffix removes at most four errors; a marked suffix sees its admitted weight-at-most-two input. Step 7.1 absorbs the input-refresh data factors for an inadmissible core port before interaction, retaining the chronological memory coefficients; an invalid retained output is already one of that slot's counted residual coordinates. Each complete protected elementary template therefore maps ${\mathcal{H}}_1(\mathcal{T})$ to ${\mathcal{H}}_1(\mathcal{T})$; the weaker computation bound ${\mathcal{H}}_2(\mathcal{T})$ follows. The Toffoli construction refreshes and corrects all seven live blocks after each listed stage, so it has those same complete-boundary types. Preparations and encoded-classical readout use the outcome-resolved cases of step 2.2; physical classical controls have the same refresh and coordinate restrictions. Finally an idle template attracts arbitrary input: if its mark is in the leading correction use step 9.1, if in its middle layer use the clean outer-code output of the leading correction, and if in its suffix use the admitted-input correction result. An outer padding mark acts on one data coordinate after the ideal body. These give the acyclic order correction, protected computation, idle attraction, retaining the zero-marked weight-four correction clause. Every reduction concerns this one finite template, with arbitrary attached syndrome coefficients; it has no concatenation index.

The finite experiment in steps 8.1–10.1 now proves the actual recursion by simultaneous induction. Retain correction ${\mathcal{E}}_{r;2}\to {\mathcal{E}}_{r;1}$, correction attraction on arbitrary input, complete protected computation ${\mathcal{E}}_{r;1}\to {\mathcal{E}}_{r;1}$, and idle attraction. Also retain correction ${\mathcal{E}}_{r;4}\to {\mathcal{E}}_{r;0}$ and arbitrary-input ${\mathcal{E}}_{r;0}$ attraction when no child is bad. The level-one cases are [F2] and steps 1.3–3.1. At level $r$, step 2.3 makes all lower admitted sectors correctable; step 5.2 gives their logical/syndrome factorization. Apply the finite experiment with $U=V_{r-1}$ and $\mathcal{T}={\mathcal{E}}_{r-1;1}$, in its proved correction/computation/idle order. Good lower replacements have precisely the induction identities it requires, while one bad child is left unrestricted. The resulting ${\mathcal{H}}_s(\mathcal{T})$ sectors are exactly the ${\mathcal{E}}_{r;s}$ of step 2.3. This establishes the simultaneous assertions without assuming a bad child's output encoded.

For a sequence of computation/correction stages, the stronger complete-template bound from step 11.1 implies the required computation ${\mathcal{E}}_{r;1}\to {\mathcal{E}}_{r;2}$ bound, and correction returns ${\mathcal{E}}_{r;1}$. Thus [F7] applies with $q=1,\mathrm{\ell }=1,d=2$ and returns the ideal joint logical instrument after the recursive decoder. These are hierarchical support bounds, not a bound of two on the total elementary error weight at higher levels. The identities retain every public logical outcome and external reference; private syndrome and fault-memory coefficients are traced only at their declared boundaries.

By step 1.3 and step 2.1 and step 1.4 and step 3.1 and step 2.2 every computation template has input budget one and output budget at most two with one bad child, and correction $C$ has input budget $d=2$ and output budget one. The zero-fault correction requirement on arbitrary inputs holds independently. Step 1.1 shows that these are exactly all nonzero sparse budgets demanded by $2q\mathrm{\ell }\le d$; there is no omitted higher-$q$ branch. Steps 5.2–10.1 prove the finite port-substitution hypothesis of [F7], and steps 2.3 and 11.1–12.1 establish its actual recursive domains and decoded action. The suppliers prove the branch maps before normalization and then sum them, with all error supports and memory actions declared. Finally choose the one-block logical alphabet containing $H,T,T^{\ast },P,P^{\ast }$, supplemented by the provided two- and three-block Clifford/Toffoli gates for circuits. By [F5] its one-block subgroup is dense in the full $U(2)$ in operator norm, including scalar phases. Together with the fixed code, all finite schedules, protected boundary preparations and readout, encoder boundary, correction and recursive goodness above, this proves the proper-code existence claim through the nonvacuous $d\ge 2\mathrm{\ell }$ route.