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:2411.02928 · Physical Review Research

Almost linear decoder for optimal geometrically local quantum codes

Quinten Eggerickx, Adam Wills, Ting-Chun Lin, Kristiaan De Greve, Min-Hsiu Hsieh

Published May 12, 2025• 2 citations
arXivHTMLPDF

Abstract

Geometrically local quantum codes, which are error-correction codes embedded in R D with checks acting only on qubits within a fixed spatial distance, have garnered significant interest. Recently, it has been demonstrated how to achieve geometrically local codes that maximize both the dimension and the distance, as well as the energy barrier of the code. In this work, we focus on the constructions involving subdivision, and we show that they have an almost linear time decoder, obtained by combining the decoder of the outer good qLDPC code and a generalized version of the Union-Find decoder. This provides the first decoder for an optimal geometrically local three-dimensional code. We demonstrate the existence of a finite threshold error rate under the code capacity noise model using a minimum weight perfect matching decoder. Furthermore, we argue that this threshold is also applicable to the decoder based on the generalized Union-Find algorithm.

DOI
10.1103/sxdx-qbcz

Related papers

Geometrically Local Quantum and Classical Codes from Subdivision

Ting-Chun Lin, Adam Wills, Min-Hsiu Hsieh

A geometrically local quantum code is an error correcting code situated within $\mathbb{R}^D$, where the checks only act on qubits within a fixed spatial distance. The main question is: What is the optimal dimension and distance for a geometrically local code? Recently, Portnoy made a significant breakthrough with codes achieving optimal dimension and distance up to polylogs. However, the construction invokes a somewhat advanced mathematical result that involves lifting a chain complex to a manifold. This paper bypasses this step and streamlines the construction by noticing that a family of good quantum low-density parity-check codes, balanced product codes, naturally carries a two-dimensional structure. Together with a new embedding result that will be shown elsewhere, this quantum code achieves the optimal dimension and distance in all dimensions. In addition, we show that the code has an optimal energy barrier. We also discuss similar results for classical codes.

arXiv:2309.16104•Sep 28, 2023•1 citation

Transform Arbitrary Good Quantum LDPC Codes into Good Geometrically Local Codes in Any Dimension

Xingjian Li, Ting-Chun Lin, Min-Hsiu Hsieh

Geometrically local quantum codes, comprised of qubits and checks embedded in $\mathbb{R}^D$ with local check operators, have been a subject of significant interest. A key challenge is identifying the optimal code construction that maximizes both dimension and distance. Recent advancements have produced several constructions, but these either depend on specific good quantum low-density parity-check (qLDPC) codes or are limited to three dimensions. In this work, we introduce a construction that can transform any good qLDPC code into an optimal geometrically local quantum code. Our approach hinges on a novel procedure that extracts a two-dimensional structure from an arbitrary three-term chain complex. We expect that this procedure will find broader applications in areas such as weight reduction and the geometric realization of chain complexes.

arXiv:2408.01769•Aug 3, 2024•0 citations

An Efficient Decoder for a Linear Distance Quantum LDPC Code

Shouzhen Gu, Christopher A. Pattison, Eugene Tang

Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.

arXiv:2206.06557•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•27 citations

Quantum Error Correction: Decoders for the Toric Code

Nando Leijenhorst

Quantum error correction is needed for future quantum computers. Classical error correcting codes are not suitable for this due to the nature of quantum mechanics. Therefore, new codes need to be developed. A promising candidate is the toric code, a surface code, because of its locality and its high error correcting capability and thresholds (the error probability below which increasing the size of the code decreases the failure rate). This thesis provides an introduction to quantum error correction and the stabilizer formalism, which is used to introduce the toric code. Several decoders are looked at, including the Minimum Weight Perfect Matching (MWPM) decoder and a recently developed decoder, the Union-Find (UF) decoder. The UF decoder is useful because of its almost-linear time complexity, while only reducing the threshold by a marginal amount compared to the MWPM decoder. In this thesis, the time complexity of the weighted growth version of the UF decoder is analysed. The toric code and the decoders have been implemented and simulated, and the thresholds have been determined. For the MWPM decoder, the threshold was determined to be 11.5±0.2%, which is not in agreement with the threshold in literature of 10.3%, and should not be possible according to the optimal threshold of about 11%. This probably is a result of the low grid sizes (up to a gridsize of 11) of the code used due to the time needed to simulate the MWPM decoder. For the UF decoder, the threshold found was 9.7 ± 0.9%, which is in agreement with the threshold of 9.9% found by N. Delfosse and N. Nickerson. The time complexity of the UF decoder has also been determined, and is indeed almost-linear as expected by the analysis.

