⚛️ quantum physics

Certifying quantum code and circuit distances at scale

This paper introduces a scalable method using tropical partition functions and dynamic programming to exactly certify quantum code and circuit distances, revealing significant overestimations in prior literature while enabling more accurate resource estimates and the utilization of defective quantum hardware.

Original author: Bin Cheng, Naixu Guo, Feng Pan

Published 2026-11-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original author: Bin Cheng, Naixu Guo, Feng Pan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers promise to solve problems that are impossible for today's machines, from designing new materials to breaking complex codes. To do this, they must perform calculations with extreme precision. However, the physical particles that store information in these machines are notoriously fragile, prone to errors from the slightest disturbance. To overcome this, scientists use a technique called quantum error correction. They spread a single piece of information across many physical particles, creating a logical unit that can survive if some of its parts fail. The strength of this protection is measured by a value called distance. A higher distance means the system can withstand more errors before the information is lost. This number is critical for engineers; it dictates how many physical particles are needed to build a useful computer and how reliable the final machine will be. For years, researchers have relied on estimates for this distance, often using computer searches that find errors but cannot prove they have found the smallest possible ones.

A team of researchers has now developed a way to calculate these distances exactly, even for the massive systems proposed for future hardware. They treated the problem of finding the smallest error as a unified mathematical puzzle and solved it using three distinct, rigorous methods that work together. Instead of guessing or stopping at the first error found, their approach proves that no smaller error exists. By combining these methods with clever shortcuts that shrink the problem size, they were able to certify the exact distances for quantum codes involving up to 31,200 physical particles and circuits with hundreds of thousands of potential failure points. This level of certainty allows them to verify the designs of major technology companies and identify flaws that previous estimates missed.

The researchers applied their method to a wide range of current proposals, including designs from Google and IBM. In many cases, they found that the published estimates were too optimistic. For instance, a specific memory circuit from IBM, which was assumed to have a distance of 18, was proven to have a distance of only 16. This difference is significant because it changes the predicted rate of errors by a large factor. In another case involving a code designed by Google, the team certified distances for systems with over 31,000 qubits, confirming values that had previously been unknown. Their audit of twenty-six recent scientific papers revealed that ten of them contained overestimated distances, with some discrepancies as large as eight units. These errors were not due to bad math in the original papers, but rather because the search methods used there could not guarantee they had found the absolute smallest error.

Beyond correcting past numbers, the team used their tools to design better circuits. They tested thousands of different schedules for how to measure errors in a specific type of quantum code. They found that while one standard schedule was optimal for some codes, it was far from the best for others. By rearranging the order of operations, they could increase the distance of a circuit from 16 to 18, making it significantly more robust. This kind of precise optimization is essential for building machines that can run long calculations without failing. The researchers also showed how their method helps in the real world of manufacturing. Quantum chips often come out of the factory with minor defects, such as a single broken sensor. Previous models suggested that any chip with a defect should be discarded. However, by certifying the distance of these imperfect chips, the team showed that many remain usable. For example, at a manufacturing yield where 99.98% of connections work, keeping chips with a few dead sensors that still maintain a high distance could increase the number of usable chips from 53% to 94%.

The work relies on a unified framework that treats both the code itself and the circuit used to measure it as a single problem. The researchers expressed the search for the smallest error as a "tropical partition function," a concept that allows them to use powerful algorithms to find the minimum value. They then employed three different exact solvers: a dynamic program that sweeps through the system like a ladder, a search that looks for errors within a specific weight limit, and a bidirectional search that meets in the middle. A cost model decides which solver to use for each part of the problem to ensure efficiency. When a solver finds an error, the team verifies it by replaying the sequence of faults in a simulator to ensure it actually causes a logical failure without triggering any alarms. This process produces a certificate: a proof that no lighter error exists, paired with the specific error that was found.

