Quantum error correction protects quantum information by encoding it in a code described by three numbers: how many physical qubits it uses, how many logical qubits it protects, and the smallest error it cannot detect. The last is an optimum over exponentially many candidates, so it is read off a solver rather than checked. Here we show that code parameters can be certified by a short certificate, a list or a pairing or a symbolic instance, whose correctness the kernel of a proof assistant decides by computation, and whose size is itself a theorem rather than an estimate. Two published code families have distances settled here: the bivariate bicycle code's $[[144,12,12]]$, certified, and the affine-permutation codes printed at $[[1152,580,\le 12]]$ and $[[2304,1156,\le 14]]$, settled at twelve and fourteen. Eleven code families and thirty-nine parameter sets follow, with nothing beyond three standard axioms trusted and the pipeline's specification step preset to twenty columns.
AI Summary
The paper studies machine-checkable certification of quantum error-correcting code parameters, particularly distance, without trusting the solver that finds them. It develops Lean certificates for ranks, logical-operator witnesses, and distance lower bounds, combining instance-level computation with symbolic hypergraph-product arguments.
For distance upper bounds, a candidate logical operator is certified as outside the relevant stabilizer row space using a dual vector orthogonal to that row space but pairing to one with the candidate. Lower bounds either exhaustively exclude low-weight logical operators or instantiate a formalized cleaning argument. The enumeration generator is proved complete and has exactly $\sum_{j<d}\binom{n}{j}\le d n^{d-1}$ entries: polynomial in $n$ only for fixed $d$. Seed-kernel certificates and symbolic dimension formulas avoid reducing full product-code matrices.
The kernel-audited dataset contains 39 parameter sets across eleven families, reaching $n=1872$, $d=7$. The $[[144,12,12]]$ bicycle code is certified using new upper-bound and rank certificates together with a lower bound transported from an independent formalization. Reported exact distances of 12 and 14 for affine-permutation codes $[[1152,580,12]]$ and $[[2304,1156,14]]$ rely on exhaustive lower-bound computations outside Lean; only the smaller instance’s upper bound is kernel-checked here.
Limitations include enumeration scaling, a specification-generation step preset to twenty columns, and unavailable large solver-proof replay. Structured exact-distance statements require appropriate nontrivial seed kernels. The search produces no parameter improvements over its published-code baseline. The audit reports 817 declarations without reflection axioms.
Central claim may not hold: The advertised affine-permutation distances are not kernel-certified exact distances: both lower bounds rely on external exhaustive computations, and the larger instance's upper bound also comes from external search.
The general lower-bound route offers a proved enumeration size, not uniformly short certificates, because its size can reach 2^n-1 when the target distance grows with code length.
The abstract's three-standard-axiom assurance does not cover the external computations used to determine the affine-permutation distances, although the body discloses that limitation.
The no-check example proves tightness of a particular candidate-list count, not optimality of certificate size or the impossibility of alternative pruning and verification methods.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Quantum error correction protects quantum information by encoding it in a code described by three numbers: how many physical qubits it uses, how many logical qubits it protects, and the smallest error it cannot detect. The last is an optimum over exponentially many candidates, so it is read off a solver rather than checked. Here we show that code parameters can be certified by a short certificate, a list or a pairing or a symbolic instance, whose correctness the kernel of a proof assistant decides by computation, and whose size is itself a theorem rather than an estimate. Two published code families have distances settled here: the bivariate bicycle code's [[144,12,12]], certified, and the affine-permutation codes printed at [[1152,580,≤12]] and [[2304,1156,≤14]], settled at twelve and fourteen. Eleven code families and thirty-nine parameter sets follow, with nothing beyond three standard axioms trusted and the pipeline's specification step preset to twenty columns.
The paper studies machine-checkable certification of quantum error-correcting code parameters, particularly distance, without trusting the solver that finds them. It develops Lean certificates for ranks, logical-operator witnesses, and distance lower bounds, combining instance-level computation with symbolic hypergraph-product arguments.
For distance upper bounds, a candidate logical operator is certified as outside the relevant stabilizer row space using a dual vector orthogonal to that row space but pairing to one with the candidate. Lower bounds either exhaustively exclude low-weight logical operators or instantiate a formalized cleaning argument. The enumeration generator is proved complete and has exactly ∑j<d(jn)≤dnd−1 entries: polynomial in n only for fixed d. Seed-kernel certificates and symbolic dimension formulas avoid reducing full product-code matrices.
The kernel-audited dataset contains 39 parameter sets across eleven families, reaching n=1872, d=7. The [[144,12,12]] bicycle code is certified using new upper-bound and rank certificates together with a lower bound transported from an independent formalization. Reported exact distances of 12 and 14 for affine-permutation codes [[1152,580,12]] and [[2304,1156,14]] rely on exhaustive lower-bound computations outside Lean; only the smaller instance’s upper bound is kernel-checked here.
Limitations include enumeration scaling, a specification-generation step preset to twenty columns, and unavailable large solver-proof replay. Structured exact-distance statements require appropriate nontrivial seed kernels. The search produces no parameter improvements over its published-code baseline. The audit reports 817 declarations without reflection axioms.
Quantum error-correcting codes (QECCs) sit between noisy quantum hardware and reliable computation, so the code parameters used in practice must be trustworthy. The single number that summarizes a code's strength is its distance, yet certifying a distance lower bound is NP-hard in general, placing it beyond the reach of pen-and-paper proofs as well as direct proof-assistant scripting. As a result, distance values in the literature come either from non-scaling hand proofs, or from unverified solvers that leave a trust gap exactly where the code is supposed to provide a guarantee. We present Lean-QEC, the first Lean 4 formalization of stabilizer-code theory that delivers end-to-end, machine-checked distance certificates at industrial code sizes. Lean-QEC formalizes the linear algebra of qubit states, the Pauli group, stabilizer codes, the binary symplectic representation, classical coding theory, and the CSS and Bivariate Bicycle families. To break the combinatorial barrier, Lean-QEC translates the distance condition into a Boolean satisfiability formula through a verified reduction. The pipeline scales through a BitVec-flattened encoding that replaces Lean's Matrix representation, and an error-location encoding that reduces the variable count from n to k⌈log2n⌉. With these, we obtain automatically-generated Lean-checked distance proofs for a large range of industrially viable qLDPC codes within the Bivariate Bicycle and Generalized Bicycle families, including [[90, 8, 10]] and [[70, 6, 9]] BB codes, with the formulation scaling up to 144 qubits when performed outside the Lean kernel. The resulting library is reusable and is designed to plug into broader Lean-based efforts toward end-to-end verification of fault-tolerant quantum computation.
Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.
Quantum error-correcting codes protect fragile quantum information by encoding it redundantly, but identifying codes that perform well in practice with minimal overhead remains difficult due to the combinatorial search space and the high cost of logical error rate evaluation. We propose a Bayesian optimization framework to discover quantum error-correcting codes that improves data efficiency and scalability with respect to previous machine learning approaches to this task. Our main contribution is a multi-view chain-complex neural embedding that allows us to predict the logical error rate of quantum LDPC codes without performing expensive simulations. Using bivariate bicycle codes and code capacity noise as a testbed, our algorithm discovers a high-rate code [[144,36]] that achieves competitive per-qubit error rate compared to the gross code, as well as a low-error code [[144,16]] that outperforms the gross code in terms of error rate per qubit. These results highlight the ability of our pipeline to automatically discover codes balancing rate and noise suppression, while the generality of the framework enables application across diverse code families, decoders, and noise models.
Four questions sit at the base of fault-tolerant quantum computing: whether a code with given parameters can exist, whether two circuits denote the same operation, how much entropy a measurement irreversibly produces, and whether a compiled gate still means what it should. They are normally answered by four disjoint techniques. We show they are one technique. In each case the answer is an invariant—the object a governing transformation leaves fixed—and that invariant can be held as a certificate a proof kernel checks and an operator-native substrate computes. The instruments are the quantum weight enumerator, whose shadow variant yields what is, to our knowledge, the first machine-checked nonexistence certificate for a quantum error-correcting code (no pure [[4, 1, 3]] stabilizer code, reduced to an integer impossibility); the spider normal form, unique both as a linear map and as a content-addressed tree, at the minimal axiomatic footprint of a proof assistant; the measurement boundary defect, whose logical entropy equals a kernel-counted cohomology dimension; and the reduction receipt, round-tripping a certified gate word to bare metal on two independent substrates. Everything downstream of the explicitly labelled modeling step in each domain is exact integer or rational arithmetic. The common shape—find the invariant the transformation fixes, and read it off as a certificate—turns four hard quantum questions into arithmetic a machine can hold. Published by The Institute for Applied Ontological Mathematics.
It is commonly believed that logical states of quantum error-correcting codes have to be highly entangled such that codes capable of correcting more errors require more entanglement to encode a qubit. Here, we show that the validity of this belief depends on the specific code and the choice of entanglement measure. To this end, we characterize a tradeoff between the code distance d quantifying the number of correctable errors, and the geometric entanglement measure of logical states quantifying their maximal overlap with product states or more general "topologically trivial" states. The maximum overlap is shown to be exponentially small in d for three families of codes: (1) low-density parity check codes with commuting check operators, (2) stabilizer codes, and (3) codes with a constant encoding rate. Equivalently, the geometric entanglement of any logical state of these codes grows at least linearly with d. On the opposite side, we also show that this distance-entanglement tradeoff does not hold in general. For any constant d and k (number of logical qubits), we show there exists a family of codes such that the geometric entanglement of some logical states approaches zero in the limit of large code length.
Code and circuit distances characterize how strongly quantum error correction suppresses logical errors and guide code comparisons, schedule choices and resource estimates. Yet many published distances are only upper bounds from heuristic searches. Here, we express both distances as tropical partition functions and evaluate them with rank-based dynamic programming and weight-bounded search. Circuit reductions and relaxations shrink the problems, and proved lower bounds with explicit logical errors of matching weight certify exact values. On two benchmarks, our method certifies more instances than all other tested exact solvers combined. We certify distances for codes with up to 31,200 qubits, such as Google's modular hyperbolic codes, and for memory circuits with up to 8×105 fault mechanisms, such as those of high-rate Cornucopia codes. Our audit of 26 recent papers identifies overestimated distances and non-tight upper bounds in 10 papers, with a maximum discrepancy of at least eight. Certified distances also guide circuit design and show which defective chips remain usable. In particular, we certify circuit distance 16 for IBM's two-gross memory circuits with the standard schedule, not the assumed 18, whereas redesigned schedules reach 18 at one noisy cycle, at the cost of one more timestep per cycle. At 99.98% junction yield, keeping gross-code memory blocks with dead checks that are certified at distance 10 or more raises the estimated usable share from 53% for perfect blocks alone to 94% with an improved schedule.