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:2107.05174 · IEEE Transactions on Information Theory

Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically

Jihao Fan, Jun Li, Ya Wang, Yonghui Li, Min-Hsiu Hsieh, Jiangfeng Du

Published Aug 24, 2022• 6 citations
arXivHTMLPDF

Abstract

In this paper, we utilize a concatenation scheme to construct new families of quantum error correction codes achieving the quantum Gilbert-Varshamov (GV) bound asymptotically. Weconcatenate alternant codes with any linear code achievingthe classical GV bound to construct Calderbank-Shor-Steane (CSS) codes. We show that the concatenated code can achieve the quantum GV bound asymptotically and can approach the Hashing bound for asymmetric Pauli channels. By combing Steane’s enlargement construction of CSS codes, we derive a family of enlarged stabilizer codes achieving the quantum GV bound for enlarged CSS codes asymptotically. Asapplications, we derive two families of fast encodable and decodable CSS codes with parameters$\mathscr {Q}_{1}=[[N,\Omega (\sqrt {N}),\Omega (\sqrt {N})]]$, and$\mathscr {Q}_{2}=[[N,\Omega (N/\log N),\Omega (N/\log N)/\Omega (\log N)]]$. We show that$\mathscr {Q}_{1}$can be encoded very efficiently by circuits of size$O(N)$and depth$O(\sqrt {N})$. For an input error syndrome,$\mathscr {Q}_{1}$can correct any adversarial error of weight up to half the minimum distance bound in$O(N)$time.$\mathscr {Q}_{1}$can also be decoded in parallel in$O(\sqrt {N})$time by using$O(\sqrt {N})$classical processors. For an input error syndrome, we proved that$\mathscr {Q}_{2}$can correct a linear number of${X}$-errors with high probability and an almost linear number of${Z}$-errors in$O(N)$time. Moreover,$\mathscr {Q}_{2}$can be decoded in parallel in$O(\log (N))$time by using$O(N)$classical processors.

DOI
10.1109/tit.2022.3201239

Related papers

Concatenated Quantum Codes Constructible in Polynomial Time: Efficient Decoding and Error Correction

Mitsuru Hamada

A method for concatenating quantum error-correcting codes is presented. The method is applicable to a wide class of quantum error-correcting codes known as Calderbank-Shor-Steane (CSS) codes. As a result, codes that achieve a high rate in the Shannon-theoretic sense and that are decodable in polynomial time are presented. The rate is the highest among those known to be achievable by CSS codes. Moreover, the best known lower bound on the greatest minimum distance of codes constructible in polynomial time is improved for a wide range.

arXiv:quant-ph/0610195•IEEE Transactions on Information Theory•Dec 1, 2008•54 citations

From Generalization of Bacon-Shor Codes to High Performance Quantum LDPC Codes

Jihao Fan, Jun Li, Ya Wang +3 more

Abstract We utilize a concatenation scheme to construct new families of quantum error correction codes that include the Bacon-Shor codes. We show that our scheme can lead to asymptotically good quantum codes while Bacon-Shor codes cannot. Further, the concatenation scheme allows us to derive quantum LDPC codes of distance Ω(N2/3/loglogN) which can improve Hastings’s recent result [arXiv:2102.10030] by a polylogarithmic factor. Moreover, assisted by the Evra-Kaufman- Zémor distance balancing construction, our concatenation scheme can yield quantum LDPC codes with non-vanishing code rates and better minimum distance upper bound than the hypergraph product quantum LDPC codes. Finally, we derive a family of fast encodable and decodable quan- tum concatenated codes with parameters Q = [[N,Ω(√N),Ω(√N)]] and they also belong to the Bacon-Shor codes. We show that Q can be encoded very efficiently by circuits of size O(N) and depth O(√N), and can correct any adversarial error of weight up to half the minimum distance bound in O(√N) time. To the best of our knowledge, they are the most powerful quantum codes for correcting so many adversarial errors in sublinear time by far.

•Jul 13, 2021•2 citations

Achievability of CSS codes performance limits over Pauli channels under separate ML decoding with bounded graphical complexity

Gulnihal Mercanoglu, Achilleas Anastasopoulos, S. Sandeep Pradhan

