A quantum memory stores logical qubits in many physical qubits so that errors can be detected and corrected. The overhead of doing so, measured by how many physical qubits are spent per logical qubit at a given error-correcting power, is one of the main costs of fault-tolerant quantum computation. Bivariate-bicycle (BB) codes are currently the leading low-overhead family: the gross code of Bravyi et al. (Nature, 2024) stores 12 logical qubits at distance 12 using 144 data qubits, roughly a tenth of the overhead of a surface code with the same distance, and it is the basis of a published hardware roadmap. The search for higher-rate members of the family is active, and the claims made in it are claims about the exact distance of explicit finite codes. These are finite but very large computations, and they are rarely checked independently.
Timeline.
Fix positive integers and let . The monomial of the ring is identified with . A polynomial with coefficients in is identified with its support, the finite set of monomials with coefficient . The circulant of is the binary matrix with a in row , column exactly when .
Given two polynomials , the BB code acts on qubits, arranged in two blocks indexed by . Its check matrices are
where and also denote their circulants. Because is abelian, over , so this is a CSS code. Its parameters are:
The code is when . Each check of a code built from two three-term polynomials touches six qubits (weight 6). The Tanner graph joins each qubit to the X- and Z-checks acting on it, and the code is connected when this graph is connected.
each with (Table 9 of the source). Each new code is also a milestone on its own.
The result. The new codes encode 25% and 50% more logical qubits at distance 12 than the best weight-6 code reported by evolutionary search, with figures of merit of 8.57 and 9.60. The ladder distances turn published values, several of them previously supported only by heuristic searches or upper bounds, into exact statements. In particular settles an upper bound left open by Bravyi et al. The envelope statement is a negative result: within this family and size range, distance 12 is the ceiling at .
Formalizing it. In the source, each lower bound on a distance is a DRAT refutation or a replayable proof tree, checked by external programs. Only the pruning lemma (Lemma 1) has a machine-checked proof, in Lean 4. A complete formalization would make the code parameters kernel-checked facts about explicit Mathlib objects, independent of every external checker. Upper bounds on distance and the values of are finite linear-algebra facts. Lower bounds are exhaustive statements over -sized spaces and are the core of the work.
The upper bound needs one explicit weight-12 logical together with a proof that it lies outside the opposite row space. The lower bound asks that no nontrivial logical of weight at most 11 exist among roughly candidate supports. Direct enumeration is out of reach. A SAT encoding with a cardinality constraint is several orders of magnitude slower than the source's pruned search, and the resulting proof objects are large: hundreds of megabytes for the larger ladder codes. Kernel-checking such certificates, or finding structure that avoids them, is the central difficulty. Computing also requires an -rank of matrices with up to 180 rows and 360 columns, and Mathlib's Matrix.rank is not computable by decide. The envelope statement additionally quantifies over 971 group shapes and every pair of three-term polynomials on each.
All objects are in the definition file BBCode_Setting. is ZMod l × ZMod m, and a polynomial is a Finset of monomials, which makes it a set of distinct terms. The circulant has entry 1 at iff . Qubits are G ⊕ G (left and right blocks). is Matrix.fromCols (circulant A) (circulant B) and is Matrix.fromCols (circulant B)ᵀ (circulant A)ᵀ, over ZMod 2. The row space is the ZMod 2-span of the rows, and the weight counts nonzero coordinates. NumLogical A B k states additively, avoiding truncated subtraction. HasZDistance A B d requires both a nontrivial Z-logical of weight exactly and the lower bound for every nontrivial Z-logical, so a code without logicals cannot satisfy it vacuously. IsCode A B n k d bundles , and both distances.
The envelope quantifies over all with . The source enumerates 961 shapes; the 10 it omits () cannot have , so the two ranges are equivalent.
Reusable infrastructure includes computable rank certificates (explicit row-echelon or basis witnesses), a verified checker for DRAT or proof-tree certificates, and symmetry lemmas for group translations acting on BB codes. Contributions of any of these, of individual sectors ( or separately), or of upper and lower bounds as separate lemmas are welcome.
namespace BBCode
theorem new_codes :
IsCode (l := 2) (m := 84) {(0, 0), (0, 1), (1, 5)} {(0, 0), (0, 4), (0, 62)} 336 20 12 ∧
IsCode (l := 2) (m := 84) {(0, 0), (0, 1), (1, 5)} {(0, 0), (0, 20), (0, 46)} 336 20 12 ∧
IsCode (l := 6) (m := 30) {(0, 0), (0, 1), (1, 2)} {(0, 0), (0, 8), (2, 16)} 360 24 12 := by
sorry
end BBCodeThe three bivariate-bicycle codes of Table 9 have the stated parameters, with :
Here , ,
and each distance is the minimum weight of a nontrivial logical in that sector. These codes encode 25% and 50% more logical qubits than the best distance-12 weight-6 code previously reported.
Formalization Note IsCode is defined in BBCode_Setting.
No open leaves. Every sub-goal is proved or awaiting decomposition.