The results have immediate implications for the architecture of future quantum computers. For IBM's planned processor, the team confirmed that the standard schedule for a specific memory block has a distance of 16, not 18 as previously assumed. However, they also identified alternative schedules that achieve the higher distance of 18, albeit with a slight increase in the time required for each cycle. This trade-off between speed and reliability is now a known quantity rather than a guess. Similarly, for Google's modular hyperbolic codes, the team provided the first exact distances for systems of that scale, settling questions that had remained open. The ability to certify these values means that resource estimates for future machines can be based on hard facts rather than upper bounds.

The study also addressed the issue of logical measurements, where separate blocks of quantum memory are joined together to perform operations. The researchers found that the distance of these merged systems depends heavily on how the extra "gauge" qubits introduced during the process are handled. If these qubits are left free, the distance can drop significantly, but if they are fixed in a specific state, the distance remains high. This distinction is crucial for designing measurement protocols that do not accidentally weaken the error protection. The team's exact calculations showed that previous estimates had missed these nuances, leading to potential overestimates of performance.

In the end, the paper transforms the distance of a quantum code from an estimate into a verified quantity. This shift removes a major source of uncertainty from the planning of quantum computers. Engineers can now compare different designs with confidence, knowing exactly how many errors each can tolerate. The method scales to the size of the largest proposals on the horizon, handling systems with hundreds of thousands of potential failure points. While some extremely large or complex instances still require substantial computing resources, the team has demonstrated that exact certification is possible for the vast majority of current designs. This precision allows for a more realistic assessment of what quantum computers can achieve and how many physical resources they will truly need.

Technical Summary: Certifying Quantum Code and Circuit Distances at Scale

Problem Statement

Quantum error correction (QEC) relies on the code distance ( $d$ ) and circuit distance ( $d_{circ}$ ) to characterize the suppression of logical errors and guide resource estimates. The code distance is the minimum weight of a logical operator, while the circuit distance is the minimum number of faults in a syndrome-measurement circuit that flips a logical observable without triggering any detectors.

