Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1405.0348 · IEEE International Symposium on Information Theory (ISIT)

Numerical techniques for finding the distances of quantum codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

Published Jun 1, 2014• 8 citations
arXivHTMLPDF

Abstract

We survey the existing techniques for calculating code distances of classical codes and apply these techniques to generic quantum codes. For classical and quantum LDPC codes, we also present a new linked-cluster technique. It reduces complexity exponent of all existing deterministic techniques designed for codes with small relative distances (which include all known families of quantum LDPC codes), and also surpasses the probabilistic technique for sufficiently high code rates.

DOI
10.1109/isit.2014.6875000

Related papers

Linked-cluster technique for finding the distance of a quantum LDPC code

Alexey A. Kovalev, Ilya I. Dumer, Leonid P. Pryadko

We present a linked-cluster technique for calculating the distance of a quantum LDPC code. It offers an advantage over existing deterministic techniques for codes with small relative distances (which includes all known families of quantum LDPC codes), and over the probabilistic technique for codes with sufficiently high rates.

Information Theory and Applications Workshop (ITA)•Feb 1, 2013•2 citations

Distance-Finding Algorithms for Quantum Codes and Circuits

Mark Webster, Abraham Jacob, Oscar Higgott

The distance of a classical or quantum code is a key figure of merit which reflects its capacity to detect errors. Quantum LDPC code families have considerable promise in reducing the overhead required for fault-tolerant quantum computation, but calculating their distance is challenging with existing methods. We generally assess the performance of a quantum code under circuit level error models, and for such scenarios the circuit distance is an important consideration. Calculating circuit distance is in general more difficult than finding the distance of the corresponding code as the detector error matrix of the circuit is usually much larger than the code's check matrix. In this work, we benchmark a wide range of distance-finding methods for various classical and quantum code families, as well as syndrome-extraction circuits. We consider both exact methods (such as Brouwer-Zimmermann, connected cluster, SAT and mixed integer programming) and heuristic methods which have lower run-time but can only give a bound on distance (examples include random information set, syndrome decoder algorithms, and Stim undetectable error methods). We further develop the QDistEvol algorithm and show that it performs well for the quantum LDPC codes in our benchmark. The algorithms and test data have been made available to the community in the codeDistance Python package.

quant-pharXiv:2603.22532•Mar 25, 2026•0 citations

Linked-Cluster Technique for Finding the Distance of a Quantum LDPC Code

Alexey A. Kovalev, Ilya I. Dumer, Leonid P. Pryadko

We present a linked-cluster technique for calculating the distance of a quantum LDPC code. It offers an advantage over existing deterministic techniques for codes with small relative distances (which includes all known families of quantum LDPC codes), and over the probabilistic technique for codes with sufficiently high rates.

arXiv:1302.1845•Feb 7, 2013•0 citations

Distance verification for classical and quantum LDPC codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

The techniques of distance verification known for general linear codes are re-applied to quantum stabilizer codes. Then distance verification is addressed for classical and quantum LDPC codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of quantum LDPC codes.

arXiv:1611.07164•Nov 22, 2016•0 citations

Distance Verification for Classical and Quantum LDPC Codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

The techniques of distance verification known for general linear codes are first applied to the quantum stabilizer codes. Then, these techniques are considered for classical and quantum (stabilizer) low-density-parity-check (LDPC) codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both the classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of the quantum stabilizer LDPC codes.

IEEE Transactions on Information Theory•Mar 31, 2017•13 citations

Distance verification for LDPC codes

Ilya I. Dumer, Alexey A. Kovalev, Leonid P. Pryadko

The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.

arXiv:1605.02410•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•1 citation
We survey the existing techniques for calculating code distances of classical codes and apply these techniques to generic quantum codes. For classical and quantum LDPC codes, we also present a new linked-cluster technique. It reduces complexity exponent of all existing deterministic techniques designed for codes with small relative distances (which include all known families of quantum LDPC codes), and also surpasses the probabilistic technique for sufficiently high code rates.
The distance of a classical or quantum code is a key figure of merit which reflects its capacity to detect errors. Quantum LDPC code families have considerable promise in reducing the overhead required for fault-tolerant quantum computation, but calculating their distance is challenging with existing methods. We generally assess the performance of a quantum code under circuit level error models, and for such scenarios the circuit distance is an important consideration. Calculating circuit distance is in general more difficult than finding the distance of the corresponding code as the detector error matrix of the circuit is usually much larger than the code's check matrix. In this work, we benchmark a wide range of distance-finding methods for various classical and quantum code families, as well as syndrome-extraction circuits. We consider both exact methods (such as Brouwer-Zimmermann, connected cluster, SAT and mixed integer programming) and heuristic methods which have lower run-time but can only give a bound on distance (examples include random information set, syndrome decoder algorithms, and Stim undetectable error methods). We further develop the QDistEvol algorithm and show that it performs well for the quantum LDPC codes in our benchmark. The algorithms and test data have been made available to the community in the codeDistance Python package.
The techniques of distance verification known for general linear codes are re-applied to quantum stabilizer codes. Then distance verification is addressed for classical and quantum LDPC codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of quantum LDPC codes.
The techniques of distance verification known for general linear codes are first applied to the quantum stabilizer codes. Then, these techniques are considered for classical and quantum (stabilizer) low-density-parity-check (LDPC) codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both the classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of the quantum stabilizer LDPC codes.
The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.