•Jan 1, 2019•1 citation

Almost optimal geometrically local quantum LDPC codes in any dimension

Xingjian Li, Ting-Chun Lin, Adam Wills +1 more

with local check operators, have been a subject of significant interest. A key challenge is identifying the optimal code construction that maximizes both code dimension and distance under the geometric constraints. In this work, we introduce a construction that can transform any good quantum LDPC code into an almost optimal geometrically local quantum code. Our approach hinges on a novel yet simple procedure that extracts a two-dimensional structure from an arbitrary three-term chain complex, building a connection between geometric operations and code constructions. We expect that this procedure will find broader applications in areas such as weight reduction and the geometric realization of chain complexes.

Nature Communications•Feb 5, 2026•0 citations

Partial Self-Correction in Layer Codes

Dominic J. Williamson

The storage of large-scale quantum information at finite temperature requires an autonomous and reliable quantum hard drive, also known as a self-correcting quantum memory. It is a long-standing open problem to find a self-correcting quantum memory in three dimensions. The recently introduced Layer Codes achieve the best possible scaling of code parameters and logical energy barrier in three dimensions, these are tantalizing features for the purposes of self-correction. In this work we show that a family of Layer Codes, based on good Quantum Tanner Codes, exhibit partial self-correction. Their memory time grows exponentially with linear system size, up to a length scale that is exponential in the inverse temperature. At this length scale, the memory time scales as a double exponential of inverse temperature. To establish this result we introduce a concatenated matching decoder that combines three rounds of parallelized minimum-weight perfect-matching with a decoder for good Quantum Tanner Codes. We show that our decoder corrects errors up to a constant fraction of the energy barrier, and a constant fraction of the code distance, for a family of Layer Codes. Our results position Layer Codes as the leading candidate for a partially self-correcting memory in three dimensions. While they fall short of achieving strict self-correction in the thermodynamic limit, our work highlights the potential of these local codes in three dimensions, with fast distance and logical qubit growth, fast decoders, and a long memory time over a wide range of parameters.

