betaFeedback

WorksComputer Science

Parametric Proof-Carrying Compilation for Quantum Error-Correction

Abstract

We present PC-QEC, a proof-carrying compilation framework for quantum error correction parameterized by both code distance and syndrome-extraction scheme. It covers all four schemes—Standard, Flag, Shor and Knill—with circuit-level distance guarantees for every legal code distance in each proved family under the declared error and readout contracts. The circuit-level model permits single-wire Pauli errors at every operation's qubit operands, capturing data errors, readout errors and ancilla errors that propagate into multi-qubit hook errors. For each family and scheme, supplied code-algebra and invariant proofs combine with proved scheme-specific propagation lemmas into a finite symbolic certificate whose size is independent of code distance. We demonstrate family-wide guarantees for five code families across all four schemes. For rotated Surface code, one Standard Scheme certificate proves a distance lower bound dd for every odd d≥3d\ge3 and checks in 214,s on average. Lean 4 mechanizes the metatheory and exact circuit-level distances for canonical rotated Surface, unrotated Surface and Toric code families.

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 dd 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 dd as input and uses it to set a zero-failure cutoff at ⌊(d−1)/2⌋\lfloor(d-1)/2\rfloor 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 dcirc≥dd^{\mathrm{circ}} \ge 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 dd changes the qubits, measurements and emitted gates. A proof for d=3d=3, for example, establishes only that instance, while repeating the argument gate by gate produces a proof that grows with dd. 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 dd 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‘)⇒dcirc≥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)}

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).

Framework of PC-QEC, showing (a) Logical Z error, (b) Hook from one error, (c) Circuit compiled with the Standard Scheme, (d) Circuit compiled with the Flag Scheme, and (e) PC-QEC pipeline.

Figure 1. Framework of PC-QEC. (a) Logical Z error: χX(Z3Z4Z5)=(1,1,1)\chi_X(Z_3Z_4Z_5)=(1,1,1), three cuts. (b) Hook from one error: χX(Z3Z1Z4)=(1,0,0)\chi_X(Z_3Z_1Z_4)=(1,0,0), one cut; parities cancel. QStab S3S_3: three rounds, QS-Hook: (E,ℓ)=(I,0)→(Z3Z1Z4,1)(E,\ell)=(I,0)\to(Z_3Z_1Z_4,1), G0=0G_0=0. (c) Circuit compiled with the Standard Scheme; hook error Z3Z_3, Xa:(I9,1)X_a:(I^9,1), Ya:(Z3Z1Z4,1)Y_a:(Z_3Z_1Z_4,1), Za:(Z3Z1Z4,0)Z_a:(Z_3Z_1Z_4,0). (d) Circuit compiled with the Flag Scheme; hook error Z3Z_3, Xa:(I9,1,0)X_a:(I^9,1,0), Ya:(Z3Z1Z4,1,1)Y_a:(Z_3Z_1Z_4,1,1), Za:(Z3Z1Z4,0,1)Z_a:(Z_3Z_1Z_4,0,1). XYZXYZ each site: I,X,Y,ZI,X,Y,Z. Red path: selected ZaZ_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): stabilizer; t↦P[q]t\mapsto P[q]; Code algebra; VdV_d: Well formed; WdW_d: Complete; Evaluate stabilizers at distance dd; Supply cut bounds for hook errors; QStab § 4; SdS_d: RR 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}; Gates and injection sites; Target proof; Hoare proof and distance; Certificate CC; Consumer checker § 6; Kd,ξK_{d,\xi}: accept ⇒dKd,ξcirc≥d\Rightarrow d^{\mathrm{circ}}_{K_{d,\xi}}\ge 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=2s+1d = 2s + 1 under Γsurf={s≥1,d=2s+1}\Gamma_{\mathrm{surf}} = \{s \ge1, d = 2s + 1\}. Write CsurfC_{\mathrm{surf}} for the ordered CodeML program and Generate⁡[Csurf](d;d,d−1)\operatorname{Generate}[C_{\mathrm{surf}}](d; d, d - 1) for its generation into QStab at distance dd, with dd extraction rounds and an error budget of d−1d - 1 (§ 3.2). Both stages of compilation appear in the program below:

HStd:Γsurf⊢F{Σ=Σclean(d)} Compile⁡Std[Generate⁡[Csurf](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)}