Capacity-approaching quantum error correction faces a fundamental tension: the required parity-check matrices need to become increasingly dense, while practical decoding and syndrome extraction favor sparse, bounded-degree structures. Reconciling these competing requirements remains an important open problem in quantum code design. We construct Calderbank-Shor-Steane (CSS) code ensembles that approach the CSS rate over memoryless Pauli channels under maximum-likelihood decoding while retaining sparse, bounded-degree graphical representations. The construction separates parity-check density from graphical complexity: although capacity-approaching components may require dense parity-check matrices, they are represented by sparse concatenated factor graphs. We first study a construction combining low-density parity-check (LDPC) and low-density generator-matrix (LDGM) component codes and numerically analyze the average weight distributions of the resulting codes. Motivated by these results, we introduce a second construction based on concatenated LDPC and LDGM codes and generalized irregular repeat-accumulate (GIRA) codes. We derive bounds on the average weight distribution of the resulting sum ensemble and use the Miller-Burshtein framework to prove simultaneous reliability of the two CSS decoding components. Consequently, the proposed ensemble achieves rates arbitrarily close to the CSS hashing bound under separate bit- and phase-error correction, while maintaining bounded graphical complexity, thus providing a foundation for future iterative decoders and indirect syndrome-extraction architectures.

cs.ITCross-listedarXiv:2611.02339•Nov 3, 2026•0 citations

Neural Belief Propagation Decoders for Concatenated Calderbank-Shor-Steane Codes

Jihao Fan, Jinbing Zhang

Quantum low-density parity check (QLDPC) codes have rapidly developed in the field of quantum error correction in recent years. A variety of quantum code families have emerged from numerous research activities. In this paper, we employ concatenated Calderbank-Shor-Steane (CSS) codes, hypergraph product codes, and Bacon-Shor codes to train belief-propagation (BP) and neural BP (NBP) decoders. At the same time, we employ a concatenation scheme in BP and NBP, the amplified construction of CSS codes is realized, and the training of longer length parameter quantum codes is realized. The numerical results show that the concatenated CSS codes demonstrate better error correction performance compared to both hypergraph product codes and Bacon-Shor codes. In addition, the concatenated CSS codes are trained using the concatenation scheme to improve the error correction performance of the decoder.

International Conference on Communications•Jun 9, 2024•1 citation

Quantum error correcting codes based on privacy amplification

Zhicheng Luo

Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.

arXiv:0808.1392•Aug 10, 2008•2 citations

Finite-Degree Quantum LDPC Codes Reaching the Gilbert-Varshamov Bound

Kenta Kasai

We construct asymptotically good nested Calderbank-Shor-Steane (CSS) code pairs from Hsu-Anastasopoulos codes and MacKay-Neal codes. For fixed balanced triples with even component degrees and $j_Z\ge4$, we prove that the coding rate stays bounded away from zero and that the relative distances on both sides stay bounded away from zero with probability tending to one as the blocklength grows. Moreover, within an explicit low-degree search window, we prove that all 56 balanced triples in that window with even common row degree, column degree at least four, and positive design quantum rate attain the classical Gilbert-Varshamov (GV) bound on both constituent sides, and consequently the CSS GV bound at fixed finite degree.