arXiv:2510.09218•Oct 10, 2025•0 citations
Geometrically local quantum codes, which are error-correction codes embedded in R D with checks acting only on qubits within a fixed spatial distance, have garnered significant interest. Recently, it has been demonstrated how to achieve geometrically local codes that maximize both the dimension and the distance, as well as the energy barrier of the code. In this work, we focus on the constructions involving subdivision, and we show that they have an almost linear time decoder, obtained by combining the decoder of the outer good qLDPC code and a generalized version of the Union-Find decoder. This provides the first decoder for an optimal geometrically local three-dimensional code. We demonstrate the existence of a finite threshold error rate under the code capacity noise model using a minimum weight perfect matching decoder. Furthermore, we argue that this threshold is also applicable to the decoder based on the generalized Union-Find algorithm.
A geometrically local quantum code is an error correcting code situated within RD\mathbb{R}^DRD, where the checks only act on qubits within a fixed spatial distance. The main question is: What is the optimal dimension and distance for a geometrically local code? Recently, Portnoy made a significant breakthrough with codes achieving optimal dimension and distance up to polylogs. However, the construction invokes a somewhat advanced mathematical result that involves lifting a chain complex to a manifold. This paper bypasses this step and streamlines the construction by noticing that a family of good quantum low-density parity-check codes, balanced product codes, naturally carries a two-dimensional structure. Together with a new embedding result that will be shown elsewhere, this quantum code achieves the optimal dimension and distance in all dimensions. In addition, we show that the code has an optimal energy barrier. We also discuss similar results for classical codes.
Geometrically local quantum codes, comprised of qubits and checks embedded in RD\mathbb{R}^DRD with local check operators, have been a subject of significant interest. A key challenge is identifying the optimal code construction that maximizes both dimension and distance. Recent advancements have produced several constructions, but these either depend on specific good quantum low-density parity-check (qLDPC) codes or are limited to three dimensions. In this work, we introduce a construction that can transform any good qLDPC code into an optimal geometrically local quantum code. Our approach hinges on a novel procedure that extracts a two-dimensional structure from an arbitrary three-term chain complex. We expect that this procedure will find broader applications in areas such as weight reduction and the geometric realization of chain complexes.
Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.
Quantum error correction is needed for future quantum computers. Classical error correcting codes are not suitable for this due to the nature of quantum mechanics. Therefore, new codes need to be developed. A promising candidate is the toric code, a surface code, because of its locality and its high error correcting capability and thresholds (the error probability below which increasing the size of the code decreases the failure rate). This thesis provides an introduction to quantum error correction and the stabilizer formalism, which is used to introduce the toric code. Several decoders are looked at, including the Minimum Weight Perfect Matching (MWPM) decoder and a recently developed decoder, the Union-Find (UF) decoder. The UF decoder is useful because of its almost-linear time complexity, while only reducing the threshold by a marginal amount compared to the MWPM decoder. In this thesis, the time complexity of the weighted growth version of the UF decoder is analysed. The toric code and the decoders have been implemented and simulated, and the thresholds have been determined. For the MWPM decoder, the threshold was determined to be 11.5±0.2%, which is not in agreement with the threshold in literature of 10.3%, and should not be possible according to the optimal threshold of about 11%. This probably is a result of the low grid sizes (up to a gridsize of 11) of the code used due to the time needed to simulate the MWPM decoder. For the UF decoder, the threshold found was 9.7 ± 0.9%, which is in agreement with the threshold of 9.9% found by N. Delfosse and N. Nickerson. The time complexity of the UF decoder has also been determined, and is indeed almost-linear as expected by the analysis.
with local check operators, have been a subject of significant interest. A key challenge is identifying the optimal code construction that maximizes both code dimension and distance under the geometric constraints. In this work, we introduce a construction that can transform any good quantum LDPC code into an almost optimal geometrically local quantum code. Our approach hinges on a novel yet simple procedure that extracts a two-dimensional structure from an arbitrary three-term chain complex, building a connection between geometric operations and code constructions. We expect that this procedure will find broader applications in areas such as weight reduction and the geometric realization of chain complexes.
The storage of large-scale quantum information at finite temperature requires an autonomous and reliable quantum hard drive, also known as a self-correcting quantum memory. It is a long-standing open problem to find a self-correcting quantum memory in three dimensions. The recently introduced Layer Codes achieve the best possible scaling of code parameters and logical energy barrier in three dimensions, these are tantalizing features for the purposes of self-correction. In this work we show that a family of Layer Codes, based on good Quantum Tanner Codes, exhibit partial self-correction. Their memory time grows exponentially with linear system size, up to a length scale that is exponential in the inverse temperature. At this length scale, the memory time scales as a double exponential of inverse temperature. To establish this result we introduce a concatenated matching decoder that combines three rounds of parallelized minimum-weight perfect-matching with a decoder for good Quantum Tanner Codes. We show that our decoder corrects errors up to a constant fraction of the energy barrier, and a constant fraction of the code distance, for a family of Layer Codes. Our results position Layer Codes as the leading candidate for a partially self-correcting memory in three dimensions. While they fall short of achieving strict self-correction in the thermodynamic limit, our work highlights the potential of these local codes in three dimensions, with fast distance and logical qubit growth, fast decoders, and a long memory time over a wide range of parameters.