Computing these distances is computationally intractable for large-scale systems. Finding the minimum distance of a classical linear code is NP-hard, and circuit distance problems are even larger, involving $10^4$ to $10^5$ fault mechanisms in current hardware proposals. Consequently, many published distances are merely upper bounds derived from heuristic searches (e.g., randomized decoding, sampling information sets, or Stim's search for undetectable errors). These heuristics often fail to certify that the found errors are of minimum weight, leading to potential overestimates. Exact methods like integer programming, MaxSAT, and connected-cluster enumeration exist but struggle to scale to the circuits proposed for near-term hardware, such as IBM's bivariate bicycle codes or Google's modular hyperbolic codes. This uncertainty forces architecture studies to rely on assumed distances, introducing significant errors in predicted logical error rates and resource requirements.

Methodology

The authors propose a unified framework to compute code and circuit distances exactly at scale by expressing them as tropical partition functions. The distance is formulated as the zero-temperature limit of free energy in the min-plus algebra:
$Z_M(t) = \min \{ |e| : Me = t \}$
where $M$ represents the constraint matrix (check matrix for codes, detector matrix for circuits) and $t$ represents the syndrome and logical label constraints.

To evaluate these functions, the authors employ three exact algorithms, coordinated by a cost model:

Dense Rank-based Dynamic Programming (Rank DP): A min-plus dynamic program that stores the minimum weight of partial assignments sharing the same boundary state. Its complexity depends on the cut rank (or rank-width) of the problem's decomposition. It is efficient for problems with low rank-width, such as surface codes and concatenated codes.
Weight-Truncated Rank DP: A bidirectional search that merges forward and backward dynamic programming tables but stores only entries within prescribed weight budgets. This combines the BEAST algorithm's bidirectional search with min-plus state merging, making it effective for problems where the distance is small but the rank-width is high.
Weight-Bounded Search: An exhaustive search that explores fault sets within increasing weight budgets. It uses canonical branching, covering bounds (dual linear programming bounds), and completion tables (meet-in-the-middle) to prune the search space. This method is particularly effective for qLDPC codes with large distances.

Reductions and Certificates:
To handle large circuits, the method employs circuit reductions:

Sector Reduction: Restricts detectors to a single memory basis.
Time Collapse: Sums detectors of each check over all rounds, creating a smaller problem whose distance serves as a lower bound for the full circuit.
Lifting: Attempts to map minimum-weight solutions of the collapsed problem back to the full circuit. If a solution lifts, the lower bound is matched, certifying the exact distance. If not, the lower bound is raised.

A result is certified only when a proved lower bound (from an exhaustive evaluator) meets the weight of an explicit logical error (upper bound) found by the search. For circuits, these errors are verified by replaying them in the Stim simulator.

Key Contributions

Exact Computation at Scale: The method certifies distances for codes with up to 31,200 qubits (Google's modular hyperbolic codes) and memory circuits with up to $8 \times 10^5$ fault mechanisms (Cornucopia codes), scales previously unreachable by exact solvers.
Benchmark Superiority: On two comprehensive benchmarks (74 instances and 126 independent instances), the method certifies more instances than all other tested exact solvers (including integer programming, MaxSAT, and dist-m4ri) combined.
Audit of Published Literature: The authors audited 26 recent papers (2023–2026). They confirmed all reported exact code distances but found that 10 papers contained overestimated circuit or code distances. The maximum discrepancy was at least 8, with several instances where assumed distances were significantly higher than the certified values.
Design and Architecture Insights:
- Schedule Optimization: For IBM's bivariate bicycle codes, the authors evaluated 8,496 uniform depth-seven schedules. They found the standard schedule is optimal for only one code; for others, optimized schedules can increase the circuit distance (e.g., from 10 to 11 for the gross code, or 16 to 18 for the two-gross code).
- Chip Yield: The method certifies distances for chips with "dead" check qubits. They show that keeping defective chips certified at distance $\ge 10$ can raise the estimated usable yield from 53% (perfect chips only) to 94% at 99.98% junction yield.
- Logical Measurements: The study certifies distances for merged codes used in logical measurements, revealing that the distance depends on whether gauge qubits are fixed. Without fixing, distances can drop significantly (e.g., to 2), whereas fixing them preserves the distance.

Results

IBM Two-Gross Code: The paper certifies a circuit distance of 16 for IBM's two-gross memory circuit with the standard schedule, contradicting the assumed value of 18 used in architecture studies. This reduces the predicted exponent of the logical error rate by one. Optimized schedules can reach 18 but require an additional timestep per cycle.
Google's Modular Hyperbolic Codes: The method certifies distances for codes with up to 31,200 qubits, resolving previously open intervals.
Cornucopia Codes: The largest certified circuit instance has $8 \times 10^5$ fault mechanisms. The certified distance implies a leading order of $p^8$ for logical error rates, rather than the $p^9$ assumed in previous extrapolations.
Performance: The method solves surface-code memory circuits up to distance 25 in under 10 seconds on a single thread, outperforming other general-purpose exact solvers which fail beyond distance 15.

Significance

The paper claims that certified exact distances transform the distance of a code or circuit from an estimate into a verified quantity. This removes a critical source of error from code comparisons, resource estimates, and architectural choices.

Reliability: It prevents the overestimation of error suppression capabilities, which could lead to under-provisioned quantum computers.
Design Guidance: It enables the evaluation of every candidate schedule in a design space, allowing for the selection of schedules that maximize circuit distance.
Hardware Viability: By certifying that defective chips can still maintain high distances, the method supports more realistic yield estimates for quantum hardware manufacturing.
Protocol Specificity: It clarifies that distances are protocol-dependent (e.g., whether gauge qubits are fixed in logical measurements), providing precise bounds for specific operational contexts rather than generic assumptions.

The authors emphasize that while some problems remain expensive (wide and large distance), the combination of reductions, relaxations, and multiple exact evaluators allows the community to move beyond heuristic upper bounds for the circuits currently proposed for hardware.