quant-pharXiv:2603.24588•Mar 26, 2026•8 citations
In this paper, we utilize a concatenation scheme to construct new families of quantum error correction codes achieving the quantum Gilbert-Varshamov (GV) bound asymptotically. Weconcatenate alternant codes with any linear code achievingthe classical GV bound to construct Calderbank-Shor-Steane (CSS) codes. We show that the concatenated code can achieve the quantum GV bound asymptotically and can approach the Hashing bound for asymmetric Pauli channels. By combing Steane’s enlargement construction of CSS codes, we derive a family of enlarged stabilizer codes achieving the quantum GV bound for enlarged CSS codes asymptotically. Asapplications, we derive two families of fast encodable and decodable CSS codes with parametersQ1=[[N,Ω(N),Ω(N)]]\mathscr {Q}_{1}=[[N,\Omega (\sqrt {N}),\Omega (\sqrt {N})]]Q1​=[[N,Ω(N​),Ω(N​)]], andQ2=[[N,Ω(N/log⁡N),Ω(N/log⁡N)/Ω(log⁡N)]]\mathscr {Q}_{2}=[[N,\Omega (N/\log N),\Omega (N/\log N)/\Omega (\log N)]]Q2​=[[N,Ω(N/logN),Ω(N/logN)/Ω(logN)]]. We show thatQ1\mathscr {Q}_{1}Q1​can be encoded very efficiently by circuits of sizeO(N)O(N)O(N)and depthO(N)O(\sqrt {N})O(N​). For an input error syndrome,Q1\mathscr {Q}_{1}Q1​can correct any adversarial error of weight up to half the minimum distance bound inO(N)O(N)O(N)time.Q1\mathscr {Q}_{1}Q1​can also be decoded in parallel inO(N)O(\sqrt {N})O(N​)time by usingO(N)O(\sqrt {N})O(N​)classical processors. For an input error syndrome, we proved thatQ2\mathscr {Q}_{2}Q2​can correct a linear number ofX{X}X-errors with high probability and an almost linear number ofZ{Z}Z-errors inO(N)O(N)O(N)time. Moreover,Q2\mathscr {Q}_{2}Q2​can be decoded in parallel inO(log⁡(N))O(\log (N))O(log(N))time by usingO(N)O(N)O(N)classical processors.
A method for concatenating quantum error-correcting codes is presented. The method is applicable to a wide class of quantum error-correcting codes known as Calderbank-Shor-Steane (CSS) codes. As a result, codes that achieve a high rate in the Shannon-theoretic sense and that are decodable in polynomial time are presented. The rate is the highest among those known to be achievable by CSS codes. Moreover, the best known lower bound on the greatest minimum distance of codes constructible in polynomial time is improved for a wide range.
Abstract We utilize a concatenation scheme to construct new families of quantum error correction codes that include the Bacon-Shor codes. We show that our scheme can lead to asymptotically good quantum codes while Bacon-Shor codes cannot. Further, the concatenation scheme allows us to derive quantum LDPC codes of distance Ω(N2/3/loglogN) which can improve Hastings’s recent result [arXiv:2102.10030] by a polylogarithmic factor. Moreover, assisted by the Evra-Kaufman- Zémor distance balancing construction, our concatenation scheme can yield quantum LDPC codes with non-vanishing code rates and better minimum distance upper bound than the hypergraph product quantum LDPC codes. Finally, we derive a family of fast encodable and decodable quan- tum concatenated codes with parameters Q = [[N,Ω(√N),Ω(√N)]] and they also belong to the Bacon-Shor codes. We show that Q can be encoded very efficiently by circuits of size O(N) and depth O(√N), and can correct any adversarial error of weight up to half the minimum distance bound in O(√N) time. To the best of our knowledge, they are the most powerful quantum codes for correcting so many adversarial errors in sublinear time by far.
Capacity-approaching quantum error correction faces a fundamental tension: the required parity-check matrices need to become increasingly dense, while practical decoding and syndrome extraction favor sparse, bounded-degree structures. Reconciling these competing requirements remains an important open problem in quantum code design. We construct Calderbank-Shor-Steane (CSS) code ensembles that approach the CSS rate over memoryless Pauli channels under maximum-likelihood decoding while retaining sparse, bounded-degree graphical representations. The construction separates parity-check density from graphical complexity: although capacity-approaching components may require dense parity-check matrices, they are represented by sparse concatenated factor graphs. We first study a construction combining low-density parity-check (LDPC) and low-density generator-matrix (LDGM) component codes and numerically analyze the average weight distributions of the resulting codes. Motivated by these results, we introduce a second construction based on concatenated LDPC and LDGM codes and generalized irregular repeat-accumulate (GIRA) codes. We derive bounds on the average weight distribution of the resulting sum ensemble and use the Miller-Burshtein framework to prove simultaneous reliability of the two CSS decoding components. Consequently, the proposed ensemble achieves rates arbitrarily close to the CSS hashing bound under separate bit- and phase-error correction, while maintaining bounded graphical complexity, thus providing a foundation for future iterative decoders and indirect syndrome-extraction architectures.
Quantum low-density parity check (QLDPC) codes have rapidly developed in the field of quantum error correction in recent years. A variety of quantum code families have emerged from numerous research activities. In this paper, we employ concatenated Calderbank-Shor-Steane (CSS) codes, hypergraph product codes, and Bacon-Shor codes to train belief-propagation (BP) and neural BP (NBP) decoders. At the same time, we employ a concatenation scheme in BP and NBP, the amplified construction of CSS codes is realized, and the training of longer length parameter quantum codes is realized. The numerical results show that the concatenated CSS codes demonstrate better error correction performance compared to both hypergraph product codes and Bacon-Shor codes. In addition, the concatenated CSS codes are trained using the concatenation scheme to improve the error correction performance of the decoder.
Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.
We construct asymptotically good nested Calderbank-Shor-Steane (CSS) code pairs from Hsu-Anastasopoulos codes and MacKay-Neal codes. For fixed balanced triples with even component degrees and jZ≥4j_Z\ge4jZ​≥4, we prove that the coding rate stays bounded away from zero and that the relative distances on both sides stay bounded away from zero with probability tending to one as the blocklength grows. Moreover, within an explicit low-degree search window, we prove that all 56 balanced triples in that window with even common row degree, column degree at least four, and positive design quantum rate attain the classical Gilbert-Varshamov (GV) bound on both constituent sides, and consequently the CSS GV bound at fixed finite degree.