⚛️ quantum physics

Distance-Finding Algorithms for Quantum Codes and Circuits

This paper benchmarks a wide range of exact and heuristic algorithms for calculating the distance of classical and quantum codes and circuits, introduces the new QDistEvol algorithm which performs well for quantum LDPC codes, and releases these tools via the `codeDistance` Python package.

Original authors: Mark Webster, Abraham Jacob, Oscar Higgott

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mark Webster, Abraham Jacob, Oscar Higgott

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 authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a fortress to protect a precious treasure (your quantum computer's data). To keep the treasure safe, you need a system that can detect when a thief (an error) tries to sneak in. The strength of your fortress is measured by its "distance."

In simple terms, distance is the minimum number of thieves required to break into the vault without being caught.

If the distance is 3, it means you need at least 3 thieves working together to steal the treasure without triggering an alarm.
If the distance is 10, you need 10 thieves. The higher the number, the safer your fortress.

The Problem: The "Too Big" Puzzle

For a long time, scientists have been designing new, super-efficient fortresses called Quantum LDPC codes. These are like architectural marvels that use far fewer resources than old designs. But there's a catch: because these new fortresses are so complex and huge, it's incredibly difficult to calculate their "distance."

It's like trying to count every possible way a thief could break into a skyscraper. For a small house, you can check every window and door. For a skyscraper with millions of rooms, checking every single possibility would take longer than the age of the universe.

Furthermore, real-world quantum computers aren't just static walls; they are active machines running constantly. This adds a layer of complexity called "circuit distance." It's not just about the walls; it's about the guards, the cameras, and the power grid all working together. Calculating this is even harder than just looking at the walls.

The Solution: A Toolkit of Detectives

The authors of this paper (Mark, Abraham, and Oscar) decided to act like a detective agency. They gathered a massive team of different "detective algorithms" (methods) to see which ones are best at finding the distance of these new quantum fortresses.

They divided their detectives into two teams:

1. The "Perfectionists" (Exact Methods)

These detectives are thorough. They promise to find the exact answer, no matter how long it takes.

How they work: They check every single possibility, or use powerful math to prove the answer is correct.
The Analogy: Imagine a detective who checks every single room in the skyscraper, one by one, to find the weakest spot.
The Downside: They are slow. For huge buildings, they might take days or weeks to finish.
The Winner: For many of these complex codes, a method called Magma (a powerful math software) and Gurobi (a solver) were the best at finding the exact answer, though they sometimes needed a time limit.

2. The "Speedsters" (Heuristic Methods)

These detectives are fast but don't promise perfection. They give you a very good guess or a "safe lower bound" (e.g., "I'm 99% sure the distance is at least 5").

How they work: They use shortcuts, random sampling, and smart guesses to find the answer quickly.
The Analogy: Imagine a detective who walks through the building, checks the most likely entry points, and says, "Based on this, the distance is probably 5."
The Downside: Sometimes they might miss a rare, sneaky way to break in.
The Star Performer: The authors introduced a new detective called QDistEvol. Think of it as a detective who uses evolution. It starts with a bunch of random guesses, keeps the best ones, mixes them together (like breeding), and creates even better guesses for the next round.
- Result: QDistEvol was the champion for the most complex, high-tech quantum codes (like the "Bivariate Bicycle" and "Lifted Product" codes). It found the best answers faster than anyone else.

The "Filter" Trick

One of the cleverest things the team did was realize that for some of these massive circuits, they didn't need to check every error. They created a filter (like a sieve).

The Analogy: Imagine trying to find a needle in a haystack. Instead of looking at every piece of hay, you use a sieve to remove the big chunks of hay first, leaving you with a much smaller pile to search.
Result: This filter reduced the size of the problem by up to 85%, making it possible for the algorithms to solve problems that were previously impossible.

Why Does This Matter?

Quantum computers are the next big thing in technology, but they are currently very fragile. To make them useful, we need these "quantum LDPC codes" to protect the data.

However, before we build a quantum computer, we need to know if our protection plan actually works. If we can't calculate the distance, we don't know if the fortress is strong enough.

This paper is like a user manual for architects. It tells us:

"If you are building a small house, use Detective A."
"If you are building a massive skyscraper, use Detective B (QDistEvol)."
"If you are building a circuit, use this Filter first."

The Takeaway

The authors have made all their tools, data, and the new QDistEvol algorithm available to the public in a free software package called codeDistance.

By giving scientists the right tools to measure the strength of these new quantum codes, this work helps speed up the development of fault-tolerant quantum computers. It's a crucial step in turning the dream of powerful quantum computing into a reality.

In short: They built a toolbox of smart, fast, and sometimes evolutionary detectives to help us measure the strength of the next generation of quantum computers, ensuring they are strong enough to protect our future data.

1. Problem Statement

The minimum distance ( $d$ ) of a quantum error-correcting (QEC) code or circuit is a fundamental figure of merit, representing the minimum number of physical errors required to cause an undetectable logical failure. While essential for evaluating fault tolerance, calculating this distance is computationally challenging, particularly for:

Quantum LDPC (Low-Density Parity-Check) codes: These promise reduced overhead but have complex structures that make distance calculation difficult.
Circuit-level distance: Determining the distance of a syndrome-extraction circuit is significantly harder than finding the code distance alone. The detector error matrix (DEM) for a circuit is often orders of magnitude larger than the code's check matrix, and the problem scales exponentially with the number of rounds and physical errors.
NP-Completeness: Finding the exact distance for arbitrary binary linear codes or stabilizer codes is an NP-complete problem.

The paper addresses the lack of systematic benchmarking for distance-finding algorithms across diverse code families (classical, quantum CSS, non-CSS, and circuits) and error models.

2. Methodology

The authors conducted a comprehensive benchmarking study comparing a wide range of exact and heuristic algorithms.

Algorithm Categories

Exact Methods (Guaranteed to find the true distance, but potentially slow):
- Brouwer-Zimmermann (BZ): An exhaustive search optimized by identifying information sets and using lower/upper bound convergence. Implemented in Magma and a new Python version (BZDistMW).
- Mixed-Integer Programming (MIP): Formulating distance finding as a constraint optimization problem solved by Gurobi and SCIP.
- MaxSAT Solvers: Using solvers like CLISAT (CASHWMaxSAT-CorePlus) to find minimum weight logical errors.
- Connected Cluster (m4riCC): A breadth-first search on Tanner graphs, effective for low-degree LDPC codes.
- Meet-in-the-Middle: Reducing complexity by splitting error enumeration (e.g., QubitSerf, MeetMiddleMW).
Heuristic Methods (Faster, provide bounds but no guarantee of exactness):
- Random Information Set (QDistRnd/m4riRW): Randomly permuting columns to find low-weight codewords via Reduced Row Echelon Form (RREF).
- Evolutionary Algorithms (QDistEvol): A genetic algorithm that evolves column permutations to minimize logical operator weight.
- Syndrome Decoders (BP-OSD): Using Belief Propagation with Ordered Statistics Decoding to find corrections for random logical syndromes.
- Stim Undetectable Error Methods: Truncated searches (GEStim, CCStim, UEStim) designed for topological codes with specific error structures (e.g., graph-like errors).

Benchmarking Framework

Datasets: The study tested algorithms on:
- Classical codes (Codetables.de, Lifted Product).
- Quantum Stabilizer codes (Non-CSS, Hyperbolic Surface/Colour, Lifted Product, Bivariate Bicycle, Quantum Tanner).
- Syndrome Extraction Circuits (Surface, Colour, Bivariate Bicycle).
Metrics: Processing time, success rate (finding the known minimum distance), and the quality of bounds when terminated early.
Tools: The authors developed the codeDistance Python package, which wraps existing implementations (Magma, GAP, C libraries, Stim) and includes new implementations (e.g., Python BZ, QDistEvol).

3. Key Contributions

Development of QDistEvol: The authors refined the QDistEvol algorithm, an evolutionary search method. They demonstrated that it significantly outperforms standard random information set methods (QDistRnd) in accuracy, particularly for high-rate quantum LDPC codes, by optimizing column permutations via mutation and selection.
Systematic Benchmarking: This is the first large-scale comparison of distance-finding methods across such a diverse set of code families and circuit types. It provides empirical data on which algorithms scale best for specific code structures (e.g., Tanner graph degree, CSS vs. non-CSS).
Block Representation Analysis: The paper analyzes how different binary representations of quantum codes (2-block symplectic, 3-block, 4-block) affect performance. They found that:
- 3-block representations often speed up Brouwer-Zimmermann and Connected Cluster methods.
- 2-block (symplectic) representations are often superior for MIP solvers (Gurobi).
Circuit Filtering: For syndrome extraction circuits, the authors introduced a DEM filtering algorithm that reduces the problem size by isolating specific error bases (X or Z), significantly improving the success rate of distance-finding algorithms on large circuits.
Open Source Release: All algorithms, test data, and the codeDistance package are made available to the community to facilitate future research.

4. Key Results

Exact Methods:
- Magma (Brouwer-Zimmermann): Best for small-to-medium classical and non-CSS quantum codes. It provides tight bounds even when terminated early.
- m4riCC (Connected Cluster): The fastest exact method for LDPC codes with low-degree Tanner graphs (e.g., Hyperbolic Surface/Colour codes).
- Gurobi (MIP): Generally outperforms SCIP and SAT solvers in processing time and provides robust bounds for large codes, especially when using 2-block representations.
Heuristic Methods:
- QDistEvol: Consistently achieved the highest success rates for high-rate LDPC codes (Lifted Product, Bivariate Bicycle, Quantum Tanner), often finding the true distance where random methods failed.
- BP-OSD: Competitive for large surface and colour codes but struggled with non-CSS and high-rate LDPC codes compared to QDistEvol.
- Stim Methods: Highly effective for topological codes with known error structures (e.g., Graphlike errors in Surface codes) but performed poorly on general LDPC codes where errors are not string-like.
Circuit Distance:
- Circuit-level distance is significantly harder than code distance.
- Filtering the Detector Error Model (DEM) is crucial for solving circuit distances.
- For Bivariate Bicycle circuits, exact methods often failed to return results within 8 hours, highlighting the need for robust heuristics like QDistEvol.

5. Significance

Accelerating Code Discovery: As the field moves toward fault-tolerant quantum computing with LDPC codes, the ability to rapidly and accurately estimate code distance is a bottleneck. This work provides a "toolkit" for researchers to select the optimal algorithm for their specific code family, filtering out unpromising candidates efficiently.
Circuit-Level Insights: By addressing the circuit distance problem (which includes measurement errors), the paper bridges the gap between theoretical code properties and practical hardware implementation.
Community Resource: The codeDistance package democratizes access to state-of-the-art distance-finding tools, allowing researchers to benchmark new code families without implementing complex solvers from scratch.
Guidance for Future Research: The results suggest that while exact methods are necessary for small codes, evolutionary heuristics (like QDistEvol) are currently the most viable path for evaluating the massive code families required for scalable quantum computers.

In summary, this paper establishes a new standard for evaluating quantum error correction protocols by providing a rigorous, data-driven comparison of distance-finding algorithms and releasing the necessary software infrastructure to the community.