Distance Prediction for Quantum Codes

AI summary

Overview

Research area: Quantum error correction (specifically qLDPC code design) combined with machine learning — predicting the minimum distance of Bivariate Bicycle (BB) quantum codes with a neural network rather than running expensive search algorithms.

Technical level: Intermediate. The paper assumes familiarity with stabilizer/CSS codes, Tanner graphs, and transformer architectures, but its central idea (replace a slow search with a fast learned predictor) is easy to grasp.

Scope: The paper builds a dataset of ~58,000 BB and perturbed-BB (PBB) codes labeled with heuristic distance upper bounds, then trains and evaluates BB-Net, an attention-based model that predicts code distance at a small fraction of the runtime of the heuristics that produced the labels.

What This Paper Is About

The distance of a quantum code determines how many physical errors it can tolerate, but computing it exactly is NP-hard, and even heuristic searches that only produce an upper bound are slow enough to bottleneck the search over large families of candidate codes. The authors ask whether a neural network can learn to predict the distance of BB codes directly from their compact algebraic description, so that thousands of candidates can be screened in seconds instead of hours. The goal is not to certify distances but to relieve the distance-calculation bottleneck in code-discovery pipelines.

Key Contributions

1. Framing distance estimation as a machine-learning problem. The authors train a network on labels produced by expensive heuristic searches and predict those labels at a small fraction of the cost. They state that, to their knowledge, this is the first work to predict quantum-code distance directly with a learned model.

2. A dedicated dataset. Approximately 58,000 code examples (final count 58,704) covering both CSS BB codes and non-CSS PBB codes, each with a corresponding distance upper bound obtained from BP-OSD, QDistRnd, and QDistEvol run with a budget of 10,000 trials per code, taking the smallest distance found across the three methods.

3. A compact input representation. A tokenization scheme that works directly from the sparse bivariate polynomials: "polynomial tokens" (one per monomial, with a one-hot polynomial identity and a 32-dimensional Fourier positional encoding using harmonics r = 1…8) and "Tanner spectral tokens" (one per group character, ℓm = n/2 tokens, each an 18-dimensional feature vector), avoiding explicit construction of the full parity-check matrices.

4. The BB-Net architecture. Two attention-based encoders (polynomial and Tanner spectral) conditioned on code parameters via FiLM, fused through a learned gated residual connection, followed by a distance-classification head.

Main Findings

• Test benchmark accuracy (5,870 codes, ±2 tolerance): BB-Net reaches 96.39% accuracy with RMSE 1.131, versus 94.86% (RMSE 1.485) for QDistEvol, 92.20% (RMSE 2.319) for QDistRnd, 82.23% (RMSE 23.322) for BP-OSD, 61.23% (RMSE 1.933) for UEStim, 34.60% (RMSE 9.309) for CCStim, and 0.02% (RMSE 4.950) for GEStim. The heuristics in this table used 200 trials per code except GEStim (1), CCStim (1), and UEStim (3).

• Runtime: BB-Net evaluates a code in 0.005 s and the whole benchmark in 26.8 s, compared with 1.0 s per code / 6,057 s total for QDistEvol, 3.3 s / 19,383 s for QDistRnd, 19.1 s / 112,275 s for BP-OSD, 13.1 s / 76,775 s for UEStim, 1.2 s / 7,164 s for CCStim, and 1.2 s / 6,940 s for GEStim. The paper describes the heuristic comparison as using a budget of up to 10^4 times more computational runtime.

• Certified subset (2,366 codes, all with d ≤ 14): BB-Net achieves 98.94% accuracy (RMSE 0.594), compared with 100.00% for QDistRnd, 100.00% for QDistEvol, 99.96% for BP-OSD, 98.44% for UEStim, 64.03% for CCStim, and 0.04% for GEStim. On these codes the heuristics are essentially solving an easier problem, while BB-Net runs in 10.8 s total versus 11,887 s (QDistRnd), 3,883 s (QDistEvol), and 9,032 s (BP-OSD).

• Upper-bound subset (3,504 unresolved codes): BB-Net is strongest, with 94.66% accuracy and RMSE 1.380, versus 91.38% / 1.923 for QDistEvol, 86.93% / 3.002 for QDistRnd, 70.26% / 30.181 for BP-OSD, 36.10% / 37.190 for UEStim, 14.73% / 35.362 for CCStim, and 0.00% / 42.355 for GEStim. The authors highlight this as the regime where both exact solvers and heuristics struggle.

• Label validity check: Of the 5,870 test codes, MILP certified 2,366 with a 2-hour-per-code time limit, and on every certified code the 10,000-trial heuristic label equals the certified distance.

• Distance screening (ROC-AUC): BB-Net scores 1.000 at d ≥ 4, 0.998 at d ≥ 8, 0.996 at d ≥ 10, 0.993 at d ≥ 12, 0.989 at d ≥ 14, 0.989 at d ≥ 16, 0.988 at d ≥ 18, 0.987 at d ≥ 20, 0.990 at d ≥ 22, and 0.991 at d ≥ 24. It is slightly below QDistEvol and QDistRnd at intermediate thresholds and comparable at the highest ones, at a fraction of their inference time.

• Ablation (validation NLL, best epoch): Adding the Tanner spectral branch improves NLL from 1.496 ± 0.014 to 1.039 ± 0.019. The full configuration with augmentation, shift canonicalization, and FiLM conditioning reaches 0.683 ± 0.010; removing FiLM gives 0.712 ± 0.025, removing shift canonicalization gives 0.762 ± 0.012, and removing augmentation gives 0.924 ± 0.026.