Here SdS_d is the QStab program generated by the ordered CodeML family, cˉd\bar{c}_d is its compiled QClifford circuit, and Σclean(d)\Sigma_{\mathrm{clean}}(d) is the clean initial error state. The error-aware Hoare judgment ⊢F\vdash_F quantifies over every error choice. Accept⁡d\operatorname{Accept}_d specifies the declared record condition, including detector silence, while LogFail⁡d\operatorname{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 for every record.

Induction gives HStd\mathcal{H}_{\mathrm{Std}} a finite representation, including all code-algebra and compilation premises, independent of the value of dd. Expanded circuits and gate-by-gate derivations still grow with dd (§ 5.3). Figure 1 uses QStab states σ\sigma, σ′\sigma' and QClifford states Σ\Sigma, Σ′\Sigma', defined in Figure 3.

The Standard Scheme circuit and single-injection outcomes

Figure 3. The Standard Scheme circuit and single-injection outcomes. Each table row starts clean and idles elsewhere. Striped sites allow II, XX, YY, ZZ. The red path selects ZuZ_u at A. Final EE 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.

ApproachHook error analysisAll-size circuit-level code distance proofProof reuse across schemes
QuantumSE [9]×\times×\times×\times
Veri-QEC [18]×\times×\times×\times
Chen et al. [8]✓\checkmark×\times×\times
AutoQ-Para [1]×\times×\times×\times
PC-QEC (this work)✓\checkmark✓\checkmark✓\checkmark

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 dd 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.

References

  1. [1]Parosh Aziz Abdulla, Yu-Fang Chen, Michal Hečko, Lukáš Holík, Ondřej Lengál, Jyun-Ao Lin, and Ramanathan S Thinniyam. 2026. Parameterized Verification of Quantum Circuits. Proc. ACM Program. Lang. 10, POPL, Article 70 (2026), 30 pages. https://doi.org/10.1145/3776712
  2. [2]Nada Amin and Tiark Rompf. 2017. Type Soundness Proofs with Definitional Interpreters. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. ACM. https://doi.org/10.1145/3009837.3009866
  3. [3]Andrew W Appel. 2001. Foundational proof-carrying code. In 16th Annual IEEE Symposium on Logic in Computer Science. IEEE, 247–256. https://doi.org/10.1109/LICS.2001.932501
  4. [4]Gilles Barthe, Benjamin Grégoire, César Kunz, and Tamara Rezk. 2006. Certificate Translation for Optimizing Compilers. In Static Analysis (SAS) (Lecture Notes in Computer Science, Vol. 4134). Springer, 301–317. https://doi.org/10.1007/1182320_20
  5. [5]Michael Beverland, Vadym Kliuchnikov, and Eddie Schoute. 2022. Surface Code Compilation via Edge-Disjoint Paths. PRX Quantum 3, 2 (2022), 020342. https://doi.org/10.1103/PRXQuantum.3.020342
  6. [6]H. Bombin and M. A. Martin-Delgado. 2007. Optimal Resources for Topological 2D Stabilizer Codes: Comparative Study. Physical Review A 76 (2007), 012305. https://doi.org/10.1103/PhysRevA.76.012305 arXiv:quant-ph/0703272
  7. [7]Rui Chao and Ben W Reichardt. 2020. Flag fault-tolerant error correction for any stabilizer code. PRX Quantum 1, 1 (2020), 010302.DOI
  8. [8]Kean Chen, Yuhao Liu, Wang Fang, Jennifer Paykin, Xin-Chuan Wu, Albert Schmitz, Steve Zdancewic, and Gushu Li. 2025. Verifying fault-tolerance of quantum error correction codes. In International Conference on Computer Aided Verification. Springer, 3–27.arxiv.org/abs/2501.14380
  9. [9]Wang Fang and Mingsheng Ying. 2024. Symbolic Execution for Quantum Error Correction Programs. Proceedings of the ACM on Programming Languages 8, PLDI (2024), 1040–1065. https://doi.org/10.1145/3656419
  10. [10]Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. 2012. Surface codes: Towards practical large-scale quantum computation. Physical Review A 86, 3 (2012), 032324. https://doi.org/10.1103/PhysRevA.86.032324
  11. [11]Craig Gidney. 2021. Stim: a fast stabilizer circuit simulator. Quantum 5 (2021), 497. https://doi.org/10.22331/q-2021-07-06-497
  12. [12]Craig Gidney and Martin Ekerå. 2021. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5 (2021), 433. https://doi.org/10.22331/q-2021-04-15-433
  13. [13]Craig Gidney, Noah Shutty, and Cody Jones. 2024. Magic state cultivation: growing T states as cheap as CNOT gates. https://doi.org/10.48550/arXiv.2409.17595 arXiv:2409.17595 [quant-ph]
  14. [14]Daniel Gottesman. 1997. Stabilizer codes and quantum error correction. arXiv preprint quant-ph/9705052 (1997).
  15. [15]Daniel Gottesman. 2010. An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation. In Quantum Information Science and Its Contributions to Mathematics. Proceedings of Symposia in Applied Mathematics, Vol. 68. American Mathematical Society, 13–58. https://arxiv.org/abs/0904.2557
  16. [16]C. A. R. Hoare. 1969. An Axiomatic Basis for Computer Programming. Commun. ACM 12, 10 (1969), 576–580, 583. https://doi.org/10.1145/363235.363259
  17. [17]Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. 2012. Surface code quantum computing by lattice surgery. New Journal of Physics 14, 12 (2012), 123011.
  18. [18]Qifan Huang, Li Zhou, Wang Fang, Mengyu Zhao, and Mingsheng Ying. 2025. Efficient Formal Verification of Quantum Error Correcting Programs. Proceedings of the ACM on Programming Languages 9, PLDI (2025), 1068–1093.DOI
  19. [19]Upendra Kapshikar and Srijita Kundu. 2023. On the Hardness of the Minimum Distance Problem of Quantum Codes. IEEE Transactions on Information Theory 69, 10 (2023), 6293–6302. https://doi.org/10.1109/TIT.2023.3286870
  20. [20]Gilad Kishony and Austin Fowler. 2026. Surface code off-the-hook: diagonal syndrome-extraction scheduling. arXiv:2602.09099. https://doi.org/10.48550/arXiv.2602.09099
  21. [21]Emanuel Knill. 2005. Quantum computing with realistically noisy devices. Nature 434, 7029 (2005), 39–44.pubmed.ncbi.nlm.nih.gov/15744292
  22. [22]K. Rustan M. Leino. 2010. Dafny: An Automatic Program Verifier for Functional Correctness. In Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-16). Springer. https://doi.org/10.1007/978-3-642-17511-4_20
  23. [23]Yuhao Liu, Shuohuao Ping, Junyu Zhou, Ethan Decker, Justin Kalloor, Mathias Weiden, Kean Chen, Yunong Shi, Ali Javadi-Abhari, Costin Iancu, et al. 2026. Alphasyndrome: Tackling the syndrome measurement circuit scheduling problem for qec codes. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. 77–93.
  24. [24]Seth Lloyd. 1996. Universal quantum simulators. Science 273, 5278 (1996), 1073–1078. https://doi.org/10.1126/science.273.5278.1073
  25. [25]Zohar Manna and Amir Pnueli. 1995. Temporal verification of reactive systems: safety. Springer-Verlag.
  26. [26]George C Necula. 1997. Proof-carrying code. In Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 106–119.
  27. [27]Michael A Nielsen and Isaac L Chuang. 2010. Quantum Computation and Quantum Information (10th anniversary ed.). Cambridge University Press.
  28. [28]Oded Padon, Kenneth L. McMillan, Aurojit Panda, Mooly Sagiv, and Sharon Shoham. 2016. Ivy: Safety Verification by Interactive Generalization. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2016). Association for Computing Machinery, 614–630. https://doi.org/10.1145/2908080.2908118
  29. [29]Benjamin Rodatz, Boldizsár Poór, and Aleks Kissinger. 2025. Fault Tolerance by Construction. arXiv:2506.17181. https://doi.org/10.48550/arXiv.2506.17181 Version 4, revised March 2026.
  30. [30]Hongzhou Sharan, Ratish Tandon, and Nikolaos Papaspyrou. 2002. A Type System for Certified Binaries. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, 217–232. https://doi.org/10.1145/503272.503293
  31. [31]Peter W Shor. 1996. Fault-tolerant quantum computation. In Proceedings of 37th Conference on Foundations of Computer Science. IEEE, 56–65.arxiv.org/abs/quant-ph/9605011
  32. [32]Peter W. Shor. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (1997), 1484–1509. https://doi.org/10.1137/S0097539795293172
  33. [33]Yu Tomita and Krysta M. Svore. 2014. Low-distance surface codes under realistic quantum noise. Physical Review A 90 (2014), 062320. https://doi.org/10.1103/PhysRevA.90.062320
  34. [34]Joshua Viszlai, Satvik Maurya, Swamit Tannu, Margaret Martonosi, and Frederic T. Chong. 2026. PropHunt: Automated Optimization of Quantum Syndrome Measurement Circuits. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (USA) (ASPLOS ’26). Association for Computing Machinery, New York, NY, USA, 1476–1491. https://doi.org/10.1145/3779212.3790205
  35. [35]Mark Webster, Abraham Jacob, and Oscar Higgott. 2026. Distance-Finding Algorithms for Quantum Codes and Circuits. arXiv:2603.22532. https://arxiv.org/abs/2603.22532
  36. [36]John Zhuoyang Ye and Jens Palsberg. 2026. Scalable testing of quantum error correction. arXiv preprint arXiv:2602.04921 (2026).arxiv.org/abs/2602.04921
  37. [37]Litao Zhou, Jianxing Qin, Qinshi Wang, Andrew W. Appel, and QinxIang Cao. 2024. VST-A: A Foundationally Sound Annotation Verifier. Proceedings of the ACM on Programming Languages 8, POPL, Article 69 (2024), 31 pages. https://doi.org/10.1145/3632911

Paper details

vlnc:W_6n3va3hq
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 15

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex

View statement
Looking for related papers…
Contents