Introduction
A fault-tolerant quantum computer could factor large integers and simulate quantum systems [24 , 32 ] . However, current quantum computers are all noisy, and long quantum computations, such as Shor’s factoring algorithm, must remain reliable despite noisy operations [12 , 32 ] . Quantum error correction (QEC) codes were invented to protect logical qubits by redundantly encoding them across physical qubits so that errors can in principle be detected and corrected. As a computation grows longer, it requires a lower logical failure probability under the chosen noise model [15 ] .
Despite a lot of good QEC code candidates for large-scale fault-tolerant quantum computers, it is still an open problem, in general, how to optimally compile a quantum circuit that implements a quantum error correction code designed in code theory in a fault-tolerant way [23 , 29 , 34 ] . A syndrome extraction circuit is designed to detect errors without revealing the encoded information. In a syndrome extraction circuit, stabilizers are measured by extra ancilla qubits, also called helper qubits. The resulting bits after measuring these helper qubits form syndrome bits, which a classical decoder uses to choose a correction [10 , 15 ] . An extraction scheme specifies the ancilla qubits, gates and measurements used to measure each stabilizer. A detector tests a parity of measurement outcomes that is fixed in an error-free run and triggers when this parity changes [11 § 5.6] .
A big challenge in quantum error correction compilation is that quantum errors can happen anywhere in the circuit, not just on data qubits that are designed to protect quantum information. The syndrome extraction circuit can itself introduce extra errors that a QEC code designer might not expect. As an example, a measurement flip can cancel evidence of a data error, and a single error on an ancilla qubit can propagate to several data qubits, producing a hook error [10 , 20 , 33 ] . Circuit-level code distance captures the resulting vulnerability: it is the minimum number of injected Pauli errors at the circuit’s injection sites that can produce a logical data error without triggering the detector [29 , 35 ] . It is a well-known fact that although quantum error correction codes, such as the famous Surface code, have code distance d d d by design, a badly compiled circuit with hook errors can reduce the circuit-level code distance by half in the worst case [20 ] .
We are interested in studying a formal proof of circuit-level code distance, because evidence shows that provable circuit-level distance supports more scalable testing of a quantum error correction circuit. ScaLER [36 §§ 3, 6.1] takes circuit-level distance d d d as input and uses it to set a zero-failure cutoff at ⌊ ( d − 1 ) / 2 ⌋ \lfloor(d-1)/2\rfloor ⌊( d − 1 ) /2 ⌋ errors in its extrapolation model. Justifying this cutoff requires a distance guarantee for the implemented circuit together with a suitable decoder-correctness argument. For matching error and readout contracts, a proof of d c i r c ≥ d d^{\mathrm{circ}} \ge d d circ ≥ d supplies the distance premise. But how can we verify this property in the QEC compilation stack, given that quantum errors can be injected anywhere?
Computing circuit-level code distance for a given compiled circuit is NP-hard in general. A circuit with one Pauli injection site per data qubit followed by noiseless extraction recovers the static code-distance problem [19 , 29 ] . Thus, there is a serious scalability barrier to formally verifying code distance at the scale we want to achieve. Code families introduce a further difficulty. Increasing d d d changes the qubits, measurements and emitted gates. A proof for d = 3 d=3 d = 3 , for example, establishes only that instance, while repeating the argument gate by gate produces a proof that grows with d d d . To break this scalability barrier, we therefore seek one finite proof for the whole family that remains valid through compilation, including the error effects introduced by the extraction circuit. A starting point is to try to take advantage of the knowledge about a code family with a clear geometric structure at the code level, such as the code distance for the Surface code. And we ask the following key research question:
How can we turn a code family’s geometric structure into a finite proof that its distance lower bound survives syndrome-extraction compilation? We propose PC-QEC (parametric proof-carrying quantum error correction) to attack this challenge. At a high level, PC-QEC expresses the geometry using algebraic parity probes, called cuts, and translates a supplied cut-invariant certificate alongside the extraction program. For the rotated Surface code, which arranges qubits on a grid [10 ] , code algebra shows that every logical residual crosses d d d cuts in some collection. The program invariant shows that ℓ \ell ℓ errors cross at most ℓ \ell ℓ cuts in each collection:
logical error: d cuts in some collection ⏟ code algebra (Lemma citep‘3.2‘) ∧ ℓ errors: ≤ ℓ cuts per collection ⏟ program invariant (Thms. citep‘A.3, 5.1‘) ⇒ d c i r c ≥ d . (1) \underbrace{\text{logical error: } d\text{ cuts in some collection}}_{\text{code algebra (Lemma {citep}`3.2`)}}
\land
\underbrace{\ell\text{ errors: }\leq\ell\text{ cuts per collection}}_{\text{program invariant (Thms. {citep}`A.3, 5.1`)}}
\Rightarrow d^{\mathrm{circ}}\geq d. \tag*{(1)} code algebra (Lemma citep ‘3.2‘) logical error: d cuts in some collection ∧ program invariant (Thms. citep ‘A.3, 5.1‘) ℓ errors: ≤ ℓ cuts per collection ⇒ d circ ≥ d . (1)
Figure 1 (a,b) illustrates why parity is a good idea: a logical Z row and a hook error both affect three data qubits, but cross three columns and one column, respectively. Row probes supply the corresponding measure for X errors. A bulk stabilizer generator couples an ancilla qubit to four nearby data qubits [5 ] . N-shaped and Z-shaped coupling orders direct hook errors across logical error strings [20 , 33 ] , enabling the one-cut bound. Cuts require no additional measurements. The bound excludes logical data errors for every record, hence also for detector-silent executions under Definition A.4. Equality additionally needs a matching execution (§ 5.3).
Figure 1. Framework of PC-QEC. (a) Logical Z error: χ X ( Z 3 Z 4 Z 5 ) = ( 1 , 1 , 1 ) \chi_X(Z_3Z_4Z_5)=(1,1,1) χ X ( Z 3 Z 4 Z 5 ) = ( 1 , 1 , 1 ) , three cuts. (b) Hook from one error: χ X ( Z 3 Z 1 Z 4 ) = ( 1 , 0 , 0 ) \chi_X(Z_3Z_1Z_4)=(1,0,0) χ X ( Z 3 Z 1 Z 4 ) = ( 1 , 0 , 0 ) , one cut; parities cancel. QStab S 3 S_3 S 3 : three rounds, QS-Hook: ( E , ℓ ) = ( I , 0 ) → ( Z 3 Z 1 Z 4 , 1 ) (E,\ell)=(I,0)\to(Z_3Z_1Z_4,1) ( E , ℓ ) = ( I , 0 ) → ( Z 3 Z 1 Z 4 , 1 ) , G 0 = 0 G_0=0 G 0 = 0 . (c) Circuit compiled with the Standard Scheme; hook error Z 3 Z_3 Z 3 , X a : ( I 9 , 1 ) X_a:(I^9,1) X a : ( I 9 , 1 ) , Y a : ( Z 3 Z 1 Z 4 , 1 ) Y_a:(Z_3Z_1Z_4,1) Y a : ( Z 3 Z 1 Z 4 , 1 ) , Z a : ( Z 3 Z 1 Z 4 , 0 ) Z_a:(Z_3Z_1Z_4,0) Z a : ( Z 3 Z 1 Z 4 , 0 ) . (d) Circuit compiled with the Flag Scheme; hook error Z 3 Z_3 Z 3 , X a : ( I 9 , 1 , 0 ) X_a:(I^9,1,0) X a : ( I 9 , 1 , 0 ) , Y a : ( Z 3 Z 1 Z 4 , 1 , 1 ) Y_a:(Z_3Z_1Z_4,1,1) Y a : ( Z 3 Z 1 Z 4 , 1 , 1 ) , Z a : ( Z 3 Z 1 Z 4 , 0 , 1 ) Z_a:(Z_3Z_1Z_4,0,1) Z a : ( Z 3 Z 1 Z 4 , 0 , 1 ) . X Y Z XYZ X Y Z each site: I , X , Y , Z I,X,Y,Z I , X , Y , Z . Red path: selected Z a Z_a Z a injection. X stabilizer; Z stabilizer; proof cut; Pauli error. (e) PC-QEC pipeline: Program / circuit; Proof / certificate; CodeML § 3; C ( d , k ) C(d,k) C ( d , k ) : stabilizer; t ↦ P [ q ] t\mapsto P[q] t ↦ P [ q ] ; Code algebra; V d V_d V d : Well formed; W d W_d W d : Complete; Evaluate stabilizers at distance d d d ; Supply cut bounds for hook errors; QStab § 4; S d S_d S d : R R R rounds; Ordered error effects; Invariant proof; Cut bounds and distance; Choose scheme ξ \xi ξ § 5; Standard Scheme; Flag Scheme; Shor Scheme; Knill Scheme; Compile circuit; Translate proof; QClifford § 5; c ˉ d , ξ \bar{c}_{d,\xi} c ˉ d , ξ ; Gates and injection sites; Target proof; Hoare proof and distance; Certificate C C C ; Consumer checker § 6; K d , ξ K_{d,\xi} K d , ξ : accept ⇒ d K d , ξ c i r c ≥ d \Rightarrow d^{\mathrm{circ}}_{K_{d,\xi}}\ge d ⇒ d K d , ξ circ ≥ d .
As shown in Figure 1 , the PC-QEC pipeline contains three different layers with different purposes. At the top layer, CodeML is a language that allows users to implement QEC codes parametrically at the code level without worrying about the compilation. It supplies the ordered family and code-algebra premises. In the middle layer, we introduce an intermediate representation language called QStab. QStab expresses the invariant at stabilizer-measurement boundaries, and each backend justifies the circuit error effects needed to compile it. Following Fault Tolerance by Construction [29 ] , this separates the high-level bound from its implementation. Finally, at the bottom layer, the language QClifford works at the standard Clifford circuit level. PC-QEC translates proofs from the QStab layer to the QClifford layer under the declared error and readout contracts for the Standard Scheme (Std), Flag Scheme (Flag), Shor Scheme (Shor) and Knill Scheme (Knill). This specialized translation reuses supplied source proofs and separately proved backend lemmas (§ 5 ). Following proof-carrying code [3 , 26 ] , a recipient (verifier) checks the certificate against the requested circuit.
Putting things all together, the result is a parametric derivation. For the Surface code, PC-QEC produces a finite proof with symbolic d = 2 s + 1 d = 2s + 1 d = 2 s + 1 under Γ s u r f = { s ≥ 1 , d = 2 s + 1 } \Gamma_{\mathrm{surf}} = \{s \ge1, d = 2s + 1\} Γ surf = { s ≥ 1 , d = 2 s + 1 } . Write C s u r f C_{\mathrm{surf}} C surf for the ordered CodeML program and Generate [ C s u r f ] ( d ; d , d − 1 ) \operatorname{Generate}[C_{\mathrm{surf}}](d; d, d - 1) Generate [ C surf ] ( d ; d , d − 1 ) for its generation into QStab at distance d d d , with d d d extraction rounds and an error budget of d − 1 d - 1 d − 1 (§ 3.2 ). Both stages of compilation appear in the program below:
H S t d : Γ s u r f ⊢ F { Σ = Σ c l e a n ( d ) } Compile S t d [ Generate [ C s u r f ] ( d ; d , d − 1 ) ] { Accept d ( Σ ) ∧ LogFail d ( Σ ) ⇒ d ≤ ℓ ( Σ ) } . (2) \mathcal{H}_{\mathrm{Std}} : \Gamma_{\mathrm{surf}} \vdash_F \{\Sigma= \Sigma_{\mathrm{clean}}(d)\}\ \operatorname{Compile}_{\mathrm{Std}}\left[\operatorname{Generate}[C_{\mathrm{surf}}](d;d,d-1)\right]\ \{\operatorname{Accept}_d(\Sigma) \land\operatorname{LogFail}_d(\Sigma) \Rightarrow d \le\ell(\Sigma)\}. \tag*{(2)} H Std : Γ surf ⊢ F { Σ = Σ clean ( d )} Compile Std [ Generate [ C surf ] ( d ; d , d − 1 ) ] { Accept d ( Σ ) ∧ LogFail d ( Σ ) ⇒ d ≤ ℓ ( Σ )} . (2)
Here S d S_d S d is the QStab program generated by the ordered CodeML family, c ˉ d \bar{c}_d c ˉ d is its compiled QClifford circuit, and Σ c l e a n ( d ) \Sigma_{\mathrm{clean}}(d) Σ clean ( d ) is the clean initial error state. The error-aware Hoare judgment ⊢ F \vdash_F ⊢ F quantifies over every error choice. Accept d \operatorname{Accept}_d Accept d specifies the declared record condition, including detector silence, while LogFail d \operatorname{LogFail}_d LogFail d identifies a logical data residual. The counter ℓ \ell ℓ records the number of injected errors. For the Standard Scheme, the proof establishes the stronger postcondition LogFail d ⇒ d ≤ ℓ \operatorname{LogFail}_d \Rightarrow d \le\ell LogFail d ⇒ d ≤ ℓ for every record.
Induction gives H S t d \mathcal{H}_{\mathrm{Std}} H Std a finite representation, including all code-algebra and compilation premises, independent of the value of d d d . Expanded circuits and gate-by-gate derivations still grow with d d d (§ 5.3 ). Figure 1 uses QStab states σ \sigma σ , σ ′ \sigma' σ ′ and QClifford states Σ \Sigma Σ , Σ ′ \Sigma' Σ ′ , defined in Figure 3 .
Figure 3. The Standard Scheme circuit and single-injection outcomes. Each table row starts clean and idles elsewhere. Striped sites allow I I I , X X X , Y Y Y , Z Z Z . The red path selects Z u Z_u Z u at A. Final E E E excludes the helper qubit.
Comparison with prior work. Table 1 compares demonstrated QEC verification capabilities. QuantumSE symbolically executes programs with specified Pauli errors [9 ] ; Veri-QEC verifies specified error conditions with primitive stabilizer measurements and also supports Coq proofs of scalable codes [18 § 6] . Chen et al. [8 ] analyze errors inside small implementing circuits (gadgets) and detect bad extraction orders for a given circuit. AutoQ-Para proves input-output correctness and equivalence for parameterized circuits [1 ] . PC-QEC accounts for hook errors, proves a circuit-level distance bound for every legal family size, and reuses the code-algebra argument and invariant-proof structure across four schemes. Each backend justifies its own error effects through scheme-specific propagation lemmas.
Table 1. Demonstrated QEC verification capabilities.
In the following sections, we use the parametric Surface code family as our running example. Specifically, we prove circuit-level code distance d d d for the odd-distance rotated Surface code compiled with the Standard Scheme (Corollary 5.2 ). Lean 4 mechanizes the metatheory and the exact circuit-level distances of the canonical rotated Surface, unrotated Surface and Toric code programs. Our approach can also be generalized to other infinite code families such as hypergraph-product (HGP) codes and Toric codes, as well as a Cartesian lifted-product (LP) code family (§ 6 ). Figure 10 shows the five code families and the cut collections or reduced-weight measure used in their proofs.
Figure 10. Code geometry — Cut collections and error measure. X X X probe; Z Z Z probe; data qubit. (a) Rotated Surface code [ [ d 2 , 1 , d ] ] [[d^2,1,d]] [[ d 2 , 1 , d ]] . d = 3 d=3 d = 3 : Figure 1(a). d d d X X X columns; d d d Z Z Z rows. Logical: d d d cuts; one injected error: ≤ 1 \le1 ≤ 1 . (b) Unrotated Surface code (HGP) [ [ d 2 + ( d − 1 ) 2 , 1 , d ] ] [[d^2+(d-1)^2,1,d]] [[ d 2 + ( d − 1 ) 2 , 1 , d ]] . X X X star. d = 3 d=3 d = 3 : 13 edge qubits. d d d X X X rows; d d d Z Z Z columns. Cuts use vertical-edge qubits (block A). Horizontal-edge qubits (block B) are excluded. (c) Toric code [ [ 2 d 2 , 2 , d ] ] [[2d^2,2,d]] [[ 2 d 2 , 2 , d ]] . One X X X cut and one Z Z Z cut. Hidden portions are occluded. Edge block A; Edge block B. X X X rows, Z Z Z columns; X X X columns, Z Z Z rows. All four collections (d d d cuts each) shown at d = 3 d=3 d = 3 . (d) Cartesian LP code (HGP) [ [ 98 t 2 , 18 , 4 t ] ] [[98t^2,18,4t]] [[ 98 t 2 , 18 , 4 t ]] . Block 0; Block 1. t = 1 t=1 t = 1 : two 7 × 7 7\times7 7 × 7 qubit arrays. One X X X check: same ( i , j ) = ( 0 , 2 ) (i,j)=(0,2) ( i , j ) = ( 0 , 2 ) . Array lines are coordinate guides. One cut κ 2 \kappa_2 κ 2 . j = 2 j=2 j = 2 . Red dots only; block 0, seed s 0 s^0 s 0 . Z , 0 Z,0 Z , 0 ; Z , 1 Z,1 Z , 1 ; X , 0 X,0 X , 0 ; X , 1 X,1 X , 1 . Rows: seeds 0–2; columns: Pauli, block. κ 2 = Z 0 , 0 , 2 Z 0 , 3 , 2 Z 0 , 5 , 2 Z 0 , 6 , 2 \kappa_2=Z_{0,0,2}Z_{0,3,2}Z_{0,5,2}Z_{0,6,2} κ 2 = Z 0 , 0 , 2 Z 0 , 3 , 2 Z 0 , 5 , 2 Z 0 , 6 , 2 ; varying j j j gives seven cuts. 3 seeds × \times × 2 blocks × \times × 2 Paulis: 12 collections, each with 7 t 7t 7 t cuts. (e) Triangular 6.6.6 color code [ [ ( 3 d 2 + 1 ) / 4 , 1 , d ] ] [[(3d^2+1)/4,1,d]] [[( 3 d 2 + 1 ) /4 , 1 , d ]] . X ˉ , Z ˉ \bar{X},\bar{Z} X ˉ , Z ˉ . d = 5 d=5 d = 5 : overlapping logicals. No cut collection: use reduced weight. × Z f a c e \times Z_{\mathrm{face}} × Z face . H = Z 1 Z 2 Z 3 Z 4 Z 5 H=Z_1Z_2Z_3Z_4Z_5 H = Z 1 Z 2 Z 3 Z 4 Z 5 . H Z f a c e = Z 0 HZ_{\mathrm{face}}=Z_0 H Z face = Z 0 . Weight modulo stabilizers: ∥ E ∥ S ≤ 3 ℓ \lVert E\rVert_S\le3\ell ∥ E ∥ S ≤ 3 ℓ . Logical: ≥ d \ge d ≥ d ; hence d c i r c ≥ ⌈ d / 3 ⌉ d^{\mathrm{circ}}\ge\lceil d/3\rceil d circ ≥ ⌈ d /3 ⌉ . Purple boundary: logical support, not a cut collection. Fig. 10. Code geometries and proof measures. Panel (b) uses the standard edge-qubit Surface code layout; blue marks an X star and red shades a Z plaquette. The colored loops in (c) are one X cut and one Z cut on the torus; the two indexed grids show all four collections. In (d), a cut is the Pauli product on the selected dots, not the connecting guide line. The enlarged cut uses seed s 0 = 1001011 s^0=1001011 s 0 = 1001011 in column 2 of block 0. Larger t t t repeats each seven-site pattern. Panel (e) uses no cut collection: red dots are Z errors, and multiplication by the face stabilizer reduces their weight. All bounds retain the orders and contracts of Table 2 .
Syndrome extraction and circuit-level code distance proofs
Background
Here we briefly go through the concepts and notation we use in the paper, which are all standard and well known in quantum error correction. For interested readers who want to learn more about these concepts, we recommend Nielsen and Chuang’s textbook [27 Chapter 10] . In a quantum circuit with n n n qubits (wires), we represent errors by Pauli strings. Write [ n ] = { 0 , … , n − 1 } [n]=\{0,\ldots,n-1\} [ n ] = { 0 , … , n − 1 } . A Pauli string E : [ n ] → { I , X , Y , Z } E:[n]\to\{I,X,Y,Z\} E : [ n ] → { I , X , Y , Z } assigns an error to each wire. Here I I I is the identity, X X X is a bit flip, Z Z Z is a phase flip, and Y Y Y combines both (while still counting as one error). The weight wt ( E ) \operatorname{wt}(E) wt ( E ) counts nonidentity entries, and P q P_q P q denotes P P P on wire q q q and I I I elsewhere. For example, in Figure 1 (c), one Z Z Z error injected on the helper qubit propagates to the data qubits, causing the hook error I Z Z Z IZZZ I Z Z Z on the four displayed wires, with weight wt ( I Z Z Z ) = 3 \operatorname{wt}(IZZZ)=3 wt ( I Z Z Z ) = 3 . The wire order is 0 , 3 , 1 , 4 0,3,1,4 0 , 3 , 1 , 4 , so this is Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 , with I I I on every other data qubit. We omit global phase while retaining commutation relations.
We say two operators commute if their order does not matter. As an example, the Pauli string operator X Z XZ X Z commutes with Z X ZX Z X . Anticommuting operators differ by a sign when their order is reversed. Distinct nonidentity single-qubit Paulis anticommute. The commutation parity ⟨ E , F ⟩ n \langle E,F\rangle_n ⟨ E , F ⟩ n combines these single-wire bits by exclusive OR (XOR), written ⊕ \oplus ⊕ . For example, the dashed column through qubits 1 , 4 , 7 1,4,7 1 , 4 , 7 in Figure 1 (b) is the Pauli string X 1 X 4 X 7 X_1X_4X_7 X 1 X 4 X 7 . We call this parity probe a cut. Against the hook error E = Z 3 Z 1 Z 4 E=Z_3Z_1Z_4 E = Z 3 Z 1 Z 4 , X X X and Z Z Z anticommute at qubits 1 1 1 and 4 4 4 , giving two contributions that cancel. The column through 0 , 3 , 6 0,3,6 0 , 3 , 6 instead has only one anticommuting position:
⟨ X 1 X 4 X 7 , Z 3 Z 1 Z 4 ⟩ 9 = 1 ⊕ 1 = 0 , ⟨ X 0 X 3 X 6 , Z 3 Z 1 Z 4 ⟩ 9 = 1. (3) \langle X_1X_4X_7,Z_3Z_1Z_4\rangle_9=1\oplus1=0,\qquad\langle X_0X_3X_6,Z_3Z_1Z_4\rangle_9=1. \tag*{(3)} ⟨ X 1 X 4 X 7 , Z 3 Z 1 Z 4 ⟩ 9 = 1 ⊕ 1 = 0 , ⟨ X 0 X 3 X 6 , Z 3 Z 1 Z 4 ⟩ 9 = 1. (3)
Thus the hook error crosses the cut in column zero but not the cut in column one. In particular, ⟨ E F , G ⟩ n = ⟨ E , G ⟩ n ⊕ ⟨ F , G ⟩ n \langle EF,G\rangle_n = \langle E,G\rangle_n \oplus\langle F,G\rangle_n ⟨ E F , G ⟩ n = ⟨ E , G ⟩ n ⊕ ⟨ F , G ⟩ n . An error that anticommutes with a stabilizer flips its syndrome bit.
A stabilizer QEC code is determined by a set of mutually commuting Pauli strings, also known as stabilizer generators. These generators and their products form the stabilizer group S \mathcal{S} S . Its elements act trivially on encoded information. The normalizer N ( S ) \mathcal{N}(\mathcal{S}) N ( S ) contains all strings that commute with every stabilizer. A logical error has zero syndrome but changes encoded information, so it belongs to N ( S ) ∖ S \mathcal{N}(\mathcal{S}) \setminus\mathcal{S} N ( S ) ∖ S . The minimum weight of such an error is the code distance. § 3.3 makes this criterion executable in CodeML.
A Pauli frame records errors relative to an error-free run. We call its restriction to the data qubits the residual. For example, in Figure 1 (c), the residual error caused by the injected Z Z Z error is I Z Z Z IZZZ I Z Z Z on the four displayed data wires. Record bits likewise describe readout deviations: zero denotes an unchanged readout and one denotes a flip relative to the error-free outcome. A detector XORs selected record bits. For example, comparing consecutive measurements of the same stabilizer detects a change, but two flipped outcomes can cancel in this parity.
We follow the standard way to model circuit-level errors, where Pauli errors can be injected anywhere in the circuit [15 ] . Our error model counts one injected error for each pre-operation X X X , Y Y Y or Z Z Z injection on a qubit (wire) at a selected location. A serious problem in circuit-level noise modeling is error propagation [15 , 20 ] : gates propagate errors and can amplify their weight without adding to the injected error count, which can be harmful and decrease the number of errors the actual circuit can protect against.
Now we explain the definition of circuit-level code distance in a compiled QEC circuit, which is what we want to formally verify. Circuit-level code distance measures the minimum number of injected Pauli errors that cause a logical residual error without triggering any detector in the circuit. We call the absence of detector triggers the detector-silence condition. From this definition and the complicated error propagation mechanism, we can see that verifying circuit-level code distance is a nontrivial problem. A direct approach would enumerate all possible error injection patterns in the entire circuit with fewer than d d d injected errors, simulate the error propagation for each of them, and decide whether the residual error is a logical error of the code. Previous work such as QuantumSE [9 ] uses symbolic execution to model and analyze QEC programs more efficiently. However, what we want to achieve is a formal proof without simulating these error injection patterns. In the next section, we will give an overview of the idea and explain how this is possible.
Overview of our approach: Turning parametric code knowledge into a parametric program invariant
The key idea of PC-QEC is that we should fully utilize the parametric code-distance knowledge provided by the design of QEC codes, and carry this knowledge across the entire compilation pipeline. Despite the complexity of modeling circuit-level noise and error propagation, all errors, including hook errors, measurement errors and data qubit errors, either have no effect on the residual data error or cause effects that we can geometrically understand and reason about when we know how the lower-level compilation works. Then, the question we ask first is: What measure separates a one-injection hook error from a logical error when both affect the same number of qubits?
Figure 1 (a) and (b) visualize the difference. In Figure 1 , the logical row Z 3 Z 4 Z 5 Z_3Z_4Z_5 Z 3 Z 4 Z 5 crosses all three columns, whereas the hook error Z 3 Z 4 Z_3Z_4 Z 3 Z 4 crosses only column zero (the two contributions in column one cancel). We extract this geometric information and call it cut parities .
So the answer to the above research question is that we can use cut parities to distinguish the geometric effects a hook error can cause given an error budget from what it takes to form a logical error under that budget. Combining both inspires us to reason about a program invariant at a lower level, which inherits the CodeML layer’s geometric relationship between cause and effect.
Next we focus on using the concrete example in Figure 1 to further elaborate the idea in detail. The X strings ( κ 0 X , κ 1 X , κ 2 X ) = ( X 0 X 3 X 6 , X 1 X 4 X 7 , X 2 X 5 X 8 ) (\kappa^X_0,\kappa^X_1,\kappa^X_2)=(X_0X_3X_6,X_1X_4X_7,X_2X_5X_8) ( κ 0 X , κ 1 X , κ 2 X ) = ( X 0 X 3 X 6 , X 1 X 4 X 7 , X 2 X 5 X 8 ) probe the Z/Y parity in each column by anticommutation. Similarly, the Z strings ( κ 0 Z , κ 1 Z , κ 2 Z ) = ( Z 0 Z 1 Z 2 , Z 3 Z 4 Z 5 , Z 6 Z 7 Z 8 ) (\kappa^Z_0,\kappa^Z_1,\kappa^Z_2)=(Z_0Z_1Z_2,Z_3Z_4Z_5,Z_6Z_7Z_8) ( κ 0 Z , κ 1 Z , κ 2 Z ) = ( Z 0 Z 1 Z 2 , Z 3 Z 4 Z 5 , Z 6 Z 7 Z 8 ) probe the X/Y parity in each row. The cut signatures χ X ( E ) = ( ⟨ κ i X , E ⟩ 9 ) i < 3 \chi_X(E)=(\langle\kappa^X_i,E\rangle_9)_{i<3} χ X ( E ) = (⟨ κ i X , E ⟩ 9 ) i < 3 and χ Z ( E ) \chi_Z(E) χ Z ( E ) collect these column and row bits. For the two errors in Figure 1 , χ X ( Z 3 Z 4 Z 5 ) = ( 1 , 1 , 1 ) \chi_X(Z_3Z_4Z_5)=(1,1,1) χ X ( Z 3 Z 4 Z 5 ) = ( 1 , 1 , 1 ) and χ X ( Z 3 Z 1 Z 4 ) = ( 1 , 0 , 0 ) \chi_X(Z_3Z_1Z_4)=(1,0,0) χ X ( Z 3 Z 1 Z 4 ) = ( 1 , 0 , 0 ) .
We say that an error crosses a cut when the corresponding signature bit is one. The signature’s Hamming weight therefore counts the crossed cuts. These probes are independent of the measured syndrome. A logical error, for example, has zero syndrome even though its cut signature can be ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) .
First, we establish a property of the code: every logical error crosses all three cuts in at least one collection. This can be formalized by the following assertion:
Logical ( E ) ⟹ wt ( χ X ( E ) ) = 3 ∨ wt ( χ Z ( E ) ) = 3. (4) \operatorname{Logical}(E) \Longrightarrow\operatorname{wt}(\chi_X(E))=3 \lor\operatorname{wt}(\chi_Z(E))=3. \tag*{(4)} Logical ( E ) ⟹ wt ( χ X ( E )) = 3 ∨ wt ( χ Z ( E )) = 3. (4)
The column probes differ by stabilizer products. A zero-syndrome error therefore has the same parity against every column probe. The same argument applies to the row probes. If both signatures are zero, code algebra shows that the error is a stabilizer. Lemma 3.2 establishes this property for every odd distance d d d and every logical representative.
Second, we establish a property of the program: each error crosses at most one cut in each collection. Why are we sure that this is correct when errors can be injected anywhere?
If the error is a data qubit error, clearly it affects only one row and one column. If the error is injected on a syndrome qubit, then either it has no effect on the residual data error or it produces a hook error. We have already shown that a hook error also has a limited effect on crossing these cuts. Combining the above, we prove a program invariant that is preserved at stabilizer-measurement boundaries regardless of what kind of error is injected at each step. More explicitly, we can construct the program invariant that relates the data residual E E E to the number ℓ \ell ℓ of injected errors:
wt ( χ X ( E ) ) ≤ ℓ ∧ wt ( χ Z ( E ) ) ≤ ℓ . (5) \operatorname{wt}(\chi_X(E)) \le\ell\quad\land\quad\operatorname{wt}(\chi_Z(E)) \le\ell. \tag*{(5)} wt ( χ X ( E )) ≤ ℓ ∧ wt ( χ Z ( E )) ≤ ℓ . (5)
Combining this with Equation (4) , we now know that the program invariant in Equation (5) , together with ℓ < 3 \ell<3 ℓ < 3 , implies ¬ Logical ( E ) \neg\operatorname{Logical}(E) ¬ Logical ( E ) . This is sufficient to prove that the circuit-level code distance is at least 3. Equality additionally requires a matching silent error pattern (§ 5.3 ). Thus, the lower-bound proof obligation is converted to proving this program invariant across the compilation stack in PC-QEC, as shown in Figure 1 . To obtain one finite proof parametric over all code distances d d d , consider the invariant’s representation. If we explicitly write down the invariant in Equation (5) for the nine data qubits in Figure 1 , it looks like:
wt ( ( ⟨ X 0 X 3 X 6 , E ⟩ 9 , ⟨ X 1 X 4 X 7 , E ⟩ 9 , ⟨ X 2 X 5 X 8 , E ⟩ 9 ) ) ≤ ℓ ∧ wt ( ( ⟨ Z 0 Z 1 Z 2 , E ⟩ 9 , ⟨ Z 3 Z 4 Z 5 , E ⟩ 9 , ⟨ Z 6 Z 7 Z 8 , E ⟩ 9 ) ) ≤ ℓ . (6) \operatorname{wt}((\langle X_0X_3X_6,E\rangle_9,\langle X_1X_4X_7,E\rangle_9,\langle X_2X_5X_8,E\rangle_9))\le\ell\quad\land\quad\operatorname{wt}((\langle Z_0Z_1Z_2,E\rangle_9,\langle Z_3Z_4Z_5,E\rangle_9,\langle Z_6Z_7Z_8,E\rangle_9))\le\ell. \tag*{(6)} wt ((⟨ X 0 X 3 X 6 , E ⟩ 9 , ⟨ X 1 X 4 X 7 , E ⟩ 9 , ⟨ X 2 X 5 X 8 , E ⟩ 9 )) ≤ ℓ ∧ wt ((⟨ Z 0 Z 1 Z 2 , E ⟩ 9 , ⟨ Z 3 Z 4 Z 5 , E ⟩ 9 , ⟨ Z 6 Z 7 Z 8 , E ⟩ 9 )) ≤ ℓ . (6)
Clearly, the size of the above explicitly expanded assertion keeps increasing with code distance d d d . We ask the following question: How can one finite proof cover circuits whose numbers of qubits, stabilizers and rounds grow with d d d ? To map our proof framework parametric over code distance, we need to represent the program invariant parametrically. One way to achieve this is to have a parametric language that can express the Surface code family and its X/Z cuts symbolically with a finite-size program. This is why we define a new parametric language in a functional style. Inspired by OCaml, we call this language CodeML. CodeML supplies the family-level algebraic premises and makes it possible to reason about the invariant in Equation (6) with a proof whose size is independent of d d d for the entire family.
Another key insight we learn from Figure 1 and the above reasoning is that the source invariant depends on each error injection’s cost and effect . The compiler determines both by tracking where the error is injected and how it propagates under a fixed syndrome extraction scheme. This justifies our design of the second abstraction layer, QStab. QStab sets the boundary between expressing the invariant we need to prove circuit-level code distance and the detailed gate implementation. Thus, the design of this IR also helps us reason about circuit-level code distance parametrically over different syndrome extraction schemes.
How does proving this invariant establish the Hoare triple in the Introduction? The program in the triple follows the three layers in Figure 1 . The CodeML program C s u r f C_{\mathrm{surf}} C surf is evaluated at distance d d d by Generate to produce the ordered QStab program S d S_d S d . The outer C o m p i l e S t d \mathrm{Compile}_{\mathrm{Std}} Compile Std then implements those measurements as the QClifford circuit c ˉ d \bar{c}_d c ˉ d . For the Standard Scheme, the intermediate goal puts the cut invariant in the postcondition of this composition:
Γ s u r f ⊢ F { Σ = Σ c l e a n ( d ) } C o m p i l e S t d [ G e n e r a t e [ C s u r f ] ( d ; d , d − 1 ) ] { w t ( χ Z ( E r a w ) ) ≤ ℓ ∧ w t ( χ X ( E r a w ) ) ≤ ℓ } (7) \Gamma_{\mathrm{surf}} \vdash_F \{\Sigma= \Sigma_{\mathrm{clean}}(d)\}\ \mathrm{Compile}_{\mathrm{Std}}\!\left[\mathrm{Generate}[C_{\mathrm{surf}}](d;d,d-1)\right]\ \left\{\begin{aligned} \mathrm{wt}(\chi_Z(E_{\mathrm{raw}})) &\le\ell\ \wedge\\ \mathrm{wt}(\chi_X(E_{\mathrm{raw}})) &\le\ell\end{aligned}\right\} \tag*{(7)} Γ surf ⊢ F { Σ = Σ clean ( d )} Compile Std [ Generate [ C surf ] ( d ; d , d − 1 ) ] { wt ( χ Z ( E raw )) wt ( χ X ( E raw )) ≤ ℓ ∧ ≤ ℓ } (7)
Here E r a w E_{\mathrm{raw}} E raw is the data residual in target state Σ \Sigma Σ , and ℓ = ℓ ( Σ ) \ell= \ell(\Sigma) ℓ = ℓ ( Σ ) is its injection count. At the end of the measurement in Figure 1 (c), these are the same E = Z 3 Z 1 Z 4 E = Z_3Z_1Z_4 E = Z 3 Z 1 Z 4 and ℓ = 1 \ell= 1 ℓ = 1 used above. For arbitrary d d d , the two signatures have d d d entries. The proof starts with zero cut parities, shows that every permitted error effect preserves the bound, and uses induction to cover all measurements and rounds. Compilation must also justify this step through the actual gates, including errors still on helper qubits. Separately proved backend lemmas establish this connection and are reused by certificate translation.
The invariant is one necessary piece of the argument. We also need successful generation of the ordered program, well-formed stabilizers, and the code-algebra fact that every logical error crosses all d d d cuts in some collection. With these premises, a logical residual must satisfy d = w t ( χ X ( E r a w ) ) ≤ ℓ d = \mathrm{wt}(\chi_X(E_{\mathrm{raw}})) \le\ell d = wt ( χ X ( E raw )) ≤ ℓ or d = w t ( χ Z ( E r a w ) ) ≤ ℓ d = \mathrm{wt}(\chi_Z(E_{\mathrm{raw}})) \le\ell d = wt ( χ Z ( E raw )) ≤ ℓ . Thus the invariant triple yields exactly the goal H S t d \mathcal{H}_{\mathrm{Std}} H Std from Equation (2) . The Standard Scheme establishes this implication for every record, so it also holds when A c c e p t d \mathrm{Accept}_d Accept d requires detector silence. By the definition of circuit-level distance, no accepted silent logical failure can then cost fewer than d d d injections. § 4.4 assembles the source premises, and § 5.3 shows the complete derivation through the compiled circuit.
CodeML: A parametric language for families of QEC codes
In CodeML, we turn the static stabilizer formalism of a QEC code family into a function that evaluates the stabilizer operator and its Pauli scheduling order, given a code distance and a stabilizer index. § 2.2 explained why we need such a language: both the stabilizers and the cuts used in our invariant must have finite descriptions as d d d grows. Here we give these objects a syntax, starting with the stabilizer measurement already shown in Figure 1 (c).
Given a code distance d d d and stabilizer index k k k , a CodeML program C ( d , k ) C(d,k) C ( d , k ) returns a bounded function. Its argument t t t is a coupling position. For the first stabilizer in Figure 1 (c), d = 3 d = 3 d = 3 , k = 0 k = 0 k = 0 , and positions t = 0 , 1 , 2 , 3 t = 0,1,2,3 t = 0 , 1 , 2 , 3 return Z [ 0 ] , Z [ 3 ] , Z [ 1 ] , Z [ 4 ] Z[0], Z[3], Z[1], Z[4] Z [ 0 ] , Z [ 3 ] , Z [ 1 ] , Z [ 4 ] , respectively. Here P [ q ] P[q] P [ q ] is the addressed Pauli written P q P_q P q in § 2.1 . Multiplying the four factors gives the stabilizer Z 0 Z 3 Z 1 Z 4 Z_0Z_3Z_1Z_4 Z 0 Z 3 Z 1 Z 4 ; visiting them in order gives the four CNOT couplings in the figure. This order determines which factors remain after an ancilla error and therefore which hook error reaches the data. Increasing k k k orders the stabilizer measurements, while increasing t t t orders the couplings within one measurement.
Syntax for stabilizers and Pauli strings. The types come from the objects introduced in § 2.1 . The type nat represents nonnegative sizes and indices, such as the number of qubits n n n and a qubit index q ∈ [ n ] q \in[n] q ∈ [ n ] . The type pauli contains the four letters I, X, Y, and Z, and bool represents tests used to select a stabilizer or a qubit. A Pauli string, such as the residual error E E E or a cut κ j X \kappa_j^X κ j X , has type str := nat → pauli. Its argument lambda λ . p \lambda.p λ . p specifies the Pauli acting at data qubit u u u . Observing the first n n n entries recovers the strings on [ n ] [n] [ n ] used in § 2.1 ; the same type serves every code size.
To retain the coupling order, an addressed Pauli P[q] is the pair ( P , q ) (P,q) ( P , q ) , of type pauli × \times × nat. A stabilizer has type bounded(pauli × \times × nat): λ t < L . e \lambda t < L.e λ t < L . e gives its L L L ordered factors. Thus the bounded lambda for Figure 1 (c) has four positions, whereas a string lambda for its data error has one Pauli entry per data qubit. The former tells the compiler which qubit to couple next; the latter describes the error on the data qubits, as in § 2.1 . Appendix § 9 .§ 1 gives the complete CodeML syntax, typing and evaluation rules.
Definition 3.1 (Family declaration). A declaration ( C , L e g a l , n , m , f ) (C,\mathrm{Legal},n,m,f) ( C , Legal , n , m , f ) supplies the program, legal code distances, data width, stabilizer count and a bound f f f on nested family calls, called fuel [2 ] . For every legal d d d and k < m ( d ) k < m(d) k < m ( d ) , evaluating C C C must return a stabilizer with a defined bound and a defined addressed Pauli at every position.
Here we use the simplest repetition code as an example. Against bit-flip (Pauli X) errors, it has code distance d d d , with d − 1 d-1 d − 1 adjacent Z stabilizers on d ≥ 2 d \ge2 d ≥ 2 data qubits. We can program this family in CodeML as family C r e p ( d , k ) = λ t < 2. Z [ k + t ] C_{\mathrm{rep}}(d,k)=\lambda t < 2.\ \mathrm{Z}[k+t] C rep ( d , k ) = λ t < 2. Z [ k + t ] . The bounded lambda returns Z on qubit k + t k+t k + t at each coupling position t = 0 , 1 t=0,1 t = 0 , 1 . Stabilizer k k k therefore couples to qubit k k k before qubit k + 1 k+1 k + 1 . At d = 3 d=3 d = 3 , the program returns Z 0 Z 1 Z_0Z_1 Z 0 Z 1 and Z 1 Z 2 Z_1Z_2 Z 1 Z 2 . At d = 5 d=5 d = 5 , the same program returns four ordered stabilizers. The bound two counts the couplings in one measurement, just as the bound four does in Figure 1 (c). The repetition code uses ( n , m , f ) = ( d , d − 1 , 1 ) (n,m,f)=(d,d-1,1) ( n , m , f ) = ( d , d − 1 , 1 ) : its body makes no further family calls. Successful evaluation fixes the coupling order. Address bounds, distinct qubits and commutation are additional proof obligations.
Programming the Surface code in Figure 1. We now program every stabilizer of the running Surface code example. Figure 2 shows the same patch at d = 3 d=3 d = 3 and d = 5 d=5 d = 5 . Write q d ( a , c ) = d a + c q_d(a,c)=da+c q d ( a , c ) = d a + c for the qubit in row a a a and column c c c . This is the numbering already used in Figure 1 : the first Z stabilizer visits coordinates ( 0 , 0 ) (0,0) ( 0 , 0 ) , ( 1 , 0 ) (1,0) ( 1 , 0 ) , ( 0 , 1 ) (0,1) ( 0 , 1 ) , ( 1 , 1 ) (1,1) ( 1 , 1 ) , which give qubits 0 , 3 , 1 , 4 0,3,1,4 0 , 3 , 1 , 4 when d = 3 d=3 d = 3 . At d = 5 d=5 d = 5 , those same coordinates give qubits 0 , 5 , 1 , 6 0,5,1,6 0 , 5 , 1 , 6 . We use s = ( d − 1 ) / 2 s=(d-1)/2 s = ( d − 1 ) /2 to count pairs of rows or columns:
Figure 2. Programming the Surface code and its cut invariant with CodeML. Red and blue faces are Z Z Z and X X X stabilizers. Black outlines select the first bulk stabilizer. Qubit addresses are q = d a + c q = da + c q = d a + c for row a a a and column c c c .
Γ s u r f = { s ≥ 1 , d = 2 s + 1 } , n ( d ) = d 2 , m ( d ) = 4 s 2 + 4 s = d 2 − 1 , f ( d ) = 1. (8) \Gamma_{\mathrm{surf}}=\{s\ge1,d=2s+1\},\qquad n(d)=d^2,\qquad m(d)=4s^2+4s=d^2-1,\qquad f(d)=1. \tag*{(8)} Γ surf = { s ≥ 1 , d = 2 s + 1 } , n ( d ) = d 2 , m ( d ) = 4 s 2 + 4 s = d 2 − 1 , f ( d ) = 1. (8)
Here L e g a l ( d ) : = 3 ≤ d ∧ d m o d 2 = 1 \mathrm{Legal}(d):=3\le d\land d\bmod2=1 Legal ( d ) := 3 ≤ d ∧ d mod 2 = 1 . Each square face, or plaquette, supports a weight-four bulk stabilizer. The curved boundary faces support weight-two stabilizers [5 , 17 ] . There are ( d − 1 ) 2 = 4 s 2 (d-1)^2=4s^2 ( d − 1 ) 2 = 4 s 2 bulk stabilizers and 2 ( d − 1 ) = 4 s 2(d-1)=4s 2 ( d − 1 ) = 4 s boundary stabilizers, giving the count m ( d ) m(d) m ( d ) above. The direct program below makes no nested family calls, so fuel one suffices.
We number bulk stabilizers in 2 × 2 2\times2 2 × 2 blocks; the remaining indices select the top, bottom, right or left boundary. For example, at d = 3 d=3 d = 3 , indices k = 0 , 1 , 2 , 3 k=0,1,2,3 k = 0 , 1 , 2 , 3 visit the four bulk faces of Figure 2 ; k = 4 k=4 k = 4 selects the top boundary X 0 X 1 X_0X_1 X 0 X 1 . Write L ( d , k ) L(d,k) L ( d , k ) for the coupling count and F ( d , k , t ) F(d,k,t) F ( d , k , t ) for the addressed Pauli at position t < L ( d , k ) t<L(d,k) t < L ( d , k ) . Figure 2 illustrates the bulk and boundary cases; the supplement gives the index decoding and their complete definitions. Each case is expressed by an ordinary if expression. Generation evaluates the declaration only for legal d d d and k < m ( d ) k<m(d) k < m ( d ) .
The Z branch visits each plaquette column by column, and the X branch visits it row by row. For d = 3 d=3 d = 3 , k = 0 k=0 k = 0 , the Z branch has a = c = 0 a=c=0 a = c = 0 and returns Z [ 3 ( t m o d 2 ) + ⌊ t / 2 ⌋ ] Z[3(t\bmod2)+\lfloor t/2\rfloor] Z [ 3 ( t mod 2 ) + ⌊ t /2 ⌋] : evaluating t = 0 , 1 , 2 , 3 t=0,1,2,3 t = 0 , 1 , 2 , 3 gives exactly the order 0 , 3 , 1 , 4 0,3,1,4 0 , 3 , 1 , 4 in Figure 1 (c). As § 2.2 explained, this order is what limits the number of column cuts crossed by a hook error.
The expression for t < a yield e computes one result for each position and abbreviates λ t < a . e \lambda t < a.e λ t < a . e . We therefore write the complete direct declaration as
family C s u r f ( d , k ) = for t < L ( d , k ) yield F ( d , k , t ) . (9) \text{family }C_{\mathrm{surf}}(d,k)=\text{for }t<L(d,k)\text{ yield }F(d,k,t). \tag*{(9)} family C surf ( d , k ) = for t < L ( d , k ) yield F ( d , k , t ) . (9)
Generation evaluates this declaration for k < m ( d ) k<m(d) k < m ( d ) before QStab execution. The case distinction selects the stabilizer, and the bounded loop returns its factors in coupling order. The program text has a fixed size for every d d d .
Figure 2 also shows how the same coordinate convention programs the cuts from § 2.2 . The column containing qubit q q q is q m o d d q \bmod d q mod d , and its row is ⌊ q / d ⌋ \lfloor q/d \rfloor ⌊ q / d ⌋ . A string lambda can therefore select a whole column or row, giving finite descriptions of both cut collections. § 3.3 uses these strings to express the invariant from Equation (5) .
First bulk stabilizer C s u r f ( d , 0 ) = λ t < 4. Z [ d ( t m o d 2 ) + ⌊ t / 2 ⌋ ] C_{\mathrm{surf}}(d,0)=\lambda t<4.\,Z[d(t\bmod2)+\lfloor t/2\rfloor] C surf ( d , 0 ) = λ t < 4. Z [ d ( t mod 2 ) + ⌊ t /2 ⌋]
Top boundary C s u r f ( d , ( d − 1 ) 2 ) = λ t < 2. X [ t ] C_{\mathrm{surf}}(d,(d-1)^2)=\lambda t<2.\,X[t] C surf ( d , ( d − 1 ) 2 ) = λ t < 2. X [ t ]
Column cuts κ j X = λ q . if q m o d d = j then X else I \kappa_j^X=\lambda q.\ \text{if }q\bmod d=j\text{ then }X\text{ else }I κ j X = λ q . if q mod d = j then X else I
Row cuts κ i Z = λ q . if ⌊ q / d ⌋ = i then Z else I \kappa_i^Z=\lambda q.\ \text{if }\lfloor q/d\rfloor=i\text{ then }Z\text{ else }I κ i Z = λ q . if ⌊ q / d ⌋ = i then Z else I
Cut signatures χ X ( E ) j = ⟨ κ j X , E ⟩ d 2 , χ Z ( E ) i = ⟨ κ i Z , E ⟩ d 2 ( i , j < d ) \chi_X(E)_j=\langle\kappa_j^X,E\rangle_{d^2},\quad\chi_Z(E)_i=\langle\kappa_i^Z,E\rangle_{d^2}\quad(i,j<d) χ X ( E ) j = ⟨ κ j X , E ⟩ d 2 , χ Z ( E ) i = ⟨ κ i Z , E ⟩ d 2 ( i , j < d )
Invariant wt ( χ X ( E ) ) ≤ ℓ ∧ wt ( χ Z ( E ) ) ≤ ℓ \operatorname{wt}(\chi_X(E))\le\ell\ \wedge\ \operatorname{wt}(\chi_Z(E))\le\ell wt ( χ X ( E )) ≤ ℓ ∧ wt ( χ Z ( E )) ≤ ℓ
The hook errors Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 and Z 5 Z 1 Z 6 Z_5Z_1Z_6 Z 5 Z 1 Z 6 have column signatures ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) and ( 1 , 0 , 0 , 0 , 0 ) (1,0,0,0,0) ( 1 , 0 , 0 , 0 , 0 ) , respectively.
From scheduled factors to a Pauli operator
The bounded value C s u r f ( 3 , 0 ) C_{\mathrm{surf}}(3,0) C surf ( 3 , 0 ) lists four couplings, but the commutation calculation in § 2.1 needs a Pauli string on all nine data qubits. We recover that string by putting each factor on its addressed qubit and multiplying the results. For a stabilizer value S S S , this is
operator ( S ) : = ∏ P [ q ] i n S λ u . if u = q then P else I . (10) \operatorname{operator}(S):=\prod_{P[q]\ \mathrm{in}\ S}\lambda u.\ \text{if }u=q\text{ then }P\text{ else }I. \tag*{(10)} operator ( S ) := P [ q ] in S ∏ λ u . if u = q then P else I . (10)
The product visits each coupling position once and multiplies the factors addressed to u u u . It therefore specifies the Pauli acting at data address u u u , whereas S [ t ] S[t] S [ t ] identifies the qubit coupled at position t t t . We write T k : = operator ( C ( d , k ) ) T_k:=\operatorname{operator}(C(d,k)) T k := operator ( C ( d , k )) and use ⟦ C ⟧ f ( d , k ) \llbracket C\rrbracket_f(d,k) [ [ C ] ] f ( d , k ) for this derived string interpretation. For a concrete operand list r r r , pauli ( r ) \operatorname{pauli}(r) pauli ( r ) denotes the same product. In the running example, T 0 = Z 0 Z 3 Z 1 Z 4 T_0=Z_0Z_3Z_1Z_4 T 0 = Z 0 Z 3 Z 1 Z 4 , with I I I on the other five data qubits. The ordered factors and this string thus describe the same stabilizer at the two levels needed for compilation and the commutation tests from § 2.1 .
From stabilizer families to fixed QStab programs
We write Generate ⟦ C ⟧ ( d ; R , B ) \operatorname{Generate}\llbracket C\rrbracket(d;R,B) Generate [ [ C ] ] ( d ; R , B ) for the CodeML-to-QStab translation used in the Introduction’s triple. For a family declaration ( C , Legal , n , m , f ) (C,\operatorname{Legal},n,m,f) ( C , Legal , n , m , f ) , it evaluates C ( d , k ) C(d,k) C ( d , k ) with fuel f ( d ) f(d) f ( d ) for every k < m ( d ) k<m(d) k < m ( d ) . Let r d , k r_{d,k} r d , k be the resulting list of addressed Pauli factors, in increasing coupling order t t t . When generation succeeds, it returns
Generate ⟦ C ⟧ ( d ; R , B ) = ⟨ n ( d ) , [ r d , k ] k < m ( d ) , R , B ⟩ . (11) \operatorname{Generate}\llbracket C\rrbracket(d;R,B)=\langle n(d),[r_{d,k}]_{k<m(d)},R,B\rangle. \tag*{(11)} Generate [ [ C ] ] ( d ; R , B ) = ⟨ n ( d ) , [ r d , k ] k < m ( d ) , R , B ⟩ . (11)
The declaration supplies n n n , m m m , f f f ; the explicit arguments R R R , B B B supply the number of extraction rounds and the error budget. Each list r d , k r_{d,k} r d , k becomes a MeasStab instruction with numeric operands in that order. Generation is defined only for legal d d d with successful evaluation and the width and operand checks stated below.
For d = 3 d = 3 d = 3 , C s u r f ( 3 , 0 ) C_{\mathrm{surf}}(3, 0) C surf ( 3 , 0 ) gives Z 0 Z 3 Z 1 Z 4 Z_0Z_3Z_1Z_4 Z 0 Z 3 Z 1 Z 4 , the measurement already shown at the QStab level in Figure 1 (c). Figure 3 expands that same example: the four ordered factors determine the CNOTs, and the selected ancilla Z error leaves the residual Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 used in § 2.2 . The generated QStab program contains numeric operands in this order, with no unevaluated CodeML expressions.
The evaluated stabilizers r ⃗ d = [ r d , k ] k < m ( d ) \vec{r}_d = [r_{d,k}]_{k<m(d)} r d = [ r d , k ] k < m ( d ) form the fixed program S d = ⟨ n ( d ) , r ⃗ d , R ( d ) , B ( d ) ⟩ S_d = \langle n(d),\vec{r}_d,R(d),B(d)\rangle S d = ⟨ n ( d ) , r d , R ( d ) , B ( d )⟩ . Thus S d = Generate [ C s u r f ] ( d ; R ( d ) , B ( d ) ) S_d = \operatorname{Generate}[C_{\mathrm{surf}}](d;R(d),B(d)) S d = Generate [ C surf ] ( d ; R ( d ) , B ( d )) . For the Surface code, each round contains d 2 − 1 d^2 - 1 d 2 − 1 stabilizers, the round count is R ( d ) = d R(d) = d R ( d ) = d , and the error budget is B ( d ) = d − 1 B(d) = d - 1 B ( d ) = d − 1 . For the nine-qubit patch in Figure 1 , this gives S 3 = Generate [ C s u r f ] ( 3 ; 3 , 2 ) = ⟨ 9 , r ⃗ 3 , 3 , 2 ⟩ S_3 = \operatorname{Generate}[C_{\mathrm{surf}}](3;3,2) = \langle9,\vec{r}_3,3,2\rangle S 3 = Generate [ C surf ] ( 3 ; 3 , 2 ) = ⟨ 9 , r 3 , 3 , 2 ⟩ : eight stabilizers measured in each of three rounds, with a budget of two injected errors. This is the budget ℓ < 3 \ell< 3 ℓ < 3 used in § 2.2 . The list r ⃗ d \vec{r}_d r d stores one round; QStab repeats it R ( d ) R(d) R ( d ) times.
Generation checks sizes and distinct in-range operands (Appendix § 9 .§ 2 ). The proof additionally establishes stabilizer commutation and the cut bound for hook errors. The latter depends on the coupling order: for example, reordering the first stabilizer as Z 0 Z 1 Z 3 Z 4 Z_0Z_1Z_3Z_4 Z 0 Z 1 Z 3 Z 4 preserves its operator but violates that bound (§ 4.3 ). Figure 3 shows how the coupling order determines which couplings remain after an ancilla-qubit error.
Assertions, cuts, and code-algebra proofs
In this subsection, we introduce an assertion language for stating the proof obligations of a CodeML program and the invariant introduced in § 2.2 . An assertion is a logical condition on the code parameters and error state. For example, Equation (5) asserts that the number of crossed cuts in each collection is at most the number ℓ \ell ℓ of injected errors. We need a finite expression for this condition so that the same invariant can be stated and proved for every legal d d d .
Appendix § 9 .§ 3 gives the complete assertion language and its rules [16 , 22 ] . String equality compares entries up to the stated width; commutation and weight use that same width. For the hook error in Figure 1 (b), the test ⟨ X 1 X 4 X 7 , E ⟩ 9 = 0 \langle X_1X_4X_7,E\rangle_9 = 0 ⟨ X 1 X 4 X 7 , E ⟩ 9 = 0 is precisely the two cancelling contributions calculated in Equation (3) . Conjunction combines the row and column bounds, while bounded quantification ranges over stabilizers or cuts. Their bounds may depend on d d d without changing the assertion’s syntax.
Expressing the logical-error condition. § 2.1 characterized a logical error as a string in N ( S ) ∖ S \mathcal{N}(S)\setminus S N ( S ) ∖ S . We give the two membership tests program names. The predicate Norm ( E ) \operatorname{Norm}(E) Norm ( E ) checks whether E E E commutes with every stabilizer, and Gen ( E ) \operatorname{Gen}(E) Gen ( E ) checks whether E E E is a product of stabilizers. Using the strings T k T_k T k derived in § 3 , an m m m -bit mask a < 2 m a < 2^m a < 2 m selects this subset through a k = ( ⌊ a / 2 k ⌋ m o d 2 ) a_k = (\lfloor a/2^k \rfloor\bmod2) a k = (⌊ a / 2 k ⌋ mod 2 ) . Each stabilizer need be selected at most once because the stabilizers commute and square to the identity. A logical error satisfies Norm and fails Gen:
Norm ( E ) ≔ ∀ k < m . ⟨ T k , E ⟩ n = 0 , Gen ( E ) ≔ ∃ a < 2 m . E ≡ n ∏ k < m ( if a k = 0 then λ q . I else T k ) , (12) \operatorname{Norm}(E) \coloneqq\forall k < m.\ \langle T_k,E\rangle_n = 0,
\qquad
\operatorname{Gen}(E) \coloneqq\exists a < 2^m.\ E \equiv_n \prod_{k<m}(\text{if }a_k=0\text{ then }\lambda q.I\text{ else }T_k), \tag*{(12)} Norm ( E ) : = ∀ k < m . ⟨ T k , E ⟩ n = 0 , Gen ( E ) : = ∃ a < 2 m . E ≡ n k < m ∏ ( if a k = 0 then λ q . I else T k ) , (12)
Logical ( E ) ≔ Norm ( E ) ∧ ¬ Gen ( E ) . \operatorname{Logical}(E) \coloneqq\operatorname{Norm}(E) \land\lnot\operatorname{Gen}(E). Logical ( E ) : = Norm ( E ) ∧ ¬ Gen ( E ) .
Thus Logical(E E E ) implements the criterion E ∈ N ( S ) ∖ S E \in\mathcal{N}(S) \setminus S E ∈ N ( S ) ∖ S [14 ] . For example, the mask a = 1 a = 1 a = 1 selects only T 0 = Z 0 Z 3 Z 1 Z 4 T_0 = Z_0Z_3Z_1Z_4 T 0 = Z 0 Z 3 Z 1 Z 4 , so Gen(T 0 T_0 T 0 ) holds. For the logical row Z 3 Z 4 Z 5 Z_3Z_4Z_5 Z 3 Z 4 Z 5 in Figure 1 (a), Norm holds and Gen fails. For the hook error Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 in Figure 1 (b), Norm fails: it anticommutes with the top-boundary stabilizer X 0 X 1 X_0X_1 X 0 X 1 . These are the same two errors distinguished by the cut parities in § 2.2 .
Expressing the cut invariant. We can now replace the explicit lists of three cuts in Equation (6) by programs that work for every d d d . Recall that q m o d d q \mathbin{\bmod} d q mod d and ⌊ q / d ⌋ \lfloor q/d \rfloor ⌊ q / d ⌋ give the column and row of data qubit q q q . We name these functions L x L_x L x and L z L_z L z ; they select the dashed column and dotted row in Figure 2 . The X and Z string lambdas below are therefore the parametric versions of the probes κ j X \kappa^X_j κ j X and κ i Z \kappa^Z_i κ i Z already used in § 2.2 :
L x ( d , q ) = ( q m o d d ) , L z ( d , q ) = ⌊ q / d ⌋ , L_x(d,q) = (q \mathbin{\bmod} d), \qquad L_z(d,q) = \lfloor q/d \rfloor, L x ( d , q ) = ( q mod d ) , L z ( d , q ) = ⌊ q / d ⌋ ,
κ j X ≔ λ q . if L x ( d , q ) = j then X else I , \kappa^X_j \coloneqq\lambda q.\ \text{if }L_x(d,q)=j\text{ then }X\text{ else }I, κ j X : = λ q . if L x ( d , q ) = j then X else I ,
κ i Z ≔ λ q . if L z ( d , q ) = i then Z else I , \kappa^Z_i \coloneqq\lambda q.\ \text{if }L_z(d,q)=i\text{ then }Z\text{ else }I, κ i Z : = λ q . if L z ( d , q ) = i then Z else I ,
χ x ( E ) j = ⟨ κ j X , E ⟩ n , χ z ( E ) i = ⟨ κ i Z , E ⟩ n , i , j < d . (13) \chi_x(E)_j = \langle\kappa^X_j,E\rangle_n,\qquad\chi_z(E)_i = \langle\kappa^Z_i,E\rangle_n,\qquad i,j<d. \tag*{(13)} χ x ( E ) j = ⟨ κ j X , E ⟩ n , χ z ( E ) i = ⟨ κ i Z , E ⟩ n , i , j < d . (13)
At d = 3 d = 3 d = 3 , j = 1 j = 1 j = 1 , the first string lambda gives X 1 X 4 X 7 X_1X_4X_7 X 1 X 4 X 7 , exactly the column cut in Equation (3) . Its parity against Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 is still zero. Thus these definitions compute the same bits as the overview; only their description is now parametric. The X/Z signature labels name the probe types. Appendix § 9 .§ 3 explains how the core language stores each parity bit as a string entry, so that string weight counts the crossed cuts. We omit the width when it is clear from context. The condition wtd ( χ x ( E ) ) ≤ ℓ ∧ wtd ( χ z ( E ) ) ≤ ℓ \operatorname{wtd}(\chi_x(E)) \le\ell\land\operatorname{wtd}(\chi_z(E)) \le\ell wtd ( χ x ( E )) ≤ ℓ ∧ wtd ( χ z ( E )) ≤ ℓ is therefore the same invariant as Equation (5) , now expressed by one finite assertion for the whole family.
Proving the code properties required by the invariant. The overview used two facts about the code: its generators define a stabilizer code, and every logical error crosses all cuts in at least one collection. The predicate WellFormed requires definedness and pairwise commutation of the generated stabilizer strings. For example, the neighboring stabilizers Z 0 Z 3 Z 1 Z 4 Z_0Z_3Z_1Z_4 Z 0 Z 3 Z 1 Z 4 and X 1 X 2 X 4 X 5 X_1X_2X_4X_5 X 1 X 2 X 4 X 5 in Figure 2 overlap at qubits 1 and 4. Their two anticommuting contributions cancel, just as in the cut calculation in § 2.1 . If a program omitted the factor X 4 X_4 X 4 from the second stabilizer, the strings would no longer commute, even though every factor still had the correct type. Commutation ensures Gen ( E ) ⇒ Norm ( E ) \operatorname{Gen}(E) \Rightarrow\operatorname{Norm}(E) Gen ( E ) ⇒ Norm ( E ) , as required by the stabilizer-group definition in § 2.1 . The distance rules require this WellFormed proof, and compilation preserves it unchanged.
The cut-completeness contract, Complete L x , L z \operatorname{Complete}_{L_x,L_z} Complete L x , L z , ensures that cut signatures do not conceal a logical error. For every fully defined data error, Norm(E E E ) together with an uncrossed row and an uncrossed column implies Gen(E E E ). Consequently, a logical error must cross all cuts in at least one collection. This is exactly the code property in Equation (4) , with three replaced by d d d .
These contracts are proved symbolically. Evaluating an assertion answers a question at a particular size. A judgment Γ ⊢ Γ F \Gamma\vdash_\Gamma F Γ ⊢ Γ F establishes Γ \Gamma Γ for every parameter and residual permitted by Γ \Gamma Γ . For surface code property F ( d ) F(d) F ( d ) , a proof of F ( 3 ) F(3) F ( 3 ) and a proof of F ( d + 2 ) F(d+2) F ( d + 2 ) assuming F ( d ) F(d) F ( d ) for arbitrary odd d ≥ 3 d \ge3 d ≥ 3 establish the family property by induction. This finite proof justifies the use of the same cut summary at every size without enumerating all errors.
Lemma 3.2 (Surface code algebra). Under Equation (8) , C s u r f C_{\mathrm{surf}} C surf satisfies the well-formedness and completeness contracts above for the cuts in Equation (13) .
Proof idea. Induct on odd d d d , starting with eight independent stabilizers at d = 3 d = 3 d = 3 . The step d ↦ d + 2 d \mapsto d + 2 d ↦ d + 2 establishes definedness, commutation and independence for the larger collection and preserves the probe intersections. At code distance d d d , among zero-syndrome errors, the d 2 − 1 d^2 - 1 d 2 − 1 independent stabilizers leave two independent logical directions beyond stabilizer products. row and column probes distinguish these directions, so zero parity for both leaves only a stabilizer product. As in § 2.2 , adjacent column probes differ by a stabilizer product, and likewise for adjacent row probes. A zero-syndrome error therefore has the same parity against every probe in a collection. If it is logical, one collection must have parity one throughout. This gives the cut-completeness property used by the invariant. The supplement supplies the independence proof for the direct construction.
Corollary 3.3. C s u r f C_{\mathrm{surf}} C surf has static code distance d d d for every legal odd d ≥ 3 d \ge3 d ≥ 3 .
An error of weight below d d d leaves an untouched row and column. Completeness therefore excludes a logical error of that weight. A full Z Z Z row attains the bound: it commutes with every stabilizer but anticommutes with an X X X -column probe, so it cannot be a stabilizer product. At d = 3 d = 3 d = 3 , this is the logical row shown in Figure 1 (a).
We have now expressed the stabilizers, cuts and invariant from § 2.2 as finite programs and assertions, and established the code property that separates logical errors from errors crossing too few cuts. The remaining question is the program property from that section: How do we prove that extraction steps preserve the invariant? QStab lets us state and prove that obligation using the error costs and effects illustrated in Figure 1 (c).
QStab: From syndrome extraction to an invariant
§ 3.3 gives us a parametric expression for the cut invariant. To prove it, we need the cost and effect of each error, as explained in § 2.2 . In Figure 1 (c), one helper-qubit error leaves Z 3 Z 1 Z 4 Z_{3}Z_{1}Z_{4} Z 3 Z 1 Z 4 on the data. The Flag Scheme in panel (d) produces the same hook error and also flips a flag readout. The circuits differ, but the data error crosses the same single column cut.
How can an IR retain these circuit-level error effects while remaining parametric over syndrome-extraction schemes? QStab records data errors, readout changes and injection counts at stabilizer-measurement boundaries. This gives the parametric invariant proof a common interface: a step has an error cost and a data and readout effect. The ordered stabilizers come from CodeML; the ancillas and gates depend on the extraction scheme. Each backend must justify the error-effect bounds used by the proof under its declared readout contract. We first prove the invariant through this interface, then show how compilation preserves it.
Ordered syndrome extraction and error effects
Recall the program S = ⟨ n , r ⃗ , R , B ⟩ S = \langle n, \vec{r}, R, B \rangle S = ⟨ n , r , R , B ⟩ generated in § 3.2 : n n n counts data qubits, r ⃗ \vec{r} r lists one round of ordered stabilizers, R R R counts rounds, and B B B is the error budget. For the patch in Figure 1 , these are nine qubits, eight stabilizers, three rounds and two allowed injections. A fixed program has numeric addresses and counts; its CodeML declaration and parametric well-formedness proof remain in the proof context.
Let m = ∣ r ⃗ ∣ m = |\vec{r}| m = ∣ r ∣ . The measurement index h < m R h < mR h < m R identifies both the round and the stabilizer within that round: r h = r ⃗ [ h m o d m ] r_h = \vec{r}[h \mathbin{\bmod} m] r h = r [ h mod m ] , with operator T h = pauli ( r h ) T_h = \operatorname{pauli}(r_h) T h = pauli ( r h ) . For the first measurement, r 0 r_0 r 0 lists Z 0 , Z 3 , Z 1 , Z 4 Z_0, Z_3, Z_1, Z_4 Z 0 , Z 3 , Z 1 , Z 4 in that order. The helper error in Figure 3 occurs after the first coupling, so its data effect is the remaining suffix Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 . In general, we write Hooks ( h ) = { ∏ j ≤ i < ∣ r h ∣ r h [ i ] ∣ 0 ≤ j ≤ ∣ r h ∣ } \operatorname{Hooks}(h) = \left\{\prod_{j \le i < |r_h|} r_h[i] \mid0 \le j \le|r_h|\right\} Hooks ( h ) = { ∏ j ≤ i < ∣ r h ∣ r h [ i ] ∣ 0 ≤ j ≤ ∣ r h ∣ } for these suffixes. The last suffix is I I I : after all couplings, a helper error has no remaining data effect in this block.
The source state σ = ( E , G , h , b , ℓ ) \sigma= (E, G, h, b, \ell) σ = ( E , G , h , b , ℓ ) in Figure 3 keeps the data residual E E E and injection count ℓ \ell ℓ used by the invariant. It also records the remaining budget b b b , the next measurement h h h , and a vector G ∈ { 0 , 1 } m R G \in\{0,1\}^{mR} G ∈ { 0 , 1 } m R of readout flips. Past entries of G G G are committed; G h G_h G h holds an offset for the current measurement, whose data-error contribution is added below. Execution starts at σ 0 = ( I n , 0 , 0 , B , 0 ) \sigma_0 = (I^n, 0, 0, B, 0) σ 0 = ( I n , 0 , 0 , B , 0 ) . A configuration γ \gamma γ adds a running, finished or budget-exhausted status (Appendix § 9 .§ 4 ).
A nondeterministic transition relation. We write γ → k S γ ′ \gamma\xrightarrow{k}_{S} \gamma' γ k S γ ′ for a step costing k ∈ { 0 , 1 } k \in\{0,1\} k ∈ { 0 , 1 } injected errors. We observe that, no matter where errors are injected, their cost and effect can always be categorized into four types. These types describe the effects at a stabilizer-measurement boundary: Type-0 changes one data qubit and leaves the readout offset unchanged; Type-1 changes one data qubit and may also flip the readout; Type-2 adds a hook error and may also flip the readout; and Type-3 flips the readout while leaving the residual data error unchanged. Each type costs one injection. Figure 3 gives concrete examples: Z 0 Z_0 Z 0 , X 0 X_0 X 0 or Y 0 Y_0 Y 0 at D has a Type-0 effect; X 0 X_0 X 0 and Y 0 Y_0 Y 0 flip ω ( 0 ) \omega(0) ω ( 0 ) only through the commutation test at the measurement. A helper Y Y Y before the last CNOT has a Type-1 effect: it adds Z 4 Z_4 Z 4 and an additional readout flip. Both Z u Z_u Z u and Y u Y_u Y u at A have Type-2 effects, producing the same hook Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 ; only Y u Y_u Y u also flips the readout. Finally, X u X_u X u at M has a Type-3 effect. The four rules below express these effects. An error step requires b > 0 b > 0 b > 0 and chooses, as needed, a data qubit q < n q < n q < n , a Pauli P ∈ { X , Y , Z } P \in\{X,Y,Z\} P ∈ { X , Y , Z } , an additional readout offset t ∈ B = { 0 , 1 } t \in\mathbb{B} = \{0,1\} t ∈ B = { 0 , 1 } , or a suffix H ∈ Hooks ( h ) H \in\operatorname{Hooks}(h) H ∈ Hooks ( h ) :
Type-0 QS-Data: E ′ = E P q , G h ′ = G h , Change one data qubit only Type-1 QS-DataReadout: E ′ = E P q , G h ′ = G h ⊕ t , Data error; optional readout flip Type-2 QS-Hook: E ′ = E H , G h ′ = G h ⊕ t , Hook error; optional readout flip Type-3 QS-Readout: E ′ = E , G h ′ = G h ⊕ 1. Flip readout; keep residual \begin{aligned}
\text{Type-0 QS-Data:}\quad&E' = EP_q,\qquad G'_h = G_h, &&\text{Change one data qubit only}\\
\text{Type-1 QS-DataReadout:}\quad&E' = EP_q,\qquad G'_h = G_h \oplus t, &&\text{Data error; optional readout flip}\\
\text{Type-2 QS-Hook:}\quad&E' = EH,\qquad G'_h = G_h \oplus t, &&\text{Hook error; optional readout flip}\\
\text{Type-3 QS-Readout:}\quad&E' = E,\qquad G'_h = G_h \oplus1. &&\text{Flip readout; keep residual}
\end{aligned} Type-0 QS-Data: Type-1 QS-DataReadout: Type-2 QS-Hook: Type-3 QS-Readout: E ′ = E P q , G h ′ = G h , E ′ = E P q , G h ′ = G h ⊕ t , E ′ = E H , G h ′ = G h ⊕ t , E ′ = E , G h ′ = G h ⊕ 1. Change one data qubit only Data error; optional readout flip Hook error; optional readout flip Flip readout; keep residual
The choices are nondeterministic: the proof must cover every permitted effect. In particular, QS-DataReadout and QS-Hook charge once even when both data and readout change.
Each error rule updates ( b , ℓ ) (b,\ell) ( b , ℓ ) to ( b − 1 , ℓ + 1 ) (b-1,\ell+1) ( b − 1 , ℓ + 1 ) and preserves every unlisted field. Thus b + ℓ = B b+\ell=B b + ℓ = B , even if errors later cancel. The classes can overlap: an ancilla Y error before the last CNOT can be viewed as a one-qubit hook error with a readout change. Either classification assigns it cost one.
The zero-cost QS-Meas step commits G h ⊕ ⟨ T h , E ⟩ G_h \oplus\langle T_h,E\rangle G h ⊕ ⟨ T h , E ⟩ and increments h h h , preserving E , b , ℓ E,b,\ell E , b , ℓ [9 § 6.2] . This is the commutation test from § 2.1 : an error anticommutes with the measured stabilizer flips its syndrome bit. Measurements can continue when b = 0 b=0 b = 0 ; only when an additional error exhausts the budget.
Figure 4 follows the first two measurements of S 3 S_3 S 3 . After the hook error, E = Z 3 Z 1 Z 4 E = Z_3Z_1Z_4 E = Z 3 Z 1 Z 4 and ℓ = 1 \ell= 1 ℓ = 1 , just as in Figure 1 (c). The next injection, Y 5 Y_5 Y 5 , adds one crossed column and one crossed row, giving signatures ( 1 , 0 , 1 ) (1,0,1) ( 1 , 0 , 1 ) and ( 0 , 1 , 0 ) (0,1,0) ( 0 , 1 , 0 ) at ℓ = 2 \ell= 2 ℓ = 2 . It also anticommutes with the second stabilizer, X 1 X 2 X 4 X 5 X_1X_2X_4X_5 X 1 X 2 X 4 X 5 , so that measurement commits G 1 = 1 G_1 = 1 G 1 = 1 . The two overlaps of the earlier hook error, at qubits 1 and 4, cancel in this readout. Appendix § 9 .§ 4 shows how a readout error can hide such evidence.
Figure 4. The first two QStab instructions of S 3 S_3 S 3 . A hook error Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 and a data error Y 5 Y_5 Y 5 each cost one injection. Each measurement preserves E E E , ℓ \ell ℓ . Both cut counts remain below three. At σ 2 \sigma_2 σ 2 , G 1 = 1 G_1 = 1 G 1 = 1 and all other entries are zero.
Assertions at every reachable state
Intermediate residuals can have nonzero syndrome: the hook error in Figure 4 is detectable, and later errors may change its syndrome. We prove the cut invariant from Equation (5) for every reachable QStab state. It holds initially, and each step preserves it. Induction then covers every measurement in every round [25 , 28 ] . This is a parametric proof: d d d remains arbitrary throughout the argument.
Appendix § 9 .§ 4 defines the source invariance judgment and the complete transition relation. To prove the two cut bounds together, we use the common property of the row and column selectors in Equation (13) : each data qubit belongs to at most one cut per collection. For example, qubit 5 belongs to column 2 and row 1, which explains the two effects of Y 5 Y_5 Y 5 in Figure 4 . We write ν \nu ν for the number of cuts and L ( ν , q ) L(\nu,q) L ( ν , q ) for a total CodeML term selecting qubit q q q ’s cut. For the Surface code, ν = d \nu=d ν = d , and L L L is the existing L x L_x L x or L z L_z L z . A value outside [ ν ] [\nu] [ ν ] selects no cut. With Pauli kind P P P , the generic cut and signature are
κ i : = λ q . if L ( ν , q ) = i then P else I , χ L , P ( E ) i : = ⟨ κ i , E ⟩ n ( i < ν ) . (14) \kappa_i := \lambda q.\ \text{if }L(\nu,q)=i\text{ then }P\text{ else }I,\qquad\chi_{L,P}(E)_i := \langle\kappa_i,E\rangle_n\quad(i<\nu). \tag*{(14)} κ i := λ q . if L ( ν , q ) = i then P else I , χ L , P ( E ) i := ⟨ κ i , E ⟩ n ( i < ν ) . (14)
Each κ i \kappa_i κ i is a Pauli string on n n n data qubits, while χ L , P ( E ) \chi_{L,P}(E) χ L , P ( E ) has one bit per cut, hence length ν \nu ν . The earlier signatures are exactly χ x = χ L x , X \chi_x=\chi_{L_x,X} χ x = χ L x , X and χ z = χ L z , Z \chi_z=\chi_{L_z,Z} χ z = χ L z , Z , with n = d 2 n=d^2 n = d 2 and ν = d \nu=d ν = d . We use e i e_i e i for a signature with only bit i i i set. At d = 3 d=3 d = 3 , e 0 = ( 1 , 0 , 0 ) e_0=(1,0,0) e 0 = ( 1 , 0 , 0 ) is the hook signature from Figure 1 (b). Thus a data error Z q Z_q Z q contributes e ( q m o d d ) e_{(q\bmod d)} e ( q mod d ) to χ x \chi_x χ x and zero to χ z \chi_z χ z ; X q X_q X q contributes zero to χ x \chi_x χ x and e ⌊ q / d ⌋ e_{\lfloor q/d\rfloor} e ⌊ q / d ⌋ to χ z \chi_z χ z . A Y Y Y error contributes to both and still costs one injection.
From hook error cut bounds to invariants
A data error therefore crosses at most one cut per collection. Why does the same bound hold when one injection reaches several data qubits? Return to the order Z 0 , Z 3 , Z 1 , Z 4 Z_0,Z_3,Z_1,Z_4 Z 0 , Z 3 , Z 1 , Z 4 in Figure 3 . Its column contributions are e 0 , e 0 , e 1 , e 1 e_0,e_0,e_1,e_1 e 0 , e 0 , e 1 , e 1 . Reading backwards, Z 4 Z_4 Z 4 crosses column 1; adding Z 1 Z_1 Z 1 cancels that crossing; adding Z 3 Z_3 Z 3 leaves only column 0; and adding Z 0 Z_0 Z 0 cancels that crossing too. Every suffix therefore crosses at most one column, including the hook error Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 from Figure 1 (b). The whole stabilizer crosses none. We now express this calculation parametrically so the proof covers every stabilizer and legal distance. Appendix § 9 .§ 5 defines the suffix contributions and the hook-bound judgment.
Figure 5. Read a rule as “if the premises above the line hold, the conclusion below follows.” Pair-Nil starts with no couplings left. Pair-Step adds two equal contributions before an already certified tail. Hook-Check instead checks every coupling boundary directly. All CodeML premises include definedness.
Figure 5 turns the cancellation into proof rules. Pair-Nil starts after all couplings. Pair-Step prepends two equal contributions v , v ′ v,v' v , v ′ to a tail whose total contribution is zero. Before the pair, v ⊕ v ′ = 0 v\oplus v'=0 v ⊕ v ′ = 0 ; inside it, only v ′ v' v ′ remains, with weight at most one. Hook-Check allows a direct proof of the same suffix bounds when the pairing rule is not used.
Figure 6 gives the parametric version of the four-coupling calculation, following program-annotation proofs [37 Fig. 1] . Here Γ = { d = 2 s + 1 , s ≥ 1 , 0 ≤ a , b < d − 1 , ( a + b ) m o d 2 = 0 } \Gamma=\{d=2s+1,s\ge1,0\le a,b<d-1,(a+b)\bmod2=0\} Γ = { d = 2 s + 1 , s ≥ 1 , 0 ≤ a , b < d − 1 , ( a + b ) mod 2 = 0 } and ( q 0 , q 1 , q 2 , q 3 ) = ( d a + b , d ( a + 1 ) + b , d a + b + 1 , d ( a + 1 ) + b + 1 ) (q_0,q_1,q_2,q_3)=(da+b,d(a+1)+b,da+b+1,d(a+1)+b+1) ( q 0 , q 1 , q 2 , q 3 ) = ( d a + b , d ( a + 1 ) + b , d a + b + 1 , d ( a + 1 ) + b + 1 ) . These are the addresses from the bulk Z Z Z branch of Figure 2 , with b b b naming the column. At d = 3 , a = b = 0 d=3,a=b=0 d = 3 , a = b = 0 , they are precisely ( 0 , 3 , 1 , 4 ) (0,3,1,4) ( 0 , 3 , 1 , 4 ) . For arbitrary d d d , the contributions still form two equal pairs: v 0 = v 1 = e b v_0=v_1=e_b v 0 = v 1 = e b and v 2 = v 3 = e b + 1 v_2=v_3=e_{b+1} v 2 = v 3 = e b + 1 . The proof tree thus has the same two Pair-Step applications at every distance.
The bulk X branch of Figure 2 pairs contributions along rows instead. Its boundary branches have two operands in the same row or column, contributing [ e i , e i ] [e_i,e_i] [ e i , e i ] to that collection and zeros to the other. These cases establish both hook bounds for every legal d d d .
We can now prove the program property from § 2.2 . Initially, E = I n E=I^n E = I n crosses no cuts and ℓ = 0 \ell=0 ℓ = 0 . Commutation parity gives χ ( E H ) = χ ( E ) ⊕ χ ( H ) \chi(EH)=\chi(E)\oplus\chi(H) χ ( E H ) = χ ( E ) ⊕ χ ( H ) , where χ = χ L , P \chi=\chi_{L,P} χ = χ L , P . The data and hook bounds show that an error step increases each cut count by at most one, while also increasing ℓ \ell ℓ by one. Readout-only errors increase ℓ \ell ℓ without changing either count; measurement steps change neither E E E nor ℓ \ell ℓ . This is exactly the progression shown in Figure 4 , now for an arbitrary step of cost k k k and arbitrary d d d :
wt ( χ L , P ( E ′ ) ) ≤ wt ( χ L , P ( E ) ) + k ≤ ℓ + k = ℓ ′ . (15) \operatorname{wt}(\chi_{L,P}(E')) \le\operatorname{wt}(\chi_{L,P}(E)) + k \le\ell+ k = \ell'. \tag*{(15)} wt ( χ L , P ( E ′ )) ≤ wt ( χ L , P ( E )) + k ≤ ℓ + k = ℓ ′ . (15)
Putting the Surface code proof together
We now assemble the premises needed for the invariant triple in Equation (7) and, eventually, the circuit-level distance guarantee. Each premise comes from a part of the argument already explained.
First, § 3.2 establishes that Generate [ C s u r f ] ( d ; d , d − 1 ) \operatorname{Generate}[\mathcal{C}_{\mathrm{surf}}](d;d,d-1) Generate [ C surf ] ( d ; d , d − 1 ) succeeds and returns S d S_d S d with defined, distinct, in-range operands, positive data width, stabilizer count and round count, and uniform X- or Z-type stabilizers. We call this parametric generation proof G G G . Second, Lemma 3.2 supplies proofs V V V of WellFormed and W W W of Complete L x , L z \operatorname{Complete}_{L_x,L_z} Complete L x , L z . As explained in § 3.3 , these establish that the generated operators define a stabilizer code and that a logical error must cross all d d d cuts in some collection.
Third, the hook proofs P z , P x P_z,P_x P z , P x from § 4.3 establish the row and column bounds. For example, the two equal pairs in Figure 6 prove that every suffix of Z 0 Z 3 Z 1 Z 4 Z_0Z_3Z_1Z_4 Z 0 Z 3 Z 1 Z 4 crosses at most one column. Equation (15) combines this hook bound with the data and readout cases to show that an arbitrary QStab step preserves the invariant. We name the source invariant I d I_d I d and use Φ d \Phi_d Φ d from the overview for the same assertion on target data:
Figure 6. A paired Surface code stabilizer and its hook-error cut certificate. The selected helper error leaves Z q 1 Z q 2 Z q 3 Z_{q_1}Z_{q_2}Z_{q_3} Z q 1 Z q 2 Z q 3 on data at cost one. At d = 3 d=3 d = 3 , a = b = 0 a=b=0 a = b = 0 , this is Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 .
I d ( E , ℓ ) : = wt d ( χ L z , Z ( E ) ) ≤ ℓ ∧ wt d ( χ L x , X ( E ) ) ≤ ℓ , Φ d ( Σ ) : = I d ( E r a w ( Σ ) , ℓ ( Σ ) ) . (16) I_d(E,\ell) := \operatorname{wt}_d(\chi_{L_z,Z}(E)) \le\ell\mathbin{\wedge} \operatorname{wt}_d(\chi_{L_x,X}(E)) \le\ell,\qquad\Phi_d(\Sigma) := I_d(E_{\mathrm{raw}}(\Sigma),\ell(\Sigma)). \tag*{(16)} I d ( E , ℓ ) := wt d ( χ L z , Z ( E )) ≤ ℓ ∧ wt d ( χ L x , X ( E )) ≤ ℓ , Φ d ( Σ ) := I d ( E raw ( Σ ) , ℓ ( Σ )) . (16)
Figure 7 expresses these steps as proof rules. Src-Cut and Src-Conj build D i n v \mathcal{D}_{\mathrm{inv}} D inv ; Src-Dist adds V , W V,W V , W to exclude logical errors when ℓ < d \ell<d ℓ < d :
Figure 7. Source proof rules: establish both cut bounds, conjoin them, and exclude logical errors below ν \nu ν errors. Both selectors have ν \nu ν cuts. All premises retain the same code body, fuel, width and static context.
D i n v = Src-Conj ( Src-Cut ( P z ) , Src-Cut ( P x ) ) , D = Src-Dist ( D i n v , V , W ) . (17) \mathcal{D}_{\mathrm{inv}}=\operatorname{Src\text{-}Conj}(\operatorname{Src\text{-}Cut}(P_z),\operatorname{Src\text{-}Cut}(P_x)),\qquad\mathcal{D}=\operatorname{Src\text{-}Dist}(\mathcal{D}_{\mathrm{inv}},V,W). \tag*{(17)} D inv = Src - Conj ( Src - Cut ( P z ) , Src - Cut ( P x )) , D = Src - Dist ( D inv , V , W ) . (17)
The complete proof uses two inductions for different purposes. Induction on odd d d d proves the code-algebra facts. With d d d arbitrary, induction on execution proves that errors preserve the invariant through all rounds. Together they give one parametric QStab derivation:
D : Γ s u r f ∣ S d ⊢ □ ( ℓ < d ⇒ ¬ Logical ( E ) ) . (18) \mathcal{D}: \quad\Gamma_{\mathrm{surf}} \mid S_d \vdash\Box(\ell< d \Rightarrow\neg\operatorname{Logical}(\mathsf{E})). \tag*{(18)} D : Γ surf ∣ S d ⊢ □ ( ℓ < d ⇒ ¬ Logical ( E )) . (18)
What remains between this source derivation and the circuit-level guarantee from the Introduction? We must establish the target cut premises corresponding to D i n v D_{\mathrm{inv}} D inv for the actual circuit. The two states observe the same data residual at measurement boundaries, but circuit errors may first occur on helpers and propagate through several gates. The generation proof G \mathcal{G} G and the gate argument in § 5.2 justify that connection. Appendix § 10 gives the complete source and target derivations.
QClifford: Translating cut certificates by example
QStab lets us prove the invariant parametrically over code distance and syndrome-extraction scheme. Our implementation translates the supported cut certificates: it preserves their logical structure and code-algebra premises, and replaces source cut leaves by target checks of propagated error effects. Users supply the family proofs; backend developers prove the scheme-specific propagation lemmas. Circuit emission, error-image construction and structural certificate translation are automatic for an instantiated program.
We explain the backend argument using the same two errors in Figure 4 : the hook Z 3 Z 1 Z 4 Z_3Z_1Z_4 Z 3 Z 1 Z 4 and the data error Y 5 Y_5 Y 5 . The key is to account for the part of an error still on a helper before it reaches the data.
Appendix § 9 .§ 6 defines QClifford and Appendix § 9 .§ 7 gives its Hoare rules. QClifford uses standard Clifford-circuit syntax and Pauli-frame notation [15 ] . We refer readers to the standard constructions for single-helper measurements (Standard) [15 ] , flagged measurements (Flag) [7 ] , cat-state extraction (Shor) [31 ] , and teleportation-based extraction (Knill) [21 ] . The supplement fixes our circuit templates and readout contracts. Here we work through the Standard Scheme circuit already shown in Figure 3 .
Following the hook error through the gates
Recall the target state Σ = ( E , ω , j r e c , ℓ ) \Sigma= (\mathcal{E}, \omega, j_{\mathrm{rec}}, \ell) Σ = ( E , ω , j rec , ℓ ) from Figure 3 : E \mathcal{E} E records Pauli errors on data and helpers, ω \omega ω records readout flips, j r e c j_{\mathrm{rec}} j rec counts readouts, and ℓ \ell ℓ counts injections. Its data restriction is E r a w \mathcal{E}_{\mathrm{raw}} E raw , and the clean state is Σ c l e a n = ( I N , 0 , 0 , 0 ) \Sigma_{\mathrm{clean}} = (I^N, 0, 0, 0) Σ clean = ( I N , 0 , 0 , 0 ) for N N N total wires. Each operand has a pre-operation err ( q ) \operatorname{err}(q) err ( q ) site that idles or injects X, Y or Z at cost one, following § 2.1 ’s error model.
The first measurement in Figure 4 has ordered operands ( 0 , 3 , 1 , 4 ) (0, 3, 1, 4) ( 0 , 3 , 1 , 4 ) . Its compiled circuit prepares helper u = 9 u = 9 u = 9 , applies four CNOTs with these data controls and target u u u , and measures u u u in Z. Select Z u Z_u Z u at site A in Figure 3 , after the first CNOT, and idle elsewhere. CNOT propagates Z from target to control, so the next three gates successively add Z 3 Z_3 Z 3 , Z 1 Z_1 Z 1 and Z 4 Z_4 Z 4 to the data. Figure 8 places the selected QStab step above a local QClifford derivation. The source step adds the whole hook at once. The target instead injects Z u Z_u Z u and propagates it through the CNOTs, with a different assertion B i B_i B i at each boundary. The B i B_i B i annotations inside the circuit give the data residual, combined cut vector and injection count. We XOR the current column cuts with the helper’s pending contribution to obtain V j V_j V j ; the assertion A j A_j A j bounds this vector and the row signature by ℓ \ell ℓ . Thus the intermediate assertions can establish the same cut bound even before the complete hook has reached the data. At B 0 B_0 B 0 , the source precondition is extended with a clean helper. At B 4 B_4 B 4 , restricting the target frame to data recovers the source postcondition; the remaining helper Z does not flip the subsequent Z readout.
Figure 8. Relating one abstract effect to concrete propagation. Colored paths are separate single-injection runs, each costing one; other sites idle. Purple assertions describe the Type-2 branch, with E = E r a w E = E_{\mathrm{raw}} E = E raw , e 0 = ( 1 , 0 , 0 ) e_0 = (1,0,0) e 0 = ( 1 , 0 , 0 ) , and V = χ x ( E ) ⊕ z u s j V = \chi_x(E) \oplus z_u s_j V = χ x ( E ) ⊕ z u s j . The source budget is two. The helper is clean at B 0 B_0 B 0 and carries Z at B 1 , … , B 4 B_1,\ldots,B_4 B 1 , … , B 4 ; row cuts and readout flips remain zero.
How do we account for the helper’s pending contribution between gates? After the third coupling, E r a w = Z 3 Z 1 \mathcal{E}_{\mathrm{raw}} = Z_3Z_1 E raw = Z 3 Z 1 crosses two columns, although ℓ = 1 \ell= 1 ℓ = 1 . The helper still carries Z u Z_u Z u , which will add Z 4 Z_4 Z 4 and cancel the crossing in column 1. This is the same 1 ⊕ 1 = 0 1 \oplus1 = 0 1 ⊕ 1 = 0 calculation on qubits 1 and 4 from § 2.1 . An instruction-level derivation must include this pending contribution.
A local derivation of the target cut bound
The source hook proof already computes what remains after each coupling. Evaluate Figure 6 ’s suffixes at d = 3 d = 3 d = 3 , a = b = 0 a = b = 0 a = b = 0 , with e 0 = ( 1 , 0 , 0 ) e_0 = (1,0,0) e 0 = ( 1 , 0 , 0 ) and e 1 = ( 0 , 1 , 0 ) e_1 = (0,1,0) e 1 = ( 0 , 1 , 0 ) :
( s 0 , s 1 , s 2 , s 3 , s 4 ) = ( 0 , e 0 , 0 , e 1 , 0 ) , s j = e q j m o d 3 ⊕ s j + 1 , ( q 0 , q 1 , q 2 , q 3 ) = ( 0 , 3 , 1 , 4 ) . (19) (s_0,s_1,s_2,s_3,s_4) = (0,e_0,0,e_1,0), \qquad s_j = e_{q_j \bmod3} \oplus s_{j+1}, \qquad(q_0,q_1,q_2,q_3) = (0,3,1,4). \tag*{(19)} ( s 0 , s 1 , s 2 , s 3 , s 4 ) = ( 0 , e 0 , 0 , e 1 , 0 ) , s j = e q j mod 3 ⊕ s j + 1 , ( q 0 , q 1 , q 2 , q 3 ) = ( 0 , 3 , 1 , 4 ) . (19)
Let z u z_u z u indicate whether the helper carries Z or Y. Only then does it contribute s j s_j s j . We add that contribution to the data signature and use the same bound as in the source invariant:
V j : = χ x ( E r a w ) ⊕ z u s j , A j : = wt ( V j ) ≤ ℓ ∧ wt ( χ z ( E r a w ) ) ≤ ℓ , A 0 = A 4 = Φ 3 . (20) V_j := \chi_x(E_{\mathrm{raw}}) \oplus z_u s_j, \qquad A_j := \operatorname{wt}(V_j) \le\ell\ \wedge\ \operatorname{wt}(\chi_z(E_{\mathrm{raw}})) \le\ell, \qquad A_0 = A_4 = \Phi_3. \tag*{(20)} V j := χ x ( E raw ) ⊕ z u s j , A j := wt ( V j ) ≤ ℓ ∧ wt ( χ z ( E raw )) ≤ ℓ , A 0 = A 4 = Φ 3 . (20)
The last equality follows from s 0 = s 4 = 0 s_0 = s_4 = 0 s 0 = s 4 = 0 : at measurement boundaries, we recover exactly the target invariant of Equation (16) .
An injected error spends one unit of the bound. A helper Z or Y toggles z u z_u z u and therefore adds s j s_j s j to V j V_j V j . Every displayed s j s_j s j has weight at most one, so wt ( V j ⊕ s j ) ≤ wt ( V j ) + 1 ≤ ℓ + 1 = ℓ ′ \operatorname{wt}(V_j \oplus s_j) \le\operatorname{wt}(V_j) + 1 \le\ell+ 1 = \ell' wt ( V j ⊕ s j ) ≤ wt ( V j ) + 1 ≤ ℓ + 1 = ℓ ′ . A helper X changes no data cut. A data injection changes at most one bit in each cut collection, and satisfies the same inequality. Idle changes nothing. Thus every choice at an injection site preserves A j A_j A j , for any incoming state satisfying it. At site A, in particular, the clean state becomes V 1 = e 0 V_1 = e_0 V 1 = e 0 , ℓ = 1 \ell= 1 ℓ = 1 , in assertion B 1 B_1 B 1 of Figure 8 (b).
A gate transfers the pending contribution to data. CNOT [ q j , u ] [q_j,u] [ q j , u ] adds z u e q j m o d 3 z_u e_{q_j \bmod3} z u e q j mod 3 to the data signature and leaves z u z_u z u and ℓ \ell ℓ unchanged. Using the suffix recurrence gives
V j + 1 ′ = ( χ x ( E r a w ) ⊕ z u e q j m o d 3 ) ⊕ z u s j + 1 = χ x ( E r a w ) ⊕ z u s j = V j . (21) V'_{j+1} = \left(\chi_x(E_{\mathrm{raw}}) \oplus z_u e_{q_j \bmod3}\right) \oplus z_u s_{j+1} = \chi_x(E_{\mathrm{raw}}) \oplus z_u s_j = V_j. \tag*{(21)} V j + 1 ′ = ( χ x ( E raw ) ⊕ z u e q j mod 3 ) ⊕ z u s j + 1 = χ x ( E raw ) ⊕ z u s j = V j . (21)
The row signature χ z \chi_z χ z is unchanged too. For the last gate, the calculation is explicitly ( 1 , 1 , 0 ) ⊕ ( 0 , 1 , 0 ) = ( 1 , 0 , 0 ) (1,1,0) \oplus(0,1,0) = (1,0,0) ( 1 , 1 , 0 ) ⊕ ( 0 , 1 , 0 ) = ( 1 , 0 , 0 ) before the gate and ( 1 , 0 , 0 ) ⊕ ( 0 , 0 , 0 ) = ( 1 , 0 , 0 ) (1,0,0) \oplus(0,0,0) = (1,0,0) ( 1 , 0 , 0 ) ⊕ ( 0 , 0 , 0 ) = ( 1 , 0 , 0 ) after it. Preparation and readout leave data unchanged at boundaries where the pending term is zero.
Consequently the instruction proofs compose into ⊢ F { Φ 3 } c ˉ 3 , 0 { Φ 3 } \vdash_F \{\Phi_3\}\ \bar{c}_{3,0}\ \{\Phi_3\} ⊢ F { Φ 3 } c ˉ 3 , 0 { Φ 3 } for this first measurement block. The Hoare triple covers every incoming state satisfying Φ 3 \Phi_3 Φ 3 and every error choice [16 ] ; the displayed execution illustrates its gate calculation. Replacing the selected helper Z by Y gives the same hook and also a readout flip, precisely as in Figure 3 ’s table. This is how knowing the scheme makes QStab’s abstract hook and readout choices concrete.
We can now continue to the second error in Figure 4 . Injecting Y 5 Y_5 Y 5 adds one column bit and one row bit at cost one:
χ x ( Z 3 Z 1 Z 4 Y 5 ) = ( 1 , 0 , 0 ) ⊕ ( 0 , 0 , 1 ) = ( 1 , 0 , 1 ) , χ z ( Z 3 Z 1 Z 4 Y 5 ) = ( 0 , 1 , 0 ) , ℓ = 2. (22) \chi_x(Z_3Z_1Z_4Y_5) = (1,0,0) \oplus(0,0,1) = (1,0,1), \qquad\chi_z(Z_3Z_1Z_4Y_5) = (0,1,0), \qquad\ell= 2. \tag*{(22)} χ x ( Z 3 Z 1 Z 4 Y 5 ) = ( 1 , 0 , 0 ) ⊕ ( 0 , 0 , 1 ) = ( 1 , 0 , 1 ) , χ z ( Z 3 Z 1 Z 4 Y 5 ) = ( 0 , 1 , 0 ) , ℓ = 2. (22)
Thus the two cut counts are 2 and 1, both at most ℓ \ell ℓ . The second measurement is X-type: its gate argument uses the same pending contribution for row cuts and transports the assertion through its Hadamard basis changes. The supplement gives these local rules. At its boundary we recover Φ 3 \Phi_3 Φ 3 again, with exactly the residual and counts in Figure 4 .
From the example to the parametric circuit guarantee
How does this calculation complete the parametric proof from § 4.4 ? The backend proof generalizes the preceding gate argument over the ordered operands and coupling index. For a bulk Z stabilizer, Figure 6 replaces e 0 e_0 e 0 , e 1 e_1 e 1 by e b e_b e b , e b + 1 e_{b+1} e b + 1 ; the cancellation is unchanged for every legal d d d . The X and boundary cases come from the same CodeML branches in Figure 2 . The generation proof G \mathcal{G} G fixes their operands and order; the hook proofs P x \mathcal{P}_x P x , P z \mathcal{P}_z P z bound their pending contributions.
Propagating one injection through the remaining circuit gives its error image . The backend lemmas establish that each record-corrected image crosses at most one cut per collection; for Standard and Flag the correction is empty. The structural translator replaces each Src-Cut leaf of D \mathcal{D} D by a target cut node and erases that leaf’s source branch and pairing derivations. The target checker checks the bound on the actual circuit’s images. Conjunction, consequence and the code-algebra proofs V V V , W W W are reused. The source derivations justify the backend lemmas’ premises in the preservation proof. This is a structural certificate translation [4 , 30 ] ; the supplement’s “Structural proof translation and checking” section gives its rules.
Why do these local checks cover every error combination? The circuit includes an injection site for every operation operand, and image construction covers X, Y and Z at every site; idle contributes zero. For any clean-start execution with ℓ \ell ℓ injections, linearity of Pauli propagation expresses its final data residual as the product of their data images E 1 , … , E ℓ E_1,\ldots,E_\ell E 1 , … , E ℓ . For either cut collection,
E r a w = ∏ i = 1 ℓ E i , χ ( E r a w ) = ∑ i = 1 ℓ χ ( E i ) , wt ( χ ( E r a w ) ) ≤ ∑ i = 1 ℓ wt ( χ ( E i ) ) ≤ ℓ . (23) E_{\mathrm{raw}} = \prod_{i=1}^{\ell} E_i,\qquad\chi(E_{\mathrm{raw}}) = \sum_{i=1}^{\ell} \chi(E_i),\qquad\operatorname{wt}(\chi(E_{\mathrm{raw}})) \le\sum_{i=1}^{\ell} \operatorname{wt}(\chi(E_i)) \le\ell. \tag*{(23)} E raw = i = 1 ∏ ℓ E i , χ ( E raw ) = i = 1 ∑ ℓ χ ( E i ) , wt ( χ ( E raw )) ≤ i = 1 ∑ ℓ wt ( χ ( E i )) ≤ ℓ . (23)
This execution-composition theorem covers cancellations and multiple injections. The purple path in Figure 8 illustrates the image of the helper Z injection. The supplement proves the corresponding composition for record-corrected observations in the other schemes. The block-composition and final consequence steps appear in Appendix § 10 .
The invariant excludes logical failure for every record when ℓ < d \ell< d ℓ < d ; when ℓ ≥ d \ell\ge d ℓ ≥ d , the postcondition already holds. Thus a certificate with budget d − 1 d-1 d − 1 establishes the final triple for every execution. It uses A d : = ℓ < d ⇒ ¬ L o g i c a l ( E ) A_d := \ell< d \Rightarrow\neg\mathrm{Logical}(E) A d := ℓ < d ⇒ ¬ Logical ( E ) , interpreted on E = E r a w E = E_{\mathrm{raw}} E = E raw and b = d − 1 − ℓ b = d - 1 - \ell b = d − 1 − ℓ .
Theorem 5.1 (Standard Scheme cut-certificate translation). *With the Standard Scheme propagation lemmas above, the supplied symbolic Surface code source derivation D \mathcal{D} D and proof G \mathcal{G} G of S d = Generate [ C s u r r ] ( d ; d − 1 ) S_d = \operatorname{Generate}[\mathcal{C}_{\mathrm{surr}}](d;d-1) S d = Generate [ C surr ] ( d ; d − 1 ) yield one finite derivation schema H s t d \mathcal{H}_{\mathrm{std}} H std of Equation (2) . For every
valuation satisfying Γ s u r f \Gamma_{\mathrm{surf}} Γ surf , it instantiates to an error-aware Hoare derivation for the corresponding emitted circuit. Its target certificate D ′ \mathcal{D}' D ′ proves A d A_d A d at budget d − 1 d-1 d − 1 .
The derivation in Appendix § 10 proves the theorem. Its size is independent of d d d : it stores the finite code-algebra proofs, the symbolic bulk and boundary gate cases, and the induction step, including their proof dependencies. Expanded circuits still grow with d d d . Appendix § 9 .8 defines the record and detector predicates used in the circuit-level distance.
A matching silent failure. The full Z row in Figure 1 (a) suggests the matching upper bound. On each top-row qubit, inject X before its last H, or Z before its last data-controlled CNOT. Each becomes a final Z without reaching a helper. These d d d injections leave the logical row ∏ b < d Z q d ( 0 , b ) \prod_{b<d} Z_{q_d(0,b)} ∏ b < d Z q d ( 0 , b ) and zero readout flips, so every detector is silent. At d = 3 d=3 d = 3 the row is Z 0 Z 1 Z 2 Z_0Z_1Z_2 Z 0 Z 1 Z 2 .
Corollary 5.2 (Surface code circuits compiled with the Standard Scheme). For S d S_d S d compiled by the Standard Scheme translation defined above and any declared record-parity detector family J d \mathcal{J}_d J d ,
∀ d ∈ N . ( d ≥ 3 ∧ d m o d 2 = 1 ) ⇒ d K d , S t d c i r c = d K d , S t d , J d c i r c = d . \forall d \in\mathbb{N}.\ (d \ge3 \land d \bmod2 = 1) \Rightarrow d^{\mathrm{circ}}_{K_{d,\mathrm{Std}}} = d^{\mathrm{circ}}_{K_{d,\mathrm{Std},\mathcal{J}_d}} = d. ∀ d ∈ N . ( d ≥ 3 ∧ d mod 2 = 1 ) ⇒ d K d , Std circ = d K d , Std , J d circ = d .
Changing the extraction scheme. The same method is parametric over schemes through QStab’s error interface: code algebra is reused, while each backend must justify its own propagated errors and readout effects. Standard and Flag bound the raw data residual for every record. Shor and Knill use virtual Pauli corrections determined by ancilla-check and Bell-measurement readout flips, respectively. Each backend’s RecordOK K \operatorname{RecordOK}_{K} RecordOK K ensures the corrected residual agrees with E r a w E_{\mathrm{raw}} E raw when claiming a raw-residual distance. The supplement gives the translations and obligations, and § 6 explains how checking binds the proof to the emitted circuit and its contract.
Evaluation
The evaluation demonstrates family-wide certification across five code families, structural source-certificate translation for a finite Shor code program, and certificate checking for eight finite target circuits (Table 2 ). It measures checking time and shows how extraction choices affect the certified distance.
Table 2. Certified distance guarantees and Standard Scheme checking times.
Certificate checking. The certificate binds the proof to the ordered program, error model and record contract: changing the coupling order in Figure 1 (c) can change its hook errors. For a parametric family, the checker verifies the generation equation, source derivation D \mathcal{D} D , proof translation and every cited CodeML premise, including each induction’s base case and arbitrary step, with d d d symbolic. At a fixed distance, the certificate C = ( c ˉ , I , D ′ ) \mathcal{C}=(\bar{c},\mathcal{I},\mathcal{D}') C = ( c ˉ , I , D ′ ) contains the circuit, its single-injection images and the translated proof. The checker regenerates the instructions, recomputes the images by a shared backward pass, and checks the cut bounds and remaining proof premises (Appendix § 12 ).
Experimental setup
We develop the verifier in OCaml. It is the trusted executable checker for symbolic family certificates and finite target certificates. Lean mechanizes the metatheory and exactness for canonical rotated Surface, unrotated Surface and Toric code programs. Table 2 reports d K c i r c d^{\mathrm{circ}}_{K} d K circ from Definition A.4 . Its lower bounds transfer to detector silence because d K , J c i r c ≥ d K c i r c d^{\mathrm{circ}}_{K,\mathcal{J}} \ge d^{\mathrm{circ}}_{K} d K , J circ ≥ d K circ . We sum verifier wall times from process launch to completion, including loading, on an Intel i5-12400 Windows host with 64 GiB RAM. Appendix § 12 gives the timed stages and measurement counts.
Family-wide distance guarantees
Can one certificate establish a useful distance guarantee for every size of a code family? For rotated Surface code, the verifier checks one supplied Standard Scheme certificate proving a circuit-level code distance lower bound d d d for every odd d ≥ 3 d \ge3 d ≥ 3 in 214 s on average . The matching silent execution in § 5.3 establishes equality for the same ordered schedule.
The other family checks take 23.9 s for unrotated Surface code, 3692 s for Cartesian LP code, 9.48 s for Toric code, and 5511 s for triangular color code. The interleaved Shor source certificate takes 105 s; the eight finite target certificates take 0.209–0.536 s each. Appendix § 12 gives the full distance and timing table.
Comparison with numerical distance search
We compare the cost of checking one supplied lower-bound proof for a family with the cost of finding the exact distance of one instance (Figure 9 ). Each search instance comes from our own pipeline: we instantiate the family’s source program at distance d d d and compile it with our Standard Scheme compiler, so the search receives the QClifford circuit that the family proof covers. We translate this circuit gate by gate into Stim [11 ] , which propagates every single-wire X, Y and Z injection to its final data error under the same error model and unrestricted readouts. The encoder of codeDistance [35 ] turns the resulting syndrome and logical-parity matrices into a MaxSAT problem, which we solve with two PySAT algorithms, its default linear search (LSU) and core-guided RC2, both on the Glucose 4 SAT solver. Every optimum agrees with our proofs: it equals the proved distance for the Surface and LP families, and for the color code it is ( d + 1 ) / 2 (d + 1)/2 ( d + 1 ) /2 , above the certified bound ⌈ d / 3 ⌉ \lceil d/3\rceil ⌈ d /3 ⌉ . Search time grows steeply with d d d : within the limit, the better configuration reaches d = 11 d = 11 d = 11 , 15, 4 and 17 in the four panels, whereas each family proof is checked once for every d d d . Appendix § 12 gives the timing boundaries and run counts.
Figure 9. Finding the exact circuit-level distance of one instance by MaxSAT search (one run, 7,200 s limit; a series ends at its first unsolved instance), compared with compiling and checking one Standard Scheme proof for the entire family. †One check of the color-code lower bound ⌈ d / 3 ⌉ \lceil d/3\rceil ⌈ d /3 ⌉ .
Conclusion
PC-QEC connects supplied code-algebra facts and QStab invariants to circuit-error obligations, then checks the resulting certificate against the requested artifact. For the Surface code, it establishes circuit-level code distance d d d for every odd d ≥ 3 d \ge3 d ≥ 3 , together with a matching silent logical failure.
AI disclosure. OpenAI Codex assisted with proof development, implementation, experiment scripts, and manuscript editing.
DATA-AVAILABILITY STATEMENT
The artifact provides sources, measurements, reproduction scripts and a claim-to-evidence map at https://anonymous.4open.science/r/PLDI2027-artifact-6F50/ ; its family certificates are distributed with it as a separate proof-input archive.
References
Formal definitions
We first fix the notation for qubit indices, Pauli errors, commutation and weight.
[ n ] = { 0 , … , n − 1 } , B = { 0 , 1 } , P = { I , X , Y , Z } ≅ B 2 . [n] = \{0,\ldots,n-1\}, \qquad\mathbb{B} = \{0,1\}, \qquad\mathbb{P} = \{I,X,Y,Z\} \cong\mathbb{B}^{2}. [ n ] = { 0 , … , n − 1 } , B = { 0 , 1 } , P = { I , X , Y , Z } ≅ B 2 .
I = ( 0 , 0 ) , X = ( 1 , 0 ) , Z = ( 0 , 1 ) , Y = ( 1 , 1 ) , ( x , z ) ( x ′ , z ′ ) = ( x ⊕ x ′ , z ⊕ z ′ ) , anti ( ( x , z ) , ( x ′ , z ′ ) ) = x z ′ ⊕ z x ′ . I=(0,0),\quad X=(1,0),\quad Z=(0,1),\quad Y=(1,1),\quad(x,z)(x',z')=(x\oplus x',z\oplus z'),\quad\operatorname{anti}((x,z),(x',z'))=xz'\oplus zx'. I = ( 0 , 0 ) , X = ( 1 , 0 ) , Z = ( 0 , 1 ) , Y = ( 1 , 1 ) , ( x , z ) ( x ′ , z ′ ) = ( x ⊕ x ′ , z ⊕ z ′ ) , anti (( x , z ) , ( x ′ , z ′ )) = x z ′ ⊕ z x ′ .
P q ( u ) = { P u = q , I u ≠ q , ⟨ E , F ⟩ n = ⨁ q < n anti ( E ( q ) , F ( q ) ) , wt n ( E ) = ∣ { q < n : E ( q ) ≠ I } ∣ . P_q(u)=
\begin{cases}
P & u=q,\\
I & u\ne q,
\end{cases}
\qquad
\langle E,F\rangle_n=\bigoplus_{q<n}\operatorname{anti}(E(q),F(q)),
\qquad
\operatorname{wt}_n(E)=|\{q<n:E(q)\ne I\}|. P q ( u ) = { P I u = q , u = q , ⟨ E , F ⟩ n = q < n ⨁ anti ( E ( q ) , F ( q )) , wt n ( E ) = ∣ { q < n : E ( q ) = I } ∣.
CodeML syntax and typing
The following definitions give the complete CodeML syntax and its types.
x ∈ Var , v ∈ N ⊎ B ⊎ P , a , a ′ : n a t , p : p a u l i , T , U : s t r , x\in\operatorname{Var},\quad v\in\mathbb{N}\uplus\mathbb{B}\uplus\mathbb{P},\quad a,a':\mathsf{nat},\quad p:\mathsf{pauli},\quad T,U:\mathsf{str}, x ∈ Var , v ∈ N ⊎ B ⊎ P , a , a ′ : nat , p : pauli , T , U : str ,
s t r : = n a t → p a u l i , f a c t o r : = p a u l i × n a t , s t a b i l i z e r : = bounded ( f a c t o r ) , P [ q ] : = ( P , q ) . \mathsf{str}:=\mathsf{nat}\to\mathsf{pauli},\quad\mathsf{factor}:=\mathsf{pauli}\times\mathsf{nat},\quad\mathsf{stabilizer}:=\operatorname{bounded}(\mathsf{factor}),\quad P[q]:=(P,q). str := nat → pauli , factor := pauli × nat , stabilizer := bounded ( factor ) , P [ q ] := ( P , q ) .
τ : : = n a t ∣ b o o l ∣ p a u l i ∣ τ × τ ∣ bounded ( τ ) ∣ s t r , \tau::=\mathsf{nat}\mid\mathsf{bool}\mid\mathsf{pauli}\mid\tau\times\tau\mid\operatorname{bounded}(\tau)\mid\mathsf{str}, τ ::= nat ∣ bool ∣ pauli ∣ τ × τ ∣ bounded ( τ ) ∣ str ,
e : : = x ∣ v ∣ o ( e , e ) ∣ ( e , e ) ∣ let ( x , y ) = e in e ∣ if e then e else e ∣ λ x < a . e ∣ e [ a ] ∣ λ x . p ∣ T ∣ C ( a , a ) , e::=x\mid v\mid o(e,e)\mid(e,e)\mid\operatorname{let}(x,y)=e\operatorname{\ in}e\mid\operatorname{if}e\operatorname{\ then}e\operatorname{\ else}e\mid\lambda x<a.e\mid e[a]\mid\lambda x.p\mid T\mid C(a,a), e ::= x ∣ v ∣ o ( e , e ) ∣ ( e , e ) ∣ let ( x , y ) = e in e ∣ if e then e else e ∣ λ x < a . e ∣ e [ a ] ∣ λ x . p ∣ T ∣ C ( a , a ) ,
o : : = + ∣ − ∣ ⋅ N ∣ div ∣ pow ∣ = N ∣ ⋅ P ∣ anti , o::=+\mid-\mid\cdot_{\mathbb{N}}\mid\operatorname{div}\mid\operatorname{pow}\mid=_{\mathbb{N}}\mid\cdot_{\mathbb{P}}\mid\operatorname{anti}, o ::= + ∣ − ∣ ⋅ N ∣ div ∣ pow ∣ = N ∣ ⋅ P ∣ anti ,
C : : = family C ( d , k ) = S C . (24) C::=\operatorname{family}\ C(d,k)=S_C. \tag*{(24)} C ::= family C ( d , k ) = S C . (24)
The operator types and typing rules are as follows.
x : τ ∈ Δ Δ ⊢ x : τ v ∈ V τ τ ∈ { n a t , b o o l , p a u l i } Δ ⊢ v : τ \frac{x:\tau\in\Delta}{\Delta\vdash x:\tau}
\qquad
\frac{v\in V_\tau\quad\tau\in\{\mathsf{nat},\mathsf{bool},\mathsf{pauli}\}}{\Delta\vdash v:\tau} Δ ⊢ x : τ x : τ ∈ Δ Δ ⊢ v : τ v ∈ V τ τ ∈ { nat , bool , pauli }
type ( o ) = τ 1 × τ 2 → τ Δ ⊢ e 1 : τ 1 Δ ⊢ e 2 : τ 2 Δ ⊢ o ( e 1 , e 2 ) : τ Δ ⊢ b : b o o l Δ ⊢ e 1 : τ Δ ⊢ e 2 : τ Δ ⊢ if b then e 1 else e 2 : τ \frac{\operatorname{type}(o)=\tau_1\times\tau_2\to\tau\quad\Delta\vdash e_1:\tau_1\quad\Delta\vdash e_2:\tau_2}{\Delta\vdash o(e_1,e_2):\tau}
\qquad
\frac{\Delta\vdash b:\mathsf{bool}\quad\Delta\vdash e_1:\tau\quad\Delta\vdash e_2:\tau}{\Delta\vdash\operatorname{if}\ b\operatorname{\ then}e_1\operatorname{\ else}e_2:\tau} Δ ⊢ o ( e 1 , e 2 ) : τ type ( o ) = τ 1 × τ 2 → τ Δ ⊢ e 1 : τ 1 Δ ⊢ e 2 : τ 2 Δ ⊢ if b then e 1 else e 2 : τ Δ ⊢ b : bool Δ ⊢ e 1 : τ Δ ⊢ e 2 : τ
Δ ⊢ e 1 : τ 1 Δ ⊢ e 2 : τ 2 Δ ⊢ ( e 1 , e 2 ) : τ 1 × τ 2 Δ ⊢ e : τ 1 × τ 2 Δ , x : τ 1 , y : τ 2 ⊢ e ′ : τ Δ ⊢ let ( x , y ) = e in e ′ : τ \frac{\Delta\vdash e_1:\tau_1\quad\Delta\vdash e_2:\tau_2}{\Delta\vdash(e_1,e_2):\tau_1\times\tau_2}
\qquad
\frac{\Delta\vdash e:\tau_1\times\tau_2\quad\Delta,x:\tau_1,y:\tau_2\vdash e':\tau}{\Delta\vdash\operatorname{let}(x,y)=e\operatorname{\ in}e':\tau} Δ ⊢ ( e 1 , e 2 ) : τ 1 × τ 2 Δ ⊢ e 1 : τ 1 Δ ⊢ e 2 : τ 2 Δ ⊢ let ( x , y ) = e in e ′ : τ Δ ⊢ e : τ 1 × τ 2 Δ , x : τ 1 , y : τ 2 ⊢ e ′ : τ
Δ ⊢ a : n a t Δ , x : n a t ⊢ e : τ Δ ⊢ λ x < a . e : bounded ( τ ) Δ ⊢ e : bounded ( τ ) Δ ⊢ a : n a t Δ ⊢ e [ a ] : τ Δ , x : n a t ⊢ p : p a u l i Δ ⊢ λ x . p : s t r \frac{\Delta\vdash a:\mathsf{nat}\quad\Delta,x:\mathsf{nat}\vdash e:\tau}{\Delta\vdash\lambda x<a.e:\operatorname{bounded}(\tau)}
\qquad
\frac{\Delta\vdash e:\operatorname{bounded}(\tau)\quad\Delta\vdash a:\mathsf{nat}}{\Delta\vdash e[a]:\tau}
\qquad
\frac{\Delta,x:\mathsf{nat}\vdash p:\mathsf{pauli}}{\Delta\vdash\lambda x.p:\mathsf{str}} Δ ⊢ λ x < a . e : bounded ( τ ) Δ ⊢ a : nat Δ , x : nat ⊢ e : τ Δ ⊢ e [ a ] : τ Δ ⊢ e : bounded ( τ ) Δ ⊢ a : nat Δ ⊢ λ x . p : str Δ , x : nat ⊢ p : pauli
Δ ⊢ T : s t r Δ ⊢ a : n a t Δ ⊢ T [ a ] : p a u l i Δ ⊢ a : n a t Δ , x : n a t ⊢ T : s t r Δ ⊢ ∏ x < a T : s t r Δ ⊢ a , a ′ : n a t Δ ⊢ C ( a , a ′ ) : s t a b i l i z e r \frac{\Delta\vdash T:\mathsf{str}\quad\Delta\vdash a:\mathsf{nat}}{\Delta\vdash T[a]:\mathsf{pauli}}
\qquad
\frac{\Delta\vdash a:\mathsf{nat}\quad\Delta,x:\mathsf{nat}\vdash T:\mathsf{str}}{\Delta\vdash\prod_{x<a}T:\mathsf{str}}
\qquad
\frac{\Delta\vdash a,a':\mathsf{nat}}{\Delta\vdash C(a,a'):\mathsf{stabilizer}} Δ ⊢ T [ a ] : pauli Δ ⊢ T : str Δ ⊢ a : nat Δ ⊢ ∏ x < a T : str Δ ⊢ a : nat Δ , x : nat ⊢ T : str Δ ⊢ C ( a , a ′ ) : stabilizer Δ ⊢ a , a ′ : nat
d : n a t , k : n a t ⊢ S C : s t a b i l i z e r ⊢ family C ( d , k ) = S C ok \frac{d:\mathsf{nat},k:\mathsf{nat}\vdash S_C:\mathsf{stabilizer}}{\vdash\operatorname{family}\ C(d,k)=S_C\ \operatorname{ok}} ⊢ family C ( d , k ) = S C ok d : nat , k : nat ⊢ S C : stabilizer
x ≠ y x \ne y x = y in let (x,y) = e in e', \quad ⟦ u − v ⟧ = max ( u − v , 0 ) \llbracket u-v\rrbracket=\max(u-v,0) [ [ u − v ] ] = max ( u − v , 0 ) , \quad
⟦ div ( u , v ) ⟧ = { ⌊ u / v ⌋ v > 0 , 0 v = 0 , \llbracket\operatorname{div}(u,v)\rrbracket=
\begin{cases}
\lfloor u/v\rfloor& v>0,\\
0 & v=0,
\end{cases} [ [ div ( u , v ) ] ] = { ⌊ u / v ⌋ 0 v > 0 , v = 0 ,
a ≤ b ≡ ( a − b = 0 ) a \le b \equiv(a-b=0) a ≤ b ≡ ( a − b = 0 ) , \quad a < b ≡ ( a + 1 − b = 0 ) a<b \equiv(a+1-b=0) a < b ≡ ( a + 1 − b = 0 ) , \quad a m o d b ≡ a − div ( a , b ) ⋅ N b a\bmod b \equiv a-\operatorname{div}(a,b)\cdot_{\mathbb{N}} b a mod b ≡ a − div ( a , b ) ⋅ N b .
CodeML evaluation and generation
We define CodeML values and evaluation with fuel f f f , followed by the generation of a QStab program.
V n a t = N , V b o o l = B , V p a u l i = P , V τ 1 × τ 2 = V τ 1 × V τ 2 , V_{\mathrm{nat}}=\mathbb{N},\quad V_{\mathrm{bool}}=\mathbb{B},\quad V_{\mathrm{pauli}}=\mathbb{P},\quad V_{\tau_1\times\tau_2}=V_{\tau_1}\times V_{\tau_2}, V nat = N , V bool = B , V pauli = P , V τ 1 × τ 2 = V τ 1 × V τ 2 ,
V b o u n d e d ( τ ) = { ( L , F ) : L ∈ N , F : [ L ] → V τ } , V s t r = N → P ⊥ , P ⊥ = P ⊎ { ⊥ } , V_{\mathrm{bounded}(\tau)}=\{(L,F):L\in\mathbb{N},\ F:[L]\to V_\tau\},\quad V_{\mathrm{str}}=\mathbb{N}\to\mathbb{P}_{\bot},\quad\mathbb{P}_{\bot}=\mathbb{P}\uplus\{\bot\}, V bounded ( τ ) = {( L , F ) : L ∈ N , F : [ L ] → V τ } , V str = N → P ⊥ , P ⊥ = P ⊎ { ⊥ } ,
⟦ e ⟧ f , ρ C = { v ρ ⊢ f C e ⇓ v , ⊥ otherwise . \llbracket e\rrbracket^{C}_{f,\rho}=
\begin{cases}
v & \rho\vdash^{C}_{f}e\Downarrow v,\\
\bot& \text{otherwise}.
\end{cases} [ [ e ] ] f , ρ C = { v ⊥ ρ ⊢ f C e ⇓ v , otherwise .
ρ ( x ) = v ρ ⊢ f C x ⇓ v \frac{\rho(x)=v}{\rho\vdash^{C}_{f}x\Downarrow v} ρ ⊢ f C x ⇓ v ρ ( x ) = v
ρ ⊢ f C e ⇓ v ρ ⊢ f C e ⇓ v \frac{\rho\vdash^{C}_{f}e\Downarrow v}{\rho\vdash^{C}_{f}e\Downarrow v} ρ ⊢ f C e ⇓ v ρ ⊢ f C e ⇓ v
ρ ⊢ f C e 1 ⇓ v 1 ρ ⊢ f C e 2 ⇓ v 2 ρ ⊢ f C o ( e 1 , e 2 ) ⇓ ⟦ o ⟧ ( v 1 , v 2 ) \frac{\rho\vdash^{C}_{f}e_1\Downarrow v_1\qquad\rho\vdash^{C}_{f}e_2\Downarrow v_2}
{\rho\vdash^{C}_{f}o(e_1,e_2)\Downarrow\llbracket o\rrbracket(v_1,v_2)} ρ ⊢ f C o ( e 1 , e 2 ) ⇓ [ [ o ] ] ( v 1 , v 2 ) ρ ⊢ f C e 1 ⇓ v 1 ρ ⊢ f C e 2 ⇓ v 2
ρ ⊢ f C b ⇓ 1 ρ ⊢ f C e 1 ⇓ v ρ ⊢ f C if b then e 1 else e 2 ⇓ v \frac{\rho\vdash^{C}_{f}b\Downarrow1\qquad\rho\vdash^{C}_{f}e_1\Downarrow v}
{\rho\vdash^{C}_{f}\textbf{if }b\textbf{ then }e_1\textbf{ else }e_2\Downarrow v} ρ ⊢ f C if b then e 1 else e 2 ⇓ v ρ ⊢ f C b ⇓ 1 ρ ⊢ f C e 1 ⇓ v
ρ ⊢ f C b ⇓ 0 ρ ⊢ f C e 2 ⇓ v ρ ⊢ f C if b then e 1 else e 2 ⇓ v \frac{\rho\vdash^{C}_{f}b\Downarrow0\qquad\rho\vdash^{C}_{f}e_2\Downarrow v}
{\rho\vdash^{C}_{f}\textbf{if }b\textbf{ then }e_1\textbf{ else }e_2\Downarrow v} ρ ⊢ f C if b then e 1 else e 2 ⇓ v ρ ⊢ f C b ⇓ 0 ρ ⊢ f C e 2 ⇓ v
ρ ⊢ f C e 1 ⇓ v 1 ρ ⊢ f C e 2 ⇓ v 2 ρ ⊢ f C ( e 1 , e 2 ) ⇓ ( v 1 , v 2 ) \frac{\rho\vdash^{C}_{f}e_1\Downarrow v_1\qquad\rho\vdash^{C}_{f}e_2\Downarrow v_2}
{\rho\vdash^{C}_{f}(e_1,e_2)\Downarrow(v_1,v_2)} ρ ⊢ f C ( e 1 , e 2 ) ⇓ ( v 1 , v 2 ) ρ ⊢ f C e 1 ⇓ v 1 ρ ⊢ f C e 2 ⇓ v 2
ρ ⊢ f C e ⇓ ( v 1 , v 2 ) ρ [ x ↦ v 1 , y ↦ v 2 ] ⊢ f C e ′ ⇓ v ρ ⊢ f C let ( x , y ) = e in e ′ ⇓ v \frac{\rho\vdash^{C}_{f}e\Downarrow(v_1,v_2)\qquad\rho[x\mapsto v_1,y\mapsto v_2]\vdash^{C}_{f}e'\Downarrow v}
{\rho\vdash^{C}_{f}\textbf{let }(x,y)=e\textbf{ in }e'\Downarrow v} ρ ⊢ f C let ( x , y ) = e in e ′ ⇓ v ρ ⊢ f C e ⇓ ( v 1 , v 2 ) ρ [ x ↦ v 1 , y ↦ v 2 ] ⊢ f C e ′ ⇓ v
\frac{\rho\vdash^{C}_{f}a\Downarrow L\qquad\forall t<L.\ \rho[x\mapsto t]\vdash^{C}_{f}e\Downarrow F(t)}
{\rho\vdash^{C}_{f}\lambda x<a.e\Downarrow(L,F)}
\quad\textsc{Bounded}
\frac{\rho\vdash^{C}_{f}e\Downarrow(L,F)\qquad\rho\vdash^{C}_{f}a\Downarrow t\qquad t<L}
{\rho\vdash^{C}_{f}e[a]\Downarrow F(t)}
\quad\textsc{Apply}
\frac{V(q)=\llbracket p\rrbracket^{C}_{f,\rho[x\mapsto q}}\qquad(q\in\mathbb{N})
{\rho\vdash^{C}_{f}\lambda x.p\Downarrow V}
\quad\textsc{String}
\frac{\rho\vdash^{C}_{f}T\Downarrow V\qquad\rho\vdash^{C}_{f}a\Downarrow q\qquad V(q)=P\in\mathbb{P}}
{\rho\vdash^{C}_{f}T[a]\Downarrow P}
\quad\textsc{Entry}
\frac{\rho\vdash^{C}_{f}a\Downarrow d_0\qquad\rho\vdash^{C}_{f}a'\Downarrow k_0\qquad[d\mapsto d_0,k\mapsto k_0]\vdash^{C}_{f}S_C\Downarrow W}
{\rho\vdash^{C}_{f+1}C(a,a')\Downarrow W}
\quad\textsc{Call}
ρ ⊢ 0 C C ( a , a ′ ) ⇓ v , \rho\vdash^{C}_{0}C(a,a')\Downarrow v, ρ ⊢ 0 C C ( a , a ′ ) ⇓ v ,
W L ( q ) : = { ∏ i < L V i ( q ) ∀ i < L . ρ [ x ↦ i ] ⊢ f C T ⇓ V i ∧ V i ( q ) ∈ P , ⊥ otherwise W_L(q):=
\begin{cases}
\prod_{i<L}V_i(q) & \forall i<L.\ \rho[x\mapsto i]\vdash^{C}_{f}T\Downarrow V_i\ \land\ V_i(q)\in\mathbb{P},\\
\bot& \text{otherwise}
\end{cases} W L ( q ) := { ∏ i < L V i ( q ) ⊥ ∀ i < L . ρ [ x ↦ i ] ⊢ f C T ⇓ V i ∧ V i ( q ) ∈ P , otherwise
ρ ⊢ f C a ⇓ L ρ ⊢ f C ∏ x < a T ⇓ W L \frac{\rho\vdash^{C}_{f}a\Downarrow L}
{\rho\vdash^{C}_{f}\prod_{x<a}T\Downarrow W_L} ρ ⊢ f C ∏ x < a T ⇓ W L ρ ⊢ f C a ⇓ L
∏ i < 0 V i ( q ) = I , F = ( C , Legal , n , m , f ) , n , m , f : N → N , \prod_{i<0} V_i(q)=I,\qquad\mathcal{F}=(C,\operatorname{Legal},n,m,f),\qquad n,m,f:\mathbb{N}\to\mathbb{N}, i < 0 ∏ V i ( q ) = I , F = ( C , Legal , n , m , f ) , n , m , f : N → N ,
GenOK ( d , R , B ) : = Legal ( d ) ∧ n ( d ) > 0 ∧ m ( d ) > 0 ∧ R > 0 ∧ B ≥ 0 \operatorname{GenOK}(d,R,B):=\operatorname{Legal}(d)\land n(d)>0\land m(d)>0\land R>0\land B\ge0 GenOK ( d , R , B ) := Legal ( d ) ∧ n ( d ) > 0 ∧ m ( d ) > 0 ∧ R > 0 ∧ B ≥ 0
∧ ∀ k < m ( d ) . ∅ ⊢ f ( d ) C C ( d , k ) ⇓ ( L k , F k ) ∧ ∀ t < L k . F k ( t ) = ( P k , t , q k , t ) ∈ P × [ n ( d ) ] \land\ \forall k<m(d).\ \varnothing\vdash_{f(d)}^{C}C(d,k)\Downarrow(L_k,F_k)\land\forall t<L_k.\ F_k(t)=(P_{k,t},q_{k,t})\in P\times[n(d)] ∧ ∀ k < m ( d ) . ∅ ⊢ f ( d ) C C ( d , k ) ⇓ ( L k , F k ) ∧ ∀ t < L k . F k ( t ) = ( P k , t , q k , t ) ∈ P × [ n ( d )]
∧ ∀ k < m ( d ) . ∀ t , t ′ < L k . q k , t = q k , t ′ ⇒ t = t ′ , \land\ \forall k<m(d).\ \forall t,t'<L_k.\ q_{k,t}=q_{k,t'}\Rightarrow t=t', ∧ ∀ k < m ( d ) . ∀ t , t ′ < L k . q k , t = q k , t ′ ⇒ t = t ′ ,
r k = [ ( P k , t ) q k , t ] t < L k , T k ( q ) = ∏ t < L k , q k , t = q P k , t , r_k=[(P_{k,t})_{q_{k,t}}]_{t<L_k},\qquad T_k(q)=\prod_{\substack{t<L_k,\\q_{k,t}=q}}P_{k,t}, r k = [( P k , t ) q k , t ] t < L k , T k ( q ) = t < L k , q k , t = q ∏ P k , t ,
Generate ⟦ C ⟧ ( d ; R , B ) = { ⟨ n ( d ) , [ r k ] k < m ( d ) , R , B ⟩ GenOK ( d , R , B ) , ⊥ otherwise . \operatorname{Generate}\llbracket C\rrbracket(d;R,B)=
\begin{cases}
\langle n(d),[r_k]_{k<m(d)},R,B\rangle& \operatorname{GenOK}(d,R,B),\\
\perp& \text{otherwise}.
\end{cases} Generate [ [ C ] ] ( d ; R , B ) = { ⟨ n ( d ) , [ r k ] k < m ( d ) , R , B ⟩ ⊥ GenOK ( d , R , B ) , otherwise .
Assertions and code-algebra judgments
The following grammar defines assertions over CodeML terms and the residual data error E E E .
e A : : = e ∣ E ∣ let x = a in e A , E : str , b , ℓ : nat . e_A ::= e\mid E\mid\operatorname{let}\ x=a\ \operatorname{in}\ e_A,\qquad E:\operatorname{str},\quad b,\ell:\operatorname{nat}. e A ::= e ∣ E ∣ let x = a in e A , E : str , b , ℓ : nat .
A : : = a = a ′ ∣ T ≡ a U ∣ ⟨ T , U ⟩ a = 0 ∣ wt a ( T ) ≤ a ′ ∣ A ∧ A ∣ ¬ A ∣ let x = a in A ∣ ∀ x < a . A . (25) A ::= a=a'\mid T\equiv_a U\mid\langle T,U\rangle_a=0\mid\operatorname{wt}_a(T)\le a'\mid A\land A\mid\neg A\mid\operatorname{let}\ x=a\ \operatorname{in}\ A\mid\forall x<a.\ A. \tag*{(25)} A ::= a = a ′ ∣ T ≡ a U ∣ ⟨ T , U ⟩ a = 0 ∣ wt a ( T ) ≤ a ′ ∣ A ∧ A ∣ ¬ A ∣ let x = a in A ∣ ∀ x < a . A . (25)
The following evaluator defines satisfaction, including the propagation of undefined values.
test C , f , ρ , V ( A ) ∈ B ⊥ , ρ ( E ) = V , B ⊥ = B ⊎ { ⊥ } , ( ρ , V ) ⊨ A ⟺ test C , f , ρ , V ( A ) = 1. \operatorname{test}_{C,f,\rho,V}(A)\in\mathbb{B}_{\perp},\qquad\rho(E)=V,\qquad\mathbb{B}_{\perp}=\mathbb{B}\uplus\{\perp\},\qquad(\rho,V)\models A\Longleftrightarrow\operatorname{test}_{C,f,\rho,V}(A)=1. test C , f , ρ , V ( A ) ∈ B ⊥ , ρ ( E ) = V , B ⊥ = B ⊎ { ⊥ } , ( ρ , V ) ⊨ A ⟺ test C , f , ρ , V ( A ) = 1.
bind ( u , F ) = { F ( u ) u ≠ ⊥ , ⊥ u = ⊥ , and ( u , v ) = { 0 u = 0 , v u = 1 , ⊥ u = ⊥ , neg ( u ) = { 1 − u u ∈ B , ⊥ u = ⊥ . \operatorname{bind}(u,F)=
\begin{cases}
F(u)&u\ne\perp,\\
\perp&u=\perp,
\end{cases}
\qquad
\operatorname{and}(u,v)=
\begin{cases}
0&u=0,\\
v&u=1,\\
\perp&u=\perp,
\end{cases}
\qquad
\operatorname{neg}(u)=
\begin{cases}
1-u&u\in\mathbb{B},\\
\perp&u=\perp.
\end{cases} bind ( u , F ) = { F ( u ) ⊥ u = ⊥ , u =⊥ , and ( u , v ) = ⎩ ⎨ ⎧ 0 v ⊥ u = 0 , u = 1 , u =⊥ , neg ( u ) = { 1 − u ⊥ u ∈ B , u =⊥ .
scan ( L , F ) = go ( 0 ) , go ( q ) = { 1 q = L , and ( F ( q ) , go ( q + 1 ) ) q < L . \operatorname{scan}(L,F)=\operatorname{go}(0),\qquad
\operatorname{go}(q)=
\begin{cases}
1&q=L,\\
\operatorname{and}(F(q),\operatorname{go}(q+1))&q<L.
\end{cases} scan ( L , F ) = go ( 0 ) , go ( q ) = { 1 and ( F ( q ) , go ( q + 1 )) q = L , q < L .
eq P ( u , v ) = { [ u = v ] u , v ∈ P , ⊥ otherwise , eqstr n ( T , U ) = scan ( n , λ q . eq P ( T ( q ) , U ( q ) ) ) . \operatorname{eq}_{\mathbb{P}}(u,v)=
\begin{cases}
[u=v]&u,v\in\mathbb{P},\\
\perp&\text{otherwise},
\end{cases}
\qquad
\operatorname{eqstr}_n(T,U)=\operatorname{scan}(n,\lambda q.\operatorname{eq}_{\mathbb{P}}(T(q),U(q))). eq P ( u , v ) = { [ u = v ] ⊥ u , v ∈ P , otherwise , eqstr n ( T , U ) = scan ( n , λ q . eq P ( T ( q ) , U ( q ))) .
p 0 = 0 , p q + 1 = p q ⊕ anti ( T ( q ) , U ( q ) ) , w 0 = 0 , w q + 1 = w q + [ T ( q ) ≠ I ] , p_0=0,\qquad p_{q+1}=p_q\oplus\operatorname{anti}(T(q),U(q)),\qquad
w_0=0,\qquad w_{q+1}=w_q+[T(q)\ne I], p 0 = 0 , p q + 1 = p q ⊕ anti ( T ( q ) , U ( q )) , w 0 = 0 , w q + 1 = w q + [ T ( q ) = I ] ,
anti ( ⊥ , u ) = anti ( u , ⊥ ) = ⊥ , [ ⊥ ≠ I ] = ⊥ , u ⊕ ⊥ = u + ⊥ = ⊥ . \operatorname{anti}(\perp,u)=\operatorname{anti}(u,\perp)=\perp,\qquad[\perp\ne I]=\perp,\qquad u\oplus\perp=u+\perp=\perp. anti ( ⊥ , u ) = anti ( u , ⊥ ) =⊥ , [ ⊥ = I ] =⊥ , u ⊕ ⊥= u + ⊥=⊥ .
test ( a = a ′ ) = bind ( ⟦ a ⟧ , λ u . bind ( ⟦ a ′ ⟧ , λ v . [ u = v ] ) ) , \operatorname{test}(a=a')=\operatorname{bind}(\llbracket a\rrbracket,\lambda u.\operatorname{bind}(\llbracket a'\rrbracket,\lambda v.[u=v])), test ( a = a ′ ) = bind ( [ [ a ] ] , λ u . bind ( [ [ a ′ ] ] , λ v . [ u = v ])) ,
test ( T ≡ a U ) = bind ( ⟦ a ⟧ , λ n . bind ( ⟦ T ⟧ , λ T 0 . bind ( ⟦ U ⟧ , λ U 0 . eqstr n ( T 0 , U 0 ) ) ) ) , \operatorname{test}(T\equiv_a U)=\operatorname{bind}(\llbracket a\rrbracket,\lambda n.\operatorname{bind}(\llbracket T\rrbracket,\lambda T_0.\operatorname{bind}(\llbracket U\rrbracket,\lambda U_0.\operatorname{eqstr}_n(T_0,U_0)))), test ( T ≡ a U ) = bind ( [ [ a ] ] , λn . bind ( [ [ T ] ] , λ T 0 . bind ( [ [ U ] ] , λ U 0 . eqstr n ( T 0 , U 0 )))) ,
test ( ⟨ T , U ⟩ a = 0 ) = bind ( ⟦ a ⟧ , λ n . bind ( ⟦ T ⟧ , λ T 0 . bind ( ⟦ U ⟧ , λ U 0 . bind ( p n ( T 0 , U 0 ) , λ p . [ p = 0 ] ) ) ) ) , \operatorname{test}(\langle T,U\rangle_a=0)=\operatorname{bind}(\llbracket a\rrbracket,\lambda n.\operatorname{bind}(\llbracket T\rrbracket,\lambda T_0.\operatorname{bind}(\llbracket U\rrbracket,\lambda U_0.\operatorname{bind}(p_n(T_0,U_0),\lambda p.[p=0])))), test (⟨ T , U ⟩ a = 0 ) = bind ( [ [ a ] ] , λn . bind ( [ [ T ] ] , λ T 0 . bind ( [ [ U ] ] , λ U 0 . bind ( p n ( T 0 , U 0 ) , λ p . [ p = 0 ])))) ,
test ( wt a ( T ) ≤ a ′ ) = bind ( ⟦ a ⟧ , λ n . bind ( ⟦ a ′ ⟧ , λ k . bind ( ⟦ T ⟧ , λ T 0 . bind ( w n ( T 0 ) , λ w . [ w ≤ k ] ) ) ) ) , \operatorname{test}(\operatorname{wt}_a(T)\le a')=\operatorname{bind}(\llbracket a\rrbracket,\lambda n.\operatorname{bind}(\llbracket a'\rrbracket,\lambda k.\operatorname{bind}(\llbracket T\rrbracket,\lambda T_0.\operatorname{bind}(w_n(T_0),\lambda w.[w\le k])))), test ( wt a ( T ) ≤ a ′ ) = bind ( [ [ a ] ] , λn . bind ( [ [ a ′ ] ] , λk . bind ( [ [ T ] ] , λ T 0 . bind ( w n ( T 0 ) , λ w . [ w ≤ k ])))) ,
test ( A ∧ B ) = and ( test ( A ) , test ( B ) ) , \operatorname{test}(A\land B)=\operatorname{and}(\operatorname{test}(A),\operatorname{test}(B)), test ( A ∧ B ) = and ( test ( A ) , test ( B )) ,
test ( ¬ A ) = neg ( test ( A ) ) , \operatorname{test}(\neg A)=\operatorname{neg}(\operatorname{test}(A)), test ( ¬ A ) = neg ( test ( A )) ,
test ( let x = a in A ) = bind ( ⟦ a ⟧ , λ u . test ρ [ x ↦ u ] , V ( A ) ) , \operatorname{test}(\operatorname{let}\ x=a\ \operatorname{in}\ A)=\operatorname{bind}(\llbracket a\rrbracket,\lambda u.\operatorname{test}_{\rho[x\mapsto u],V}(A)), test ( let x = a in A ) = bind ( [ [ a ] ] , λ u . test ρ [ x ↦ u ] , V ( A )) ,
test ( ∀ x < a . A ) = bind ( ⟦ a ⟧ , λ L . scan ( L , λ i . test ρ [ x ↦ i ] , V ( A ) ) ) . \operatorname{test}(\forall x<a.\ A)=\operatorname{bind}(\llbracket a\rrbracket,\lambda L.\operatorname{scan}(L,\lambda i.\operatorname{test}_{\rho[x\mapsto i],V}(A))). test ( ∀ x < a . A ) = bind ( [ [ a ] ] , λ L . scan ( L , λi . test ρ [ x ↦ i ] , V ( A ))) .
The remaining logical connectives are defined from conjunction, negation and bounded universal quantification.
⊤ : = ( 0 = 0 ) , ⊥ A : = ¬ ⊤ , A ∨ B : = ¬ ( ¬ A ∧ ¬ B ) , \top:=(0=0),\qquad\perp_A:=\neg\top,\qquad A\lor B:=\neg(\neg A\land\neg B), ⊤ := ( 0 = 0 ) , ⊥ A := ¬⊤ , A ∨ B := ¬ ( ¬ A ∧ ¬ B ) ,
A ⇒ B : = ¬ ( A ∧ ¬ B ) , ∃ x < a . A : = ¬ ∀ x < a . ¬ A . (26) A\Rightarrow B:=\neg(A\land\neg B),\qquad\exists x<a.\ A:=\neg\forall x<a.\neg A. \tag*{(26)} A ⇒ B := ¬ ( A ∧ ¬ B ) , ∃ x < a . A := ¬∀ x < a .¬ A . (26)
The following judgments and inference rules define reasoning about assertions under assumptions Γ \Gamma Γ .
Total ( n , V ) : = ∀ q < n . V ( q ) ≠ ⊥ , Def ( A ) : = A ∨ ¬ A , \operatorname{Total}(n,V) := \forall q < n.\ V(q) \ne\bot,\qquad\operatorname{Def}(A) := A \vee\neg A, Total ( n , V ) := ∀ q < n . V ( q ) = ⊥ , Def ( A ) := A ∨ ¬ A ,
Γ ⊨ C , f , n A ⟺ ∀ ρ , V . Total ( n , V ) ∧ ( ρ , V ) ⊨ Γ ⇒ ( ρ , V ) ⊨ A . \Gamma\mathrel{\vDash_{C,f,n}} A \Longleftrightarrow\forall\rho,V.\ \operatorname{Total}(n,V) \wedge(\rho,V) \mathrel{\vDash} \Gamma\Rightarrow(\rho,V) \mathrel{\vDash} A. Γ ⊨ C , f , n A ⟺ ∀ ρ , V . Total ( n , V ) ∧ ( ρ , V ) ⊨ Γ ⇒ ( ρ , V ) ⊨ A .
A ∈ Γ Γ ⊢ A Γ ⊢ A Γ , B ⊢ A Γ ⊢ ⊥ A Γ ⊢ A Γ ⊢ A Γ ⊢ B Γ ⊢ A ∧ B Γ ⊢ A ∧ B Γ ⊢ A Γ ⊢ A ∧ B Γ ⊢ B \frac{A \in\Gamma}{\Gamma\vdash A}
\qquad
\frac{\Gamma\vdash A}{\Gamma,B \vdash A}
\qquad
\frac{\Gamma\vdash\bot_A}{\Gamma\vdash A}
\qquad
\frac{\Gamma\vdash A\qquad\Gamma\vdash B}{\Gamma\vdash A \wedge B}
\qquad
\frac{\Gamma\vdash A \wedge B}{\Gamma\vdash A}
\qquad
\frac{\Gamma\vdash A \wedge B}{\Gamma\vdash B} Γ ⊢ A A ∈ Γ Γ , B ⊢ A Γ ⊢ A Γ ⊢ A Γ ⊢ ⊥ A Γ ⊢ A ∧ B Γ ⊢ A Γ ⊢ B Γ ⊢ A Γ ⊢ A ∧ B Γ ⊢ B Γ ⊢ A ∧ B
Γ ⊢ A Γ , A ⊢ D Γ , B ⊢ D Γ ⊢ D Γ ⊢ A Γ ⊢ A ⇒ B Γ ⊢ B \frac{\Gamma\vdash A \qquad\Gamma,A \vdash D \qquad\Gamma,B \vdash D}{\Gamma\vdash D}
\qquad
\frac{\Gamma\vdash A \qquad\Gamma\vdash A \Rightarrow B}{\Gamma\vdash B} Γ ⊢ D Γ ⊢ A Γ , A ⊢ D Γ , B ⊢ D Γ ⊢ B Γ ⊢ A Γ ⊢ A ⇒ B
Γ ⊢ A Γ ⊢ A ∨ B Γ ⊢ Def ( A ) Γ ⊢ B Γ ⊢ A ∨ B Γ ⊢ Def ( A ) Γ , A ⊢ B Γ ⊢ A ⇒ B Γ ⊢ Def ( A ) Γ , A ⊢ ⊥ A Γ ⊢ ¬ A \frac{\Gamma\vdash A}{\Gamma\vdash A \vee B}
\qquad
\frac{\Gamma\vdash\operatorname{Def}(A)\qquad\Gamma\vdash B}{\Gamma\vdash A \vee B}
\qquad
\frac{\Gamma\vdash\operatorname{Def}(A)\qquad\Gamma,A \vdash B}{\Gamma\vdash A \Rightarrow B}
\qquad
\frac{\Gamma\vdash\operatorname{Def}(A)\qquad\Gamma,A \vdash\bot_A}{\Gamma\vdash\neg A} Γ ⊢ A ∨ B Γ ⊢ A Γ ⊢ A ∨ B Γ ⊢ Def ( A ) Γ ⊢ B Γ ⊢ A ⇒ B Γ ⊢ Def ( A ) Γ , A ⊢ B Γ ⊢ ¬ A Γ ⊢ Def ( A ) Γ , A ⊢ ⊥ A
Γ , x < h ⊢ A Γ ⊢ ∀ x < h . A Γ ⊢ ∀ x < h . A Γ ⊢ t < h Γ ⊢ A [ t / x ] \frac{\Gamma,x < h \vdash A}{\Gamma\vdash\forall x < h.A}
\qquad
\frac{\Gamma\vdash\forall x < h.A\qquad\Gamma\vdash t < h}{\Gamma\vdash A[t/x]} Γ ⊢ ∀ x < h . A Γ , x < h ⊢ A Γ ⊢ A [ t / x ] Γ ⊢ ∀ x < h . A Γ ⊢ t < h
Γ ⊢ ∀ x < h . Def ( A ) Γ ⊢ t < h Γ ⊢ A [ t / x ] Γ ⊢ ∃ x < h . A Γ ⊢ ∃ x < h . A Γ , x < h , A ⊢ B Γ ⊢ B \frac{\Gamma\vdash\forall x < h.\operatorname{Def}(A)\qquad\Gamma\vdash t < h\qquad\Gamma\vdash A[t/x]}{\Gamma\vdash\exists x < h.A}
\qquad
\frac{\Gamma\vdash\exists x < h.A\qquad\Gamma,x < h,A \vdash B}{\Gamma\vdash B} Γ ⊢ ∃ x < h . A Γ ⊢ ∀ x < h . Def ( A ) Γ ⊢ t < h Γ ⊢ A [ t / x ] Γ ⊢ B Γ ⊢ ∃ x < h . A Γ , x < h , A ⊢ B
⊢ = ⊢ C , f , n , TotalNat ( h ) ∧ TotalNat ( t ) , x ∉ FV ( Γ , h ) , x ∉ FV ( B ) ( ∃ -elimination ) . \vdash= \vdash_{C,f,n},\qquad\operatorname{TotalNat}(h) \wedge\operatorname{TotalNat}(t),\qquad x \notin\operatorname{FV}(\Gamma,h),\qquad x \notin\operatorname{FV}(B)\quad(\exists\text{-elimination}). ⊢= ⊢ C , f , n , TotalNat ( h ) ∧ TotalNat ( t ) , x ∈ / FV ( Γ , h ) , x ∈ / FV ( B ) ( ∃ -elimination ) .
Here TotalNat ( h ) \operatorname{TotalNat}(h) TotalNat ( h ) states that h h h evaluates to a natural number under every valuation satisfying Γ \Gamma Γ . The outer judgment Γ ⊢ C F \Gamma\vdash_C F Γ ⊢ C F fixes the family C C C and quantifies over natural parameters and total residuals. It uses ordinary first-order deduction over these assertions, including evaluation of closed atomic assertions, together with natural induction on a variable that is fresh for Γ \Gamma Γ :
Γ ⊢ C F ( 0 ) Γ , k ∈ N , F ( k ) ⊢ C F ( k + 1 ) k ∉ FV ( Γ ) Γ ⊢ C ∀ k ∈ N . F ( k ) \frac{\Gamma\vdash_C F(0)\qquad\Gamma,k \in\mathbb{N},F(k) \vdash_C F(k+1)\qquad k \notin\operatorname{FV}(\Gamma)}
{\Gamma\vdash_C \forall k \in\mathbb{N}.F(k)} Γ ⊢ C ∀ k ∈ N . F ( k ) Γ ⊢ C F ( 0 ) Γ , k ∈ N , F ( k ) ⊢ C F ( k + 1 ) k ∈ / FV ( Γ )
The Surface code induction on odd d d d instantiates F ( k ) F(k) F ( k ) at d = 2 k + 3 d = 2k+3 d = 2 k + 3 . The code-algebra predicates below express normalizer membership, stabilizer generation, logical errors and well-formedness.
a k = ⌊ a 2 k ⌋ m o d 2 , T 0 = I n , T 1 = T . a_k = \left\lfloor\frac{a}{2^k}\right\rfloor\bmod2,\qquad T^0 = I^n,\qquad T^1 = T. a k = ⌊ 2 k a ⌋ mod 2 , T 0 = I n , T 1 = T .
Norm ( E ) : = ∀ k < m . ⟨ T k , E ⟩ n = 0 , \operatorname{Norm}(E) := \forall k < m.\ \langle T_k,E\rangle_n = 0, Norm ( E ) := ∀ k < m . ⟨ T k , E ⟩ n = 0 ,
Gen ( E ) : = ∃ a < 2 m . E ≡ n ∏ k < m T k a k , \operatorname{Gen}(E) := \exists a < 2^m.\ E \equiv_n \prod_{k<m} T_k^{a_k}, Gen ( E ) := ∃ a < 2 m . E ≡ n k < m ∏ T k a k ,
Logical ( E ) : = Norm ( E ) ∧ ¬ Gen ( E ) , \operatorname{Logical}(E) := \operatorname{Norm}(E) \wedge\neg\operatorname{Gen}(E), Logical ( E ) := Norm ( E ) ∧ ¬ Gen ( E ) ,
WellFormed : = ( ∀ k < m . T k ≡ n T k ) ∧ ( ∀ i , j < m . ⟨ T i , T j ⟩ n = 0 ) . (27) \operatorname{WellFormed} := \left(\forall k < m.\ T_k \equiv_n T_k\right) \wedge\left(\forall i,j < m.\langle T_i,T_j\rangle_n = 0\right). \tag*{(27)} WellFormed := ( ∀ k < m . T k ≡ n T k ) ∧ ( ∀ i , j < m . ⟨ T i , T j ⟩ n = 0 ) . (27)
Cut signatures as strings. To use the string-weight test in Equation (25) on the cut signatures of Equation (13) , we store each parity bit as I for zero or X for one. Since X ⋅ X = I X \cdot X = I X ⋅ X = I , string multiplication computes XOR. For each cut, a product over the n n n data wires contributes X at anticommuting sites and I elsewhere. Thus U ⊕ V : = λ j . U [ j ] ⋅ V [ j ] U \oplus V := \lambda j.U[j] \cdot V[j] U ⊕ V := λj . U [ j ] ⋅ V [ j ] , equality uses ≡ d \equiv_d ≡ d , and string weight counts the crossed cuts. Bounded products and string lambdas express these operations in the core language. For example, the signature (1, 0, 0) of the hook error becomes the string X I I XII X I I , whose weight is one. The logical row’s signature (1, 1, 1) becomes X X X XXX X X X , whose weight is three. The signature e i e_i e i with only bit i i i set has the CodeML representation e i : = λ j . if j = i then X else I e_i := \lambda j.\ \text{if }j=i\text{ then }X\text{ else }I e i := λj . if j = i then X else I .
QStab syntax and transitions
We define QStab programs and states, then give the error and measurement transitions.
r : : = [ ( P j ) q j ] j < w , S = ⟨ n , r ⃗ , R , B ⟩ , n > 0 , m = ∣ r ⃗ ∣ > 0 , R > 0 , M = m R , B ∈ N , r h = r ⃗ [ h m o d m ] , T h = ∏ i < ∣ r h ∣ r h [ i ] , Hooks ( h ) = { ∏ j ≤ i < ∣ r h ∣ r h [ i ] : 0 ≤ j ≤ ∣ r h ∣ } , σ = ( E , G , h , b , ℓ ) ∈ P n × B M × [ M ] × N 2 , γ : : = run ( σ ) ∣ done ( σ ) ∣ error ( σ ) , γ 0 = run ( I n , 0 , 0 , B , 0 ) , v = G h ⊕ ⟨ T h , E ⟩ n . \begin{aligned}
r &::= [(P_j)_{q_j}]_{j<w}, \qquad S=\langle n,\vec r,R,B\rangle,\qquad n>0,\ m=|\vec r|>0,\ R>0,\ M=mR,\ B\in\mathbb{N},\\
r_h&=\vec r[h\bmod m],\qquad T_h=\prod_{i<|r_h|}r_h[i],\qquad
\operatorname{Hooks}(h)=\left\{\prod_{j\leq i<|r_h|}r_h[i]:0\leq j\leq|r_h|\right\},\\
\sigma&=(E,G,h,b,\ell)\in\mathcal{P}^{n}\times\mathbb{B}^{M}\times[M]\times\mathbb{N}^{2},\\
\gamma&::=\operatorname{run}(\sigma)\mid\operatorname{done}(\sigma)\mid\operatorname{error}(\sigma),\qquad
\gamma_0=\operatorname{run}(I^n,0,0,B,0),\qquad v=G_h\oplus\langle T_h,E\rangle_n.
\end{aligned} r r h σ γ ::= [( P j ) q j ] j < w , S = ⟨ n , r , R , B ⟩ , n > 0 , m = ∣ r ∣ > 0 , R > 0 , M = m R , B ∈ N , = r [ h mod m ] , T h = i < ∣ r h ∣ ∏ r h [ i ] , Hooks ( h ) = ⎩ ⎨ ⎧ j ≤ i < ∣ r h ∣ ∏ r h [ i ] : 0 ≤ j ≤ ∣ r h ∣ ⎭ ⎬ ⎫ , = ( E , G , h , b , ℓ ) ∈ P n × B M × [ M ] × N 2 , ::= run ( σ ) ∣ done ( σ ) ∣ error ( σ ) , γ 0 = run ( I n , 0 , 0 , B , 0 ) , v = G h ⊕ ⟨ T h , E ⟩ n .
b > 0 q < n P ∈ { X , Y , Z } run ( E , G , h , b , ℓ ) → 1 S run ( E P q , G , h , b − 1 , ℓ + 1 ) QS-Data \frac{b>0\quad q<n\quad P\in\{X,Y,Z\}}
{\operatorname{run}(E,G,h,b,\ell)\mathrel{\xrightarrow{1}_{S}}\operatorname{run}(EP_q,G,h,b-1,\ell+1)}
\quad\textnormal{QS-Data} run ( E , G , h , b , ℓ ) 1 S run ( E P q , G , h , b − 1 , ℓ + 1 ) b > 0 q < n P ∈ { X , Y , Z } QS-Data
b > 0 q < n P ∈ { X , Y , Z } t ∈ B run ( E , G , h , b , ℓ ) → 1 S run ( E P q , G [ h ↦ G h ⊕ t ] , h , b − 1 , ℓ + 1 ) QS-DataReadout \frac{b>0\quad q<n\quad P\in\{X,Y,Z\}\quad t\in\mathbb{B}}
{\operatorname{run}(E,G,h,b,\ell)\mathrel{\xrightarrow{1}_{S}}\operatorname{run}(EP_q,G[h\mapsto G_h\oplus t],h,b-1,\ell+1)}
\quad\textnormal{QS-DataReadout} run ( E , G , h , b , ℓ ) 1 S run ( E P q , G [ h ↦ G h ⊕ t ] , h , b − 1 , ℓ + 1 ) b > 0 q < n P ∈ { X , Y , Z } t ∈ B QS-DataReadout
b > 0 H ∈ Hooks ( h ) t ∈ B run ( E , G , h , b , ℓ ) → 1 S run ( E H , G [ h ↦ G h ⊕ t ] , h , b − 1 , ℓ + 1 ) QS-Hook \frac{b>0\quad H\in\operatorname{Hooks}(h)\quad t\in\mathbb{B}}
{\operatorname{run}(E,G,h,b,\ell)\mathrel{\xrightarrow{1}_{S}}\operatorname{run}(EH,G[h\mapsto G_h\oplus t],h,b-1,\ell+1)}
\quad\textnormal{QS-Hook} run ( E , G , h , b , ℓ ) 1 S run ( E H , G [ h ↦ G h ⊕ t ] , h , b − 1 , ℓ + 1 ) b > 0 H ∈ Hooks ( h ) t ∈ B QS-Hook
b > 0 run ( E , G , h , b , ℓ ) → 1 S run ( E , G [ h ↦ G h ⊕ 1 ] , h , b − 1 , ℓ + 1 ) QS-Readout \frac{b>0}
{\operatorname{run}(E,G,h,b,\ell)\mathrel{\xrightarrow{1}_{S}}\operatorname{run}(E,G[h\mapsto G_h\oplus1],h,b-1,\ell+1)}
\quad\textnormal{QS-Readout} run ( E , G , h , b , ℓ ) 1 S run ( E , G [ h ↦ G h ⊕ 1 ] , h , b − 1 , ℓ + 1 ) b > 0 QS-Readout
h + 1 < M run ( σ ) → 0 S run ( E , G [ h ↦ v ] , h + 1 , b , ℓ ) QS-Meas \frac{h+1<M}
{\operatorname{run}(\sigma)\mathrel{\xrightarrow{0}_{S}}\operatorname{run}(E,G[h\mapsto v],h+1,b,\ell)}
\quad\textnormal{QS-Meas} run ( σ ) 0 S run ( E , G [ h ↦ v ] , h + 1 , b , ℓ ) h + 1 < M QS-Meas
h + 1 = M run ( σ ) → 0 S done ( E , G [ h ↦ v ] , h , b , ℓ ) QS-Halt \frac{h+1=M}
{\operatorname{run}(\sigma)\mathrel{\xrightarrow{0}_{S}}\operatorname{done}(E,G[h\mapsto v],h,b,\ell)}
\quad\textnormal{QS-Halt} run ( σ ) 0 S done ( E , G [ h ↦ v ] , h , b , ℓ ) h + 1 = M QS-Halt
b = 0 run ( σ ) → 0 S error ( σ ) QS-Exhaust \frac{b=0}
{\operatorname{run}(\sigma)\mathrel{\xrightarrow{0}_{S}}\operatorname{error}(\sigma)}
\quad\textnormal{QS-Exhaust} run ( σ ) 0 S error ( σ ) b = 0 QS-Exhaust
A readout error can hide the evidence of a data error. For the first stabilizer T 0 = Z 0 Z 3 Z 1 Z 4 T_0=Z_0Z_3Z_1Z_4 T 0 = Z 0 Z 3 Z 1 Z 4 of S 3 S_3 S 3 , a data error X 3 X_3 X 3 followed by a readout error gives E = X 3 E=X_3 E = X 3 , G 0 = 1 G_0=1 G 0 = 1 and ℓ = 2 \ell=2 ℓ = 2 . Measurement commits 1 ⊕ ⟨ T 0 , X 3 ⟩ 9 = 1 ⊕ 1 = 0 1\oplus\langle T_0,X_3\rangle_9=1\oplus1=0 1 ⊕ ⟨ T 0 , X 3 ⟩ 9 = 1 ⊕ 1 = 0 . This hides one syndrome bit. The full failure test checks all detectors and whether the residual is logical.
Source invariance requires an assertion to hold at every reachable QStab state. A configuration run ( σ ) \operatorname{run}(\sigma) run ( σ ) , done ( σ ) \operatorname{done}(\sigma) done ( σ ) or error ( σ ) \operatorname{error}(\sigma) error ( σ ) satisfies A A A when A A A holds for the residual E E E and the values b , ℓ b,\ell b , ℓ of σ \sigma σ .
Definition A.1 (Source invariance).
S ⊨ □ A ⟺ ∀ γ . γ 0 → ∗ S γ ⇒ γ ⊨ A , S\models\Box A\Longleftrightarrow\forall\gamma.\ \gamma_0\xrightarrow{*}_{S}\gamma\Rightarrow\gamma\models A, S ⊨ □ A ⟺ ∀ γ . γ 0 ∗ S γ ⇒ γ ⊨ A , Γ ⊨ S ⊨ □ A ⟺ ∀ ρ ⊨ Γ . S ρ ⊨ □ A ρ . \Gamma\models S\models\Box A\Longleftrightarrow\forall\rho\models\Gamma.\ S_\rho\models\Box A_\rho. Γ ⊨ S ⊨ □ A ⟺ ∀ ρ ⊨ Γ. S ρ ⊨ □ A ρ .
QStab invariant rules
The following definitions describe cut signatures and the bounds on hook errors used to prove QStab invariants.
L : N × [ n ] → N , ν > 0 , P ∈ { X , Z } , κ i L , P ( q ) = { P L ( ν , q ) = i , I L ( ν , q ) ≠ i , χ L , P ( E ) i = ⟨ κ i L , P , E ⟩ n ( i < ν ) . L:\mathbb{N}\times[n]\to\mathbb{N},\qquad\nu>0,\qquad P\in\{X,Z\},\qquad
\kappa_i^{L,P}(q)=
\begin{cases}
P & L(\nu,q)=i,\\
I & L(\nu,q)\ne i,
\end{cases}
\qquad
\chi_{L,P}(E)_i=\langle\kappa_i^{L,P},E\rangle_n\quad(i<\nu). L : N × [ n ] → N , ν > 0 , P ∈ { X , Z } , κ i L , P ( q ) = { P I L ( ν , q ) = i , L ( ν , q ) = i , χ L , P ( E ) i = ⟨ κ i L , P , E ⟩ n ( i < ν ) .
Definition A.2 (Cut bounds for hook errors).
w = ∣ r ∣ , sig L , P ( r ) = [ v j ] j < w , v j = χ L , P ( r [ j ] ) ∈ B ν . w = |r|,\qquad\operatorname{sig}_{L,P}(r) = [v_j]_{j<w},\qquad v_j = \chi_{L,P}(r[j]) \in\mathbb{B}^{\nu}. w = ∣ r ∣ , sig L , P ( r ) = [ v j ] j < w , v j = χ L , P ( r [ j ]) ∈ B ν . s w = 0 , s j = v j ⊕ s j + 1 ( 0 ≤ j < w ) , (28) s_w = 0,\qquad s_j = v_j \oplus s_{j+1}\ (0 \le j < w), \tag*{(28)} s w = 0 , s j = v j ⊕ s j + 1 ( 0 ≤ j < w ) , (28) s 0 = 0 ∧ ∀ j ≤ w . wt ( s j ) ≤ 1. (29) s_0 = 0\ \land\ \forall j \le w.\ \operatorname{wt}(s_j) \le1. \tag*{(29)} s 0 = 0 ∧ ∀ j ≤ w . wt ( s j ) ≤ 1. (29) Γ ⊢ HookBound L , P ( S ) ⟺ ∀ h < M . Γ ⊢ h o o k sig L , P ( r h ) ∧ DistinctInRange n ( r h ) . \Gamma\vdash\operatorname{HookBound}_{L,P}(S)\quad\Longleftrightarrow\quad\forall h < M.\ \Gamma\vdash_{\mathrm{hook}} \operatorname{sig}_{L,P}(r_h)\ \land\ \operatorname{DistinctInRange}_n(r_h). Γ ⊢ HookBound L , P ( S ) ⟺ ∀ h < M . Γ ⊢ hook sig L , P ( r h ) ∧ DistinctInRange n ( r h ) . Here DistinctInRange n ( [ ( P j ) q j ] j < w ) \operatorname{DistinctInRange}_n([(P_j)_{q_j}]_{j<w}) DistinctInRange n ([( P j ) q j ] j < w ) requires q j < n q_j < n q j < n for every j < w j < w j < w and q j ≠ q j ′ q_j \ne q_{j'} q j = q j ′ for j ≠ j ′ j \ne j' j = j ′ .
The following rules establish hook bounds from the sequence of cut signatures.
\frac{\Gamma\vdash_{\mathrm{hook}} []}{\Gamma\vdash_{\mathrm{hook}} \vec{v}}\ \textsc{Pair-Nil}
\qquad
\frac{\Gamma\vdash_C v = 0\qquad\Gamma\vdash_{\mathrm{hook}} \vec{v}}{\Gamma\vdash_{\mathrm{hook}} v :: \vec{v}}\ \textsc{Pair-Zero}
\frac{\Gamma\vdash_C v = v'\qquad\Gamma\vdash_C \operatorname{wt}(v') \le1\qquad\Gamma\vdash_{\mathrm{hook}} \vec{v}}{\Gamma\vdash_{\mathrm{hook}} v :: v' :: \vec{v}}\ \textsc{Pair-Step}
\frac{\Gamma\vdash_C s_0 = 0\qquad\Gamma\vdash_C \forall j \le w.\ \operatorname{wt}(s_j) \le1}{\Gamma\vdash_{\mathrm{hook}} [v_j]_{j<w}}\ \textsc{Hook-Check}
Completeness connects the two cut invariants to the distance bound in the rules below.
Complete L X , L Z : ∀ E ∈ P n . ∀ i , j < ν . Norm ( E ) ∧ χ L Z , Z ( E ) i = 0 ∧ χ L X , X ( E ) j = 0 ⇒ Gen ( E ) . (30) \operatorname{Complete}_{L_X,L_Z}:\quad\forall E \in\mathbb{P}^n.\ \forall i,j < \nu.\ \operatorname{Norm}(E)\ \land\ \chi_{L_Z,Z}(E)_i = 0\ \land\ \chi_{L_X,X}(E)_j = 0\ \Rightarrow\ \operatorname{Gen}(E). \tag*{(30)} Complete L X , L Z : ∀ E ∈ P n . ∀ i , j < ν . Norm ( E ) ∧ χ L Z , Z ( E ) i = 0 ∧ χ L X , X ( E ) j = 0 ⇒ Gen ( E ) . (30) I X : = wt ν ( χ L X , X ( E ) ) ≤ ℓ , I Z : = wt ν ( χ L Z , Z ( E ) ) ≤ ℓ . I_X := \operatorname{wt}_{\nu}(\chi_{L_X,X}(E)) \le\ell,\qquad I_Z := \operatorname{wt}_{\nu}(\chi_{L_Z,Z}(E)) \le\ell. I X := wt ν ( χ L X , X ( E )) ≤ ℓ , I Z := wt ν ( χ L Z , Z ( E )) ≤ ℓ . \frac{\Gamma\vdash\operatorname{HookBound}_{L,P}(S)}{\Gamma\mid S \vdash\Box(\operatorname{wt}_{\nu}(\chi_{L,P}(E)) \le\ell)}\ \textsc{Src-Cut}
\qquad
\frac{\Gamma\mid S \vdash\Box A\qquad\Gamma\mid S \vdash\Box A'}{\Gamma\mid S \vdash\Box(A \land A')}\ \textsc{Src-Conj}
\frac{\Gamma\mid S \vdash\Box A\qquad\Gamma,A \vdash_{C,f,n} A'}{\Gamma\mid S \vdash\Box A'}\ \textsc{Src-Conseq}
\frac{\Gamma\mid S \vdash\Box(I_Z \land I_X)\qquad\Gamma\vdash_C \operatorname{WellFormed}\qquad\Gamma\vdash_C \operatorname{Complete}_{L_X,L_Z}}{\Gamma\mid S \vdash\Box(\ell< \nu\Rightarrow\neg\operatorname{Logical}(E))}\ \textsc{Src-Dist}
The following soundness statement connects derivable invariants to reachable-state semantics.
Theorem A.3 (Checked source invariance).
∀ ρ ⊨ Γ . GenOK ρ ∧ WellFormedRound ( S ρ ) Γ ∣ S ⊢ □ A Γ ∣ S ⊨ □ A \frac{\forall\rho\models\Gamma.\ \operatorname{GenOK}_{\rho}\ \land\ \operatorname{WellFormedRound}(S_{\rho})\qquad\Gamma\mid S \vdash\Box A}{\Gamma\mid S \models\Box A} Γ ∣ S ⊨ □ A ∀ ρ ⊨ Γ. GenOK ρ ∧ WellFormedRound ( S ρ ) Γ ∣ S ⊢ □ A Here WellFormedRound ( S ρ ) \operatorname{WellFormedRound}(S_{\rho}) WellFormedRound ( S ρ ) requires DistinctInRange n ( r ) \operatorname{DistinctInRange}_n(r) DistinctInRange n ( r ) for every stabilizer r r r of the round.
QClifford syntax and execution
We define QClifford instructions and states, followed by their error-propagation and execution rules.
N ≥ n > 0 , q , u ∈ [ N ] , q ≠ u , β ∈ { ∣ 0 ⟩ , ∣ + ⟩ } , N \ge n > 0,\quad q,u \in[N],\quad q \ne u,\quad\beta\in\{\lvert0\rangle,\lvert+\rangle\}, N ≥ n > 0 , q , u ∈ [ N ] , q = u , β ∈ {∣ 0 ⟩ , ∣ + ⟩} ,
g : : = H [ q ] ∣ C N O T [ q , u ] ∣ q : = β ∣ M e a s Z ( q ) , i : : = gate ( g ) ∣ err ( q ) , c ˉ : : = ϵ ∣ i ; c ˉ , g ::= \mathrm{H}[q] \mid\mathrm{CNOT}[q,u] \mid q := \beta\mid\mathrm{Meas}_{Z}(q),\quad i ::= \operatorname{gate}(g) \mid\operatorname{err}(q),\quad\bar{c} ::= \epsilon\mid i\,;\,\bar{c}, g ::= H [ q ] ∣ CNOT [ q , u ] ∣ q := β ∣ Meas Z ( q ) , i ::= gate ( g ) ∣ err ( q ) , c ˉ ::= ϵ ∣ i ; c ˉ ,
Σ = ( E , ω , j r e c , ℓ ) ∈ P N × B N × N 2 , Σ c l e a n = ( I N , 0 , 0 , 0 ) , E r a w = E ↾ [ n ] , E ( q ) = X x q Z z q . \Sigma= (\mathcal{E},\omega,j_{\mathrm{rec}},\ell) \in\mathcal{P}^{N} \times\mathbb{B}^{N} \times\mathbb{N}^{2},\quad\Sigma_{\mathrm{clean}}=(I^{N},0,0,0),\quad E_{\mathrm{raw}}=\mathcal{E}\!\restriction_{[n]},\quad\mathcal{E}(q)=X^{x_q}Z^{z_q}. Σ = ( E , ω , j rec , ℓ ) ∈ P N × B N × N 2 , Σ clean = ( I N , 0 , 0 , 0 ) , E raw = E ↾ [ n ] , E ( q ) = X x q Z z q .
The state updates below track Pauli errors and measurement records through each instruction.
prop H [ q ] ( Σ ) = Σ [ x q ↦ z q , z q ↦ x q ] , \operatorname{prop}_{\mathrm{H}[q]}(\Sigma)=\Sigma[x_q\mapsto z_q,z_q\mapsto x_q], prop H [ q ] ( Σ ) = Σ [ x q ↦ z q , z q ↦ x q ] ,
prop C N O T [ q , u ] ( Σ ) = Σ [ x u ↦ x u ⊕ x q , z q ↦ z q ⊕ z u ] , \operatorname{prop}_{\mathrm{CNOT}[q,u]}(\Sigma)=\Sigma[x_u\mapsto x_u\oplus x_q,z_q\mapsto z_q\oplus z_u], prop CNOT [ q , u ] ( Σ ) = Σ [ x u ↦ x u ⊕ x q , z q ↦ z q ⊕ z u ] ,
prop q : = β ( Σ ) = Σ [ x q ↦ 0 , z q ↦ 0 ] ( β ∈ { ∣ 0 ⟩ , ∣ + ⟩ } ) , \operatorname{prop}_{q:=\beta}(\Sigma)=\Sigma[x_q\mapsto0,z_q\mapsto0]\quad(\beta\in\{\lvert0\rangle,\lvert+\rangle\}), prop q := β ( Σ ) = Σ [ x q ↦ 0 , z q ↦ 0 ] ( β ∈ {∣ 0 ⟩ , ∣ + ⟩}) ,
prop M e a s Z ( q ) ( Σ ) = Σ [ ω ↦ ω [ j r e c ↦ x q ] , j r e c ↦ j r e c + 1 ] , \operatorname{prop}_{\mathrm{Meas}_{Z}(q)}(\Sigma)=\Sigma[\omega\mapsto\omega[j_{\mathrm{rec}}\mapsto x_q],j_{\mathrm{rec}}\mapsto j_{\mathrm{rec}}+1], prop Meas Z ( q ) ( Σ ) = Σ [ ω ↦ ω [ j rec ↦ x q ] , j rec ↦ j rec + 1 ] ,
inj q , X a Z b ( Σ ) = Σ [ x q ↦ x q ⊕ a , z q ↦ z q ⊕ b , ℓ ↦ ℓ + 1 ] ( ( a , b ) ≠ ( 0 , 0 ) ) . (31) \operatorname{inj}_{q,X^{a}Z^{b}}(\Sigma)=\Sigma[x_q\mapsto x_q\oplus a,z_q\mapsto z_q\oplus b,\ell\mapsto\ell+1]\quad((a,b)\ne(0,0)). \tag*{(31)} inj q , X a Z b ( Σ ) = Σ [ x q ↦ x q ⊕ a , z q ↦ z q ⊕ b , ℓ ↦ ℓ + 1 ] (( a , b ) = ( 0 , 0 )) . (31)
The execution rules compose these updates, allowing each error instruction to inject one Pauli error or none.
Σ → gate ( g ) prop g ( Σ ) Σ → err ( q ) Σ P ∈ { X , Y , Z } Σ → err ( q ) inj q , P ( Σ ) ⟨ ϵ , Σ ⟩ ⇓ Σ \Sigma\xrightarrow{\operatorname{gate}(g)} \operatorname{prop}_{g}(\Sigma)
\qquad
\Sigma\xrightarrow{\operatorname{err}(q)} \Sigma
\qquad
\frac{P\in\{X,Y,Z\}}{\Sigma\xrightarrow{\operatorname{err}(q)} \operatorname{inj}_{q,P}(\Sigma)}
\qquad
\langle\epsilon,\Sigma\rangle\Downarrow\Sigma Σ gate ( g ) prop g ( Σ ) Σ err ( q ) Σ Σ err ( q ) inj q , P ( Σ ) P ∈ { X , Y , Z } ⟨ ϵ , Σ ⟩ ⇓ Σ
Σ → i Σ 1 ⟨ c ˉ , Σ 1 ⟩ ⇓ Σ 2 ⟨ i ; c ˉ , Σ ⟩ ⇓ Σ 2 \frac{\Sigma\xrightarrow{i}\Sigma_{1}\qquad\langle\bar{c},\Sigma_{1}\rangle\Downarrow\Sigma_{2}}{\langle i\,;\,\bar{c},\Sigma\rangle\Downarrow\Sigma_{2}} ⟨ i ; c ˉ , Σ ⟩ ⇓ Σ 2 Σ i Σ 1 ⟨ c ˉ , Σ 1 ⟩ ⇓ Σ 2
QClifford Hoare logic
The following definitions give the meaning of a QClifford Hoare triple and the rules for deriving it.
φ , ψ , θ : State Q C → B , ( ψ ∘ F ) ( Σ ) = ψ ( F ( Σ ) ) , \varphi,\psi,\theta:\operatorname{State}_{\mathrm{QC}}\to\mathbb{B},\quad(\psi\circ F)(\Sigma)=\psi(F(\Sigma)), φ , ψ , θ : State QC → B , ( ψ ∘ F ) ( Σ ) = ψ ( F ( Σ )) ,
⊨ { φ } c ˉ { ψ } ⟺ ∀ Σ , Σ ′ . φ ( Σ ) ∧ ⟨ c ˉ , Σ ⟩ ⇓ Σ ′ ⇒ ψ ( Σ ′ ) . \models\{\varphi\}\bar{c}\{\psi\}\Longleftrightarrow\forall\Sigma,\Sigma'.\ \varphi(\Sigma)\land\langle\bar{c},\Sigma\rangle\Downarrow\Sigma'\Rightarrow\psi(\Sigma'). ⊨ { φ } c ˉ { ψ } ⟺ ∀Σ , Σ ′ . φ ( Σ ) ∧ ⟨ c ˉ , Σ ⟩ ⇓ Σ ′ ⇒ ψ ( Σ ′ ) .
\vdash\{\varphi\}\epsilon\{\varphi\}\quad\textsc{H-Skip}
\vdash\{\psi\circ\operatorname{prop}_{g}\}\operatorname{gate}(g)\{\psi\}\quad\textsc{H-Gate}
\vdash\left\{\psi\land\bigwedge_{P\in\{X,Y,Z\}}\psi\circ\operatorname{inj}_{q,P}\right\}\operatorname{err}(q)\{\psi\}\quad\textsc{H-Err}
\frac{\vdash\{\varphi\}\bar{c}\{\theta\}\qquad\vdash\{\theta\}\bar{c}'\{\psi\}}{\vdash\{\varphi\}\bar{c}\,;\,\bar{c}'\{\psi\}}\quad\textsc{H-Seq}
\frac{\vdash\{\varphi_{1}\}\bar{c}\{\psi_{1}\}\qquad\vdash\{\varphi_{2}\}\bar{c}\{\psi_{2}\}}{\vdash\{\varphi_{1}\land\varphi_{2}\}\bar{c}\{\psi_{1}\land\psi_{2}\}}\quad\textsc{H-Conj}
\frac{\varphi\Rightarrow\varphi'\qquad\vdash\{\varphi'\}\bar{c}\{\psi'\}\qquad\psi'\Rightarrow\psi}{\vdash\{\varphi\}\bar{c}\{\psi\}}\quad\textsc{H-Conseq}
⊢ F { φ } c ˉ { ψ } ≡ ⊢ { φ } c ˉ { ψ } . \vdash_{F}\{\varphi\}\bar{c}\{\psi\}\equiv\vdash\{\varphi\}\bar{c}\{\psi\}. ⊢ F { φ } c ˉ { ψ } ≡⊢ { φ } c ˉ { ψ } .
The repetition rule assembles a finite sequence of indexed circuit blocks.
\frac{\Gamma\vdash k\in\mathbb{N}\qquad\Gamma,i\in\mathbb{N},\,i<k\vdash_{F}\{\mathcal{I}(i)\}c(i)\{\mathcal{I}(i+1)\}}{\Gamma\vdash_{F}\{\mathcal{I}(0)\}\underset{i<k}{\operatorname{concat}}\,c(i)\{\mathcal{I}(k)\}}\quad\textsc{H-Repeat} \tag*{(32)}
Circuit-level distance
We define circuit-level distance using the backend’s record predicate and, when required, detector silence.
Definition A.4 (Circuit-level code distance).
K = ( C , L e g a l , n , m , f , d , N , c ˉ K , R e c o r d O K K ) , J = ( J a ) a < ν , J a ⊆ [ M K ] , K = (C, \mathit{Legal}, n, m, f, d, N, \bar{c}_K, \mathit{RecordOK}_K), \qquad\mathcal{J} = (J_a)_{a<\nu}, \qquad J_a \subseteq[M_K], K = ( C , Legal , n , m , f , d , N , c ˉ K , RecordOK K ) , J = ( J a ) a < ν , J a ⊆ [ M K ] ,
where L e g a l ( d ) \mathit{Legal}(d) Legal ( d ) holds, N ≥ n ( d ) N \ge n(d) N ≥ n ( d ) , and M K M_K M K counts the Meas Z \operatorname{Meas}_Z Meas Z instructions of c ˉ K \bar{c}_K c ˉ K . The predicate L o g i c a l \mathit{Logical} Logical and the restriction E r a w E_{\mathrm{raw}} E raw are taken at n ( d ) n(d) n ( d ) , m ( d ) m(d) m ( d ) and the stabilizers T k T_k T k of C ( d , k ) C(d,k) C ( d , k ) .
S i l e n t J ( ω ) : = ∀ a < ν . ⋀ j ∈ J a ω ( j ) = 0 , A c c e p t K , J ( Σ ) : = R e c o r d O K K ( ω ) ∧ S i l e n t J ( ω ) . \mathit{Silent}_{\mathcal{J}}(\omega) := \forall a < \nu.\ \bigwedge_{j \in J_a} \omega(j) = 0, \qquad\mathit{Accept}_{K,\mathcal{J}}(\Sigma) := \mathit{RecordOK}_K(\omega) \land\mathit{Silent}_{\mathcal{J}}(\omega). Silent J ( ω ) := ∀ a < ν . ⋀ j ∈ J a ω ( j ) = 0 , Accept K , J ( Σ ) := RecordOK K ( ω ) ∧ Silent J ( ω ) .
d K , J c i r c : = min { ℓ ( Σ ′ ) : ⟨ c ˉ K , Σ c l e a n ⟩ ⇓ Σ ′ , A c c e p t K , J ( Σ ′ ) ∧ L o g i c a l ( E r a w ′ ) } , min ∅ = ∞ . (33) d^{\mathrm{circ}}_{K,\mathcal{J}} := \min\{\ell(\Sigma') : \langle\bar{c}_K,\Sigma_{\mathrm{clean}}\rangle\Downarrow\Sigma',\ \mathit{Accept}_{K,\mathcal{J}}(\Sigma') \land\mathit{Logical}(E'_{\mathrm{raw}})\}, \qquad\min\varnothing= \infty. \tag*{(33)} d K , J circ := min { ℓ ( Σ ′ ) : ⟨ c ˉ K , Σ clean ⟩ ⇓ Σ ′ , Accept K , J ( Σ ′ ) ∧ Logical ( E raw ′ )} , min ∅ = ∞. (33) d K c i r c : = min { ℓ ( Σ ′ ) : ⟨ c ˉ K , Σ c l e a n ⟩ ⇓ Σ ′ , R e c o r d O K K ( ω ′ ) ∧ L o g i c a l ( E r a w ′ ) } , d^{\mathrm{circ}}_K := \min\{\ell(\Sigma') : \langle\bar{c}_K,\Sigma_{\mathrm{clean}}\rangle\Downarrow\Sigma',\ \mathit{RecordOK}_K(\omega') \land\mathit{Logical}(E'_{\mathrm{raw}})\}, d K circ := min { ℓ ( Σ ′ ) : ⟨ c ˉ K , Σ clean ⟩ ⇓ Σ ′ , RecordOK K ( ω ′ ) ∧ Logical ( E raw ′ )} , A c c e p t d = A c c e p t K d , J d , L o g F a i l d = L o g i c a l ( E r a w ) . \mathit{Accept}_d = \mathit{Accept}_{K_d,\mathcal{J}_d}, \qquad\mathit{LogFail}_d = \mathit{Logical}(E_{\mathrm{raw}}). Accept d = Accept K d , J d , LogFail d = Logical ( E raw ) .
Surface code proof derivations
The following derivations assemble the Surface code cut invariant and its compiled circuit-distance guarantee.
Γ s u r f = { s ≥ 1 , d = 2 s + 1 } , n ( d ) = d 2 , m ( d ) = d 2 − 1 , f ( d ) = 1 , R ( d ) = d , B ( d ) = d − 1. \Gamma_{\mathrm{surf}} = \{s \ge1, d = 2s + 1\}, \qquad n(d) = d^2, \qquad m(d) = d^2 - 1, \qquad f(d) = 1, \qquad R(d) = d, \qquad B(d) = d - 1. Γ surf = { s ≥ 1 , d = 2 s + 1 } , n ( d ) = d 2 , m ( d ) = d 2 − 1 , f ( d ) = 1 , R ( d ) = d , B ( d ) = d − 1.
G : S d = Generate [ C s u r f ] ( d ; d , d − 1 ) , c ˉ d = Compile S t d [ S d ] = concat h < m ( d ) R ( d ) c ˉ d , h . \mathcal{G} : S_d = \operatorname{Generate}_{\lbrack C_{\mathrm{surf}}\rbrack}(d; d, d-1), \qquad\bar{c}_d = \operatorname{Compile}_{\mathrm{Std}}[S_d] = \underset{h<m(d)R(d)}{\operatorname{concat}}\ \bar{c}_{d,h}. G : S d = Generate [ C surf ] ( d ; d , d − 1 ) , c ˉ d = Compile Std [ S d ] = h < m ( d ) R ( d ) concat c ˉ d , h .
P z : Γ s u r f ⊢ HookBound L z , Z ( S d ) , P x : Γ s u r f ⊢ HookBound L x , X ( S d ) , P_z : \Gamma_{\mathrm{surf}} \vdash\operatorname{HookBound}_{L_z,Z}(S_d), \qquad P_x : \Gamma_{\mathrm{surf}} \vdash\operatorname{HookBound}_{L_x,X}(S_d), P z : Γ surf ⊢ HookBound L z , Z ( S d ) , P x : Γ surf ⊢ HookBound L x , X ( S d ) ,
V : Γ s u r f ⊢ C WellFormed , W : Γ s u r f ⊢ C Complete L x , L z . V : \Gamma_{\mathrm{surf}} \vdash_C \operatorname{WellFormed}, \qquad W : \Gamma_{\mathrm{surf}} \vdash_C \operatorname{Complete}_{L_x,L_z}. V : Γ surf ⊢ C WellFormed , W : Γ surf ⊢ C Complete L x , L z .
First, the hook proofs establish the QStab cut invariant by the source rules of Figure 7 .
P z : Γ s u r f ⊢ HookBound L z , Z ( S d ) Γ s u r f ∣ S d ⊢ □ ( wt d ( χ L z , Z ( E ) ) ≤ ℓ ) \begin{aligned}
P_z &: \Gamma_{\mathrm{surf}} \vdash\operatorname{HookBound}_{L_z,Z}(S_d) \\
&\qquad\Gamma_{\mathrm{surf}} \mid S_d \vdash\Box\left(\operatorname{wt}_d(\chi_{L_z,Z}(E)) \le\ell\right)
\end{aligned} P z : Γ surf ⊢ HookBound L z , Z ( S d ) Γ surf ∣ S d ⊢ □ ( wt d ( χ L z , Z ( E )) ≤ ℓ )
P x : Γ s u r f ⊢ HookBound L x , X ( S d ) Γ s u r f ∣ S d ⊢ □ ( wt d ( χ L x , X ( E ) ) ≤ ℓ ) \begin{aligned}
P_x &: \Gamma_{\mathrm{surf}} \vdash\operatorname{HookBound}_{L_x,X}(S_d) \\
&\qquad\Gamma_{\mathrm{surf}} \mid S_d \vdash\Box\left(\operatorname{wt}_d(\chi_{L_x,X}(E)) \le\ell\right)
\end{aligned} P x : Γ surf ⊢ HookBound L x , X ( S d ) Γ surf ∣ S d ⊢ □ ( wt d ( χ L x , X ( E )) ≤ ℓ )
D i n v : Γ s u r f ∣ S d ⊢ □ I d ( E , ℓ ) . (34) D_{\mathrm{inv}} : \Gamma_{\mathrm{surf}} \mid S_d \vdash\Box I_d(E,\ell). \tag*{(34)} D inv : Γ surf ∣ S d ⊢ □ I d ( E , ℓ ) . (34)
Src-Cut is sound by induction on execution: I d ( I n ( d ) , 0 ) I_d(I^{n(d)},0) I d ( I n ( d ) , 0 ) holds because both cut signatures are zero, and Equation (15) shows that every step γ → S d γ ′ \gamma\mathrel{\to_{S_d}} \gamma' γ → S d γ ′ preserves I d I_d I d . Src-Dist then adds well-formedness and completeness.
D = Src-Dist ( D i n v , V , W ) : Γ s u r f ∣ S d ⊢ □ ( ℓ < d ⇒ ¬ L o g i c a l ( E ) ) . (35) \mathcal{D} = \operatorname{Src-Dist}(D_{\mathrm{inv}},V,W) : \Gamma_{\mathrm{surf}} \mid S_d \vdash\Box\left(\ell< d \Rightarrow\neg\mathit{Logical}(E)\right). \tag*{(35)} D = Src-Dist ( D inv , V , W ) : Γ surf ∣ S d ⊢ □ ( ℓ < d ⇒ ¬ Logical ( E ) ) . (35)
Second, the Standard Scheme propagation lemmas carry the same hook proofs to every compiled block. § 5.2 derives the first block at d = 3 d = 3 d = 3 ; the supplement’s pending-contribution argument proves the triple for an arbitrary ordered stabilizer whose suffix signatures satisfy the hook bound. The generation proof G \mathcal{G} G supplies the ordered operands of block h h h .
G P z P x Γ s u r f , h < m ( d ) R ( d ) ⊢ F { Φ d } c ˉ d , h { Φ d } . (36) \frac{\mathcal{G}\qquad P_z\qquad P_x}{\Gamma_{\mathrm{surf}},\ h < m(d)R(d) \vdash_F \{\Phi_d\}\ \bar{c}_{d,h}\ \{\Phi_d\}}. \tag*{(36)} Γ surf , h < m ( d ) R ( d ) ⊢ F { Φ d } c ˉ d , h { Φ d } G P z P x . (36)
The following induction composes the compiled syndrome-extraction blocks of Equation (36) by H-Repeat.
Φ d ( Σ c l e a n ( d ) ) Γ s u r f , h < m ( d ) R ( d ) ⊢ F { Φ d } c ˉ d , h { Φ d } Γ s u r f ⊢ F { Σ = Σ c l e a n ( d ) } c ˉ d { Φ d } . (37) \frac{\Phi_d(\Sigma_{\mathrm{clean}}(d)) \qquad\Gamma_{\mathrm{surf}},\ h < m(d)R(d) \vdash_F \{\Phi_d\}\ \bar{c}_{d,h}\ \{\Phi_d\}}{\Gamma_{\mathrm{surf}} \vdash_F \{\Sigma= \Sigma_{\mathrm{clean}}(d)\}\ \bar{c}_d\ \{\Phi_d\}}. \tag*{(37)} Γ surf ⊢ F { Σ = Σ clean ( d )} c ˉ d { Φ d } Φ d ( Σ clean ( d )) Γ surf , h < m ( d ) R ( d ) ⊢ F { Φ d } c ˉ d , h { Φ d } . (37)
Finally, cut completeness turns the compiled invariant into the circuit-distance guarantee.
Φ d ∧ Logical ( E r a w ) ⟹ d = wt ( χ x ( E r a w ) ) ≤ ℓ ∨ d = wt ( χ z ( E r a w ) ) ≤ ℓ ⟹ d ≤ ℓ (38) \Phi_d \land\operatorname{Logical}(E_{\mathrm{raw}}) \Longrightarrow d = \operatorname{wt}(\chi_x(E_{\mathrm{raw}})) \le\ell\lor d = \operatorname{wt}(\chi_z(E_{\mathrm{raw}})) \le\ell\Longrightarrow d \le\ell \tag*{(38)} Φ d ∧ Logical ( E raw ) ⟹ d = wt ( χ x ( E raw )) ≤ ℓ ∨ d = wt ( χ z ( E raw )) ≤ ℓ ⟹ d ≤ ℓ (38)
This implication is the target reading of D \mathcal{D} D : it reuses V V V and W W W and gives the target certificate D ′ \mathcal{D}' D ′ of Theorem 5.1 , which proves A d A_d A d at budget d − 1 d-1 d − 1 . H-Conseq weakens the postcondition.
Γ s u r f ⊢ F { Σ = Σ c l e a n ( d ) } c ˉ d { Φ d } V : Γ s u r f ⊢ C W e l l F o r m e d W : Γ s u r f ⊢ C C o m p l e t e L x , L z Γ s u r f ⊢ F { Σ = Σ c l e a n ( d ) } c ˉ d { Φ d } ⏟ initialization and induction: Equation (38) H S t d : Γ s u r f ⊢ F { Σ = Σ c l e a n ( d ) } Compile S t d [ Generate [ C s u r f ] ( d ; d , d − 1 ) ] { Accept d ( Σ ) ∧ LogFail d ( Σ ) ⇒ d ≤ ℓ ( Σ ) } (39) \begin{aligned}
&\Gamma_{\mathrm{surf}} \vdash_F \{\Sigma= \Sigma_{\mathrm{clean}}(d)\}\,\bar{c}_d\,\{\Phi_d\}
&& V : \Gamma_{\mathrm{surf}} \vdash_C \mathrm{WellFormed}
&& W : \Gamma_{\mathrm{surf}} \vdash_C \mathrm{Complete}_{L_x,L_z} \\
&\hspace{3em}\underbrace{\phantom{\Gamma_{\mathrm{surf}} \vdash_F \{\Sigma= \Sigma_{\mathrm{clean}}(d)\}\,\bar{c}_d\,\{\Phi_d\}}}_{\text{initialization and induction: Equation (38)}}\\
&\mathcal{H}_{\mathrm{Std}} :
\Gamma_{\mathrm{surf}} \vdash_F \{\Sigma= \Sigma_{\mathrm{clean}}(d)\}\,
\operatorname{Compile}_{\mathrm{Std}}\!\left[\operatorname{Generate}\!\left[C_{\mathrm{surf}}\right](d;d,d-1)\right]\,
\{\operatorname{Accept}_d(\Sigma)\land\operatorname{LogFail}_d(\Sigma)\Rightarrow d\le\ell(\Sigma)\} \tag*{(39)}
\end{aligned} Γ surf ⊢ F { Σ = Σ clean ( d )} c ˉ d { Φ d } initialization and induction: Equation (38) Γ surf ⊢ F { Σ = Σ clean ( d )} c ˉ d { Φ d } H Std : Γ surf ⊢ F { Σ = Σ clean ( d )} Compile Std [ Generate [ C surf ] ( d ; d , d − 1 ) ] { Accept d ( Σ ) ∧ LogFail d ( Σ ) ⇒ d ≤ ℓ ( Σ )} V : Γ surf ⊢ C WellFormed W : Γ surf ⊢ C Complete L x , L z (39)
C Code-family geometries
What must we prove again when the code family has a different geometry or more logical qubits? Figure 10 shows how the Surface code argument extends. Panel (a) retains the columns and rows of Figure 1 (a). Panel (b) places the unrotated Surface code’s data qubits on lattice edges, with X stars and Z plaquettes [17 ] . Its cuts use rows and columns of vertical-edge qubits (block A A A ); horizontal-edge qubits (block B B B ) belong to no counted cut. Panel (c) unwraps the Toric code’s two periodic edge blocks to show four collections. Panel (d) replaces complete rows and columns by seed-selected subsets, giving twelve algebraic cut collections for LP code. Each of these four families supplies a new proof that every logical residual crosses enough cuts in some collection, and each ordered extraction program must establish its one-error bounds. The invariant induction and structural certificate-translation rules are reused. Under the declared contracts, unrotated Surface code and Toric code attain d d d , and Cartesian LP code attains 4 t 4t 4 t . Toric code uses four cut collections for two logical qubits, and Cartesian LP code uses twelve for eighteen. Code algebra identifies logical residuals, while extraction proofs bound error effects.
What is a cut in Cartesian LP code? As in Figure 1 (a), a cut is a Pauli string used to probe an error’s parity; its support may contain disconnected qubits. In Figure 10 (d), write ( b , i , j ) (b,i,j) ( b , i , j ) for a qubit’s block, row and column. At t = 1 t=1 t = 1 , the first seed s 0 = 1001011 s^0=1001011 s 0 = 1001011 selects rows 0, 3, 5, 6. In column two of block zero this gives κ 2 = Z 0 , 0 , 2 Z 0 , 3 , 2 Z 0 , 5 , 2 Z 0 , 6 , 2 \kappa_2=Z_{0,0,2}Z_{0,3,2}Z_{0,5,2}Z_{0,6,2} κ 2 = Z 0 , 0 , 2 Z 0 , 3 , 2 Z 0 , 5 , 2 Z 0 , 6 , 2 . An X error at ( 0 , 0 , 2 ) (0,0,2) ( 0 , 0 , 2 ) crosses this cut; adding X at ( 0 , 3 , 2 ) (0,3,2) ( 0 , 3 , 2 ) cancels its parity. Varying the column gives seven cuts in one collection. The highlighted X check meets κ 2 \kappa_2 κ 2 twice. Its six slots contribute ( e 2 , 0 , e 2 , 0 , 0 , 0 ) (e_2,0,e_2,0,0,0) ( e 2 , 0 , e 2 , 0 , 0 , 0 ) , where e 2 e_2 e 2 marks only cut κ 2 \kappa_2 κ 2 ; every suffix therefore crosses at most one cut in this collection. Three seeds (reversed for the X probes), two blocks and two probe Paulis give twelve collections. At general t t t , each collection has 7 t 7t 7 t cuts. A separate code-algebra proof shows that every logical residual crosses at least 4 t 4t 4 t cuts in some collection; this is the threshold used with the one-error bound.
How does reduced weight establish the color-code bound? Panel (e) uses reduced weight in place of a cut collection. For this self-dual, one-logical-qubit family, any two nontrivial pure-X logical supports have odd overlap; the same holds for pure-Z supports. A disjoint collection of centralizing probes therefore contains at most one nontrivial logical probe. To obtain a bound that scales with d d d , we minimize error weight over equivalent representatives modulo stabilizers [6 , 13 ] . On the displayed face, the five-qubit hook H = Z 1 Z 2 Z 3 Z 4 Z 5 H=Z_1Z_2Z_3Z_4Z_5 H = Z 1 Z 2 Z 3 Z 4 Z 5 satisfies H ( Z 0 Z 1 Z 2 Z 3 Z 4 Z 5 ) = Z 0 H(Z_0Z_1Z_2Z_3Z_4Z_5)=Z_0 H ( Z 0 Z 1 Z 2 Z 3 Z 4 Z 5 ) = Z 0 ; its reduced weight is at most one. More generally, a hook on s s s qubits of a weight-w w w face has reduced weight at most min ( s , w − s ) ≤ 3 \min(s,w-s)\leq3 min ( s , w − s ) ≤ 3 , since w ≤ 6 w\leq6 w ≤ 6 . Thus ℓ \ell ℓ injected errors have reduced weight at most 3 ℓ 3\ell 3 ℓ , whereas a logical residual has reduced weight at least d d d . This proves the lower bound ⌊ d / 3 ⌋ \lfloor d/3\rfloor ⌊ d /3 ⌋ under the declared contract. The purple boundary shows a logical operator’s support.
Detailed evaluation results
Timings average three completed measurements; {sup}‡ averages two, and {sup}† reports one.
Each single-wire Pauli injection costs one error (§ 2.1 ). Serial stabilizer measurements use fresh ancilla qubits and d d d rounds for families (t t t for LP codes), or one pass with zero readout flips for finite cases. Standard Scheme and Flag Scheme families admit all records. For all native family certificates, the Shor Scheme requires zero edge flips and zero XOR in each cat-readout group, and the Knill Scheme requires zero resource and Bell flips. These are the complete benchmark predicates, stronger than the Surface code correction-erasing conditions in § 5.3 . The Toric code also has a separate formal exactness theorem admitting all records in every scheme. These conditions constrain the record of relative readout flips.
Reading the table. We use the standard notation [ [ n , k , d ] ] [[n,k,d]] [[ n , k , d ]] for a code with n n n data qubits, k k k logical qubits and distance d d d [14 , 18 , 27 ] . HGP denotes a hypergraph-product construction. Rotated Surface and triangular color code families use odd d ≥ 3 d \ge3 d ≥ 3 , unrotated Surface code uses d ≥ 2 d \ge2 d ≥ 2 , Toric code uses d ≥ 3 d \ge3 d ≥ 3 , and Cartesian LP code uses t ≥ 1 t \ge1 t ≥ 1 . Table 2 reports d K c i r c d_{K}^{\mathrm{circ}} d K circ from Definition A.4 . Equality in the detector-silent setting additionally requires a matching silent witness. The two Surface code rows use the canonical formal programs for their four-scheme equalities. The printed rotated Surface code order additionally has the Standard Scheme equality in § 5.3 . Their timings check native lower certificates. The family benchmarks check symbolic certificates. The interleaved Shor experiment translates a supplied source certificate using the supported structural rules, while the finite target benchmarks check supplied target certificates directly. The native Surface package writes the same ordered schedule with the recursive family body of the supplement and fuel s + 1 s+1 s + 1 . The timed stages are lower-proof checking, supplied upper-witness checking for finite cases, and circuit binding for finite targets. Circuit/proof emission, verification-condition generation, witness search and Lean builds are performed separately.
Combining the images. After the checker of § 6 recomputes the single-injection images, backward-flow exactness and linearity combine the images by XOR, including readout cancellations, to establish the assertion for every execution within the declared budget. The intermediate Hoare assertions in Figure 8 explain this reasoning. The emitted finite certificate stores image evidence and structural proof nodes. Its expanded circuit and image table grow with d d d .
Comparison protocol. Each search instance is built in five steps. First, our tool instantiates the family’s symbolic source program at distance d d d , giving the ordered QStab program; this is the same source file that the timed family certificate is checked against. For the triangular color code, the ordered stabilizers come from a generator that agrees with the CodeML definition at every tested size. Second, our Standard Scheme compiler emits the QClifford circuit. Third, we translate the QClifford gate list gate by gate into Stim [11 ] operations and let Stim propagate every pre-operation X, Y and Z injection on every operand to the end of the circuit, which gives the final data error and the readout flips of each single injection. Fourth, each injection is summarized by the syndrome of its final data error against the code’s stabilizers and by its parities against a complete basis of logical operators; readout flips impose no constraint, matching the unrestricted readouts of the Standard Scheme contract. Identical summaries are merged, and the summaries form a check matrix and a logical matrix. Fifth, the published encoder of codeDistance [35 ] turns the question of the fewest injections with zero syndrome and nonzero logical parity into a MaxSAT problem, which two PySAT algorithms solve on Glucose 4: linear search (LSU), which is the package default, and core-guided RC2. The optimum is mapped back to concrete injections and replayed in Stim as one combined execution, which must have exactly that many injections, zero syndrome and a nontrivial logical residual. At the smallest instance of each family, every Stim single-injection image also equals the image computed by our checker. The Standard circuits use d d d rounds for unrotated and rotated Surface codes and for the triangular color code, and t = d / 4 t = d/4 t = d /4 rounds for Cartesian LP codes. Total search time includes process startup, program instantiation, compilation, propagation, logical-basis construction, encoding, search and witness replay. Each completed optimum is replayed as a combined execution. Every instance runs once, in a fresh single-threaded process with a 7,200 s limit, and each series ends at its first unsolved instance. The limit exceeds every family-proof total. The searches ran as high-priority processes on the evaluation host, with up to eight in parallel. The first three family-proof totals in Figure 9 sum certificate compilation and verification: 27.3 s, 219.5 s and 3715.8 s, respectively. The color-code panel shows the table’s verification-only time of 5511 s. Table 2 reports verification alone. The reported means use three completed runs for each family except Cartesian LP, which uses two completed runs; its third attempt exhausted memory. The triangular color-code timing is one run.
LSU completes unrotated Surface up to d = 11 d = 11 d = 11 and times out at d = 13 d = 13 d = 13 ; rotated Surface up to d = 15 d = 15 d = 15 and times out at d = 17 d = 17 d = 17 ; Cartesian LP up to d = 4 d = 4 d = 4 and times out at d = 8 d = 8 d = 8 ; triangular color up to d = 17 d = 17 d = 17 and times out at d = 19 d = 19 d = 19 . RC2 completes unrotated Surface up to d = 11 d = 11 d = 11 and times out at d = 13 d = 13 d = 13 ; rotated Surface up to d = 13 d = 13 d = 13 and times out at d = 17 d = 17 d = 17 ; Cartesian LP up to d = 4 d = 4 d = 4 and times out at d = 8 d = 8 d = 8 ; triangular color up to d = 15 d = 15 d = 15 and times out at d = 17 d = 17 d = 17 . Every completed search for the Surface and LP families returns distance d d d . For the triangular color code the searches return 2, 3, 4, 5, 6, 7, 8, 9 at d = 3 , 5 , 7 , 9 , 11 , 13 , 15 , 17 d = 3, 5, 7, 9, 11, 13, 15, 17 d = 3 , 5 , 7 , 9 , 11 , 13 , 15 , 17 , that is ( d + 1 ) / 2 (d + 1)/2 ( d + 1 ) /2 , the exact circuit-level distance of this Standard schedule; it lies above the certified family lower bound ⌈ d / 3 ⌉ \lceil d/3 \rceil ⌈ d /3 ⌉ . Both configurations agree on every instance that both complete. The RC2 search for rotated Surface d = 15 d = 15 d = 15 was stopped unsolved after 4518 s, before the limit. LSU is the faster configuration on the larger instances, and Table 3 lists every measurement.
Table 3. Wall time in seconds of every exact-distance search in Figure 9 . A dash marks an instance that was not run because its series had ended; {sup}*stopped unsolved before the 7,200 s limit.