• Qualitative successes: Table 7 lists test codes where the heuristics overestimate the reference distance but BB-Net matches it — for example a (324, 18, 9) code with reference distance 18 where BP-OSD returns 44 and QDistEvol 45, and a (270, 27, 5) code with reference 25 where QDistRnd returns 37.

Methodology in Plain English

The authors start by generating a large pool of candidate BB codes: two-block qLDPC codes defined by two sparse polynomials A(x, y) and B(x, y) over a two-dimensional cyclic group, giving block length n = 2ℓm. They restrict to n ≤ 360 and ℓ, m ≤ 30, keep only valid codes (nonzero logical dimension k, at least two surviving terms in A and B, nonempty C and D for PBB, and commuting stabilizers), and remove duplicates and symmetry-equivalent specifications. Each surviving code is labeled with the smallest distance found by three heuristic searchers at 10,000 trials each. Since heuristics give only upper bounds, the labels are upper bounds — the paper says this explicitly.

The network never sees the huge parity-check matrices. Instead, each code is turned into two short token sequences. The first is one token per monomial in the polynomial supports, tagged with which polynomial it belongs to and positioned using sine/cosine features of its cyclic coordinates. The second is one token per Fourier character of the cyclic group, summarizing how the polynomials respond at that frequency. Two transformer-style encoders process these sequences, the polynomial branch is conditioned on the code parameters (ℓ, m, n, k) through a feature-wise scale-and-shift layer (FiLM), and a learned gate combines the two latent vectors. A small classification head then outputs a probability distribution over distance values, trained with categorical cross-entropy.

Two data-handling tricks matter. "Shift canonicalization" maps each code to a single canonical representative so that trivially equivalent inputs do not appear as different examples. "Augmentation" applies random distance-preserving symmetries — group automorphisms, cyclic translations, and swapping the polynomial registers — so the model sees varied but equivalent forms of the same code. Training used 8 layers, d_model 256, learning rate 3e-4, dropout 0.1, 90 epochs with 9 warmup epochs, batch size 256, and the AdamW optimizer with weight decay 0.01, on an L40s GPU.

Why This Matters

Distance evaluation sits inside the inner loop of any search over quantum code families: if each candidate costs seconds to minutes, only a tiny fraction of the design space can be explored. A predictor that runs in milliseconds changes the economics of that loop, allowing broad screening first and expensive verification only on the survivors.

Real-world applications (as framed by the paper):

• ML-driven code-search pipelines: BB-Net can act as a fast filter that ranks candidates before QDistRnd, QDistEvol, BP-OSD, or MILP are applied to the most promising codes to tighten bounds or obtain certificates.
• Fault-tolerant quantum computing hardware design: BB codes are presented as a practical route to high-threshold, low-overhead fault tolerance that maps efficiently to hardware constraints, so faster code screening feeds directly into architecture decisions.
• LLM-assisted code discovery: The paper situates its work alongside recent efforts that use LLMs to propose new QEC codes, where the cost of evaluating each proposal is the limiting factor.
• Benchmarking and dataset reuse: The released dataset of 58,704 labeled codes provides a common testbed for future distance-prediction and distance-estimation methods.

Industry relevance: Any organization pursuing qLDPC-based fault tolerance — quantum hardware vendors, cloud quantum-computing providers, and compiler/EDA-like tooling teams — has an interest in cheaper code evaluation, since the number of candidate codes that can be assessed directly bounds the quality of the code finally chosen.

Future Directions

• Closing the certification gap. The labels are upper bounds, and on the certified subset QDistRnd, QDistEvol, and BP-OSD reach 100.00%, 100.00%, and 99.96% accuracy while BB-Net reaches 98.94%. Extending learned prediction toward certified or guaranteed bounds, rather than a proxy for heuristic output, is a natural next step.

• Going beyond BB and PBB codes. The tokenization and spectral encoder are built specifically around the bivariate cyclic structure; generalizing to other qLDPC families — or to quantum LDPC codes without an Abelian group lift — remains open.

• Scaling past n ≤ 360. The dataset is capped at block length 360 and ℓ, m ≤ 30, and the certified examples all have d ≤ 14. Whether accuracy and speed hold for larger, higher-distance codes is not established here.

• Integration into closed-loop search. The paper motivates use inside search pipelines but reports no end-to-end experiment in which BB-Net-guided screening actually yields newly discovered codes with better distance than existing ones.

Target Audience

Researchers and practitioners working on quantum error correction and qLDPC code design; machine-learning researchers interested in scientific applications of transformers and structured tokenization; and quantum-computing engineers building tooling for fault-tolerant architectures. Readers wanting the headline result can read the abstract and Table 1, while those interested in the representation design will find the tokenization and ablation sections most useful.

Authors’ abstract

The distance of a quantum code is a fundamental metric that dictates its error-correction capability. While quantum low-density parity-check (qLDPC) families such as Bivariate Bicycle (BB) codes offer a promising pathway to low-overhead fault-tolerant quantum computing, computing their distance is challenging. Current exact solvers and even search heuristics that provide a distance upper bound suffer from severe computational bottlenecks, restricting the discovery of optimal codes. In this paper, we construct a dataset of BB codes with corresponding distance upper bounds obtained through high-budget heuristic searches. We introduce BB-Net, an attention-based neural network architecture for predicting the distance of BB codes. It achieves 96.39% accuracy on the reference distances in the test set, compared with 94.86% for state-of-the-art heuristics with a budget of up to $10^{4}$ times more computational runtime. On a subset with certified exact distances, BB-Net achieves 98.94%. By relieving the distance-calculation bottleneck, BB-Net enables faster screening of large code spaces, particularly in ML-driven search pipelines, and thereby can accelerate the discovery of novel quantum error-correcting codes, an important capability for advancing scalable fault-tolerant quantum computing. Our code is publicly available: https://github.com/NadavSc/BBNet