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

NATO science for peace and security series. D, Information and communication security

Finding error-correcting codes using computers

Lam Clement

Published Jan 1, 2011• 3 citations
Publisher

Abstract

The theory of error-correcting codes is a vast and fast-moving area with many open problems. The objective of this paper is to survey where the current boundaries of knowledge are in a few selected areas, by listing the smallest unsolved cases. Our hope is that these lists will motivate further computational to move these boundaries.
DOI
10.3233/978-1-60750-663-8-278

Related papers

Error Correcting Codes

Peter M Kosek

Error correcting codes is an area of mathematics that combines many theoretical concepts with a wide variety of applications.In this expository thesis, we will begin by introducing many of the fundamental ideas in classical error correcting codes.The goal of this is to introduce the reader to the field of coding theory and discuss a few of the wide range of classical codes that have been studied.The second section will discuss the recent findings in error correcting codes, namely their use in quantum error correcting codes.This section uses much more theoretical areas of math, when compared to the classical section, in the construction of quantum error correcting codes.Most of the research discussed in this section has been completed within the past six years.All of the research discoveries presented in this thesis have been previously known.

•Jan 1, 2014•0 citations

A Fast Polar Code List Decoder Architecture Based on Sphere Decoding

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

Polar codes are a recently discovered family of capacity-achieving error-correcting codes. Among the proposed decoding algorithms, successive-cancellation list decoding guarantees the best error-correction performance with codes of moderate lengths, but it yields low throughput. Speed-up techniques have been proposed in the past: most of them rely on approximations that degrade the error-correction capability of the algorithm. We propose a speed-up technique for successive-cancellation list decoding of polar codes that is exact for list size of 2, while its approximations bring negligible error-correction performance degradation (<;0.05 dB) for other list sizes. A decoder architecture is designed: the proposed technique increases the throughput of a factor of 3.16×, at the cost of 14.2% in area occupation.

IEEE Transactions on Circuits and Systems I Regular Papers•Nov 14, 2016•100 citations

Improved Decoding of Circuit Noise and Fragile Boundaries of Tailored Surface Codes

Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica +2 more

Realizing the full potential of quantum computation requires quantum error correction (QEC), with most recent breakthrough demonstrations of QEC using the surface code.QEC codes use multiple noisy physical qubits to encode information in fewer logical qubits, enabling the identification of errors through a decoding process.This process increases the logical fidelity (or accuracy) making the computation more reliable.However, most fast (efficient run-time) decoders neglect important noise characteristics, thereby reducing their accuracy.In this work, we introduce decoders that are both fast and accurate, and can be used with a wide class of QEC codes including the surface code.Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC.Using the surface code threshold as a performance metric, we observe a threshold at 0.94% error probability for our decoders, outperforming the 0.82% threshold for a standard minimum-weight perfect matching decoder.We also test our belief-matching decoders in a theoretical case study of codes tailored to a biased noise model.We find that the decoders lead to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.Surprisingly, in the wellbelow-threshold regime, the rectangular surface code becomes more resource efficient than the tailored surface code due to a previously unnoticed phenomenon that we call "fragile boundaries."Our decoders outperform all other fast decoders in terms of threshold and accuracy, enabling better results in current quantum-error-correction experiments and opening up new areas for theoretical case studies.

arXiv:2203.04948•Physical Review X•Jul 19, 2023•84 citations

Introduction to the theory of error-correcting codes (third edition)

Computers & Mathematics with Applications•Oct 1, 1998•0 citations

Introduction to the Theory of Error‐Correcting Codes

Vera S. Pless

Wiley eBooks•Jun 18, 1998•170 citations

Fast Successive-Cancellation List Flip Decoding of Polar Codes

Nghia Doan, Seyyed Ali Hashemi, Warren J. Gross

This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.

arXiv:2109.12239•IEEE Access•Jan 1, 2022•8 citations
Error correcting codes is an area of mathematics that combines many theoretical concepts with a wide variety of applications.In this expository thesis, we will begin by introducing many of the fundamental ideas in classical error correcting codes.The goal of this is to introduce the reader to the field of coding theory and discuss a few of the wide range of classical codes that have been studied.The second section will discuss the recent findings in error correcting codes, namely their use in quantum error correcting codes.This section uses much more theoretical areas of math, when compared to the classical section, in the construction of quantum error correcting codes.Most of the research discussed in this section has been completed within the past six years.All of the research discoveries presented in this thesis have been previously known.
Polar codes are a recently discovered family of capacity-achieving error-correcting codes. Among the proposed decoding algorithms, successive-cancellation list decoding guarantees the best error-correction performance with codes of moderate lengths, but it yields low throughput. Speed-up techniques have been proposed in the past: most of them rely on approximations that degrade the error-correction capability of the algorithm. We propose a speed-up technique for successive-cancellation list decoding of polar codes that is exact for list size of 2, while its approximations bring negligible error-correction performance degradation (<;0.05 dB) for other list sizes. A decoder architecture is designed: the proposed technique increases the throughput of a factor of 3.16×, at the cost of 14.2% in area occupation.
Realizing the full potential of quantum computation requires quantum error correction (QEC), with most recent breakthrough demonstrations of QEC using the surface code.QEC codes use multiple noisy physical qubits to encode information in fewer logical qubits, enabling the identification of errors through a decoding process.This process increases the logical fidelity (or accuracy) making the computation more reliable.However, most fast (efficient run-time) decoders neglect important noise characteristics, thereby reducing their accuracy.In this work, we introduce decoders that are both fast and accurate, and can be used with a wide class of QEC codes including the surface code.Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC.Using the surface code threshold as a performance metric, we observe a threshold at 0.94% error probability for our decoders, outperforming the 0.82% threshold for a standard minimum-weight perfect matching decoder.We also test our belief-matching decoders in a theoretical case study of codes tailored to a biased noise model.We find that the decoders lead to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.Surprisingly, in the wellbelow-threshold regime, the rectangular surface code becomes more resource efficient than the tailored surface code due to a previously unnoticed phenomenon that we call "fragile boundaries."Our decoders outperform all other fast decoders in terms of threshold and accuracy, enabling better results in current quantum-error-correction experiments and opening up new areas for theoretical case studies.
This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.