Construction and Decoding of Quantum Margulis Codes
Michele Pacenti, Dimitris Chytas, Bane Vasić · 2025
Read Construction and Decoding of Quantum Margulis Codes by Michele Pacenti, Dimitris Chytas, Bane Vasić (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03936.txt.
Introduction
Michele Pacenti, Dimitris Chytas, and Bane Vasić build, in 2025 work, a fresh class of quantum error codes. Quantum machines need codes that catch faults, and sparse graph codes lead the field. Their codes grow from a known sparse plan, set in a two-block algebra frame, which sets them apart from the bicycle codes in wide use.
The shape of their code's graph lacks the mirror traits that breed a known flaw in decoding rivals. As a result, a plain fast decoder does the whole job, with work that grows in line with code size. A new build rule also sets the graph's ring length at six or eight, which firms the codes up. Tests on codes of a few hundred bits beat the rivals in the floor zone, where errors are rare.
Catalog record
| CREATOR | Michele Pacenti, Dimitris Chytas, Bane Vasić |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-03936
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Construction and Decoding of Quantum Margulis Codes Thanks: Part of this work was presented at the 60th Annual Allerton Conference on Communication, Control, and Computing, in Urbana, IL, USA, September 2024. This work is supported by the NSF under grants CCF-2420424, CIF-2106189, CCF-2100013, ECCS/CCSS-2027844, ECCS/CCSS-2052751, and in part by the CoQREATE program under grant ERC-1941583. Bane Vasić has disclosed an outside interest in his startup company Codelucida to The University of Arizona. Conflicts of interest resulting from this interest are being managed by The University of Arizona in accordance with its policies. Michele Pacenti, Dimitris Chytas, Bane Vasić Abstract Quantum low-density parity-check codes are a promising approach to fault-tolerant quantum computation, offering potential advantages in rate and decoding efficiency. In this work, we introduce quantum Margulis codes, a new class of QLDPC codes derived from Margulis’ classical LDPC construction via the two-block group algebra framework. We show that quantum Margulis codes, unlike bivariate bicycle codes which require ordered statistics decoding for effective error correction, can be efficiently decoded using a standard min-sum decoder with linear complexity, when decoded under depolarizing noise. This is attributed to their Tanner graph structure, which does not exhibit group symmetry, thereby mitigating the well-known problem of error degeneracy in QLDPC decoding. To further enhance performance, we propose an algorithm for constructing 2BGA codes with controlled girth, ensuring a minimum girth of 6 or 8, and use it to generate several quantum Margulis codes of length 240 and 642. We validate our approach through numerical simulations, demonstrating that quantum Margulis codes behave significantly better than BB codes in the error floor region, under min-sum decoding. 1 Introduction In the past years, the existence of asymptotically good quantum LDPC codes has been established [ 1 , 2 , 3 ] . However, their practical applicability remains uncertain, particularly in the finite-length regime. Recently, a class of codes known as bivariate bicycle (BB) codes [ 4 ] was introduced and tested in an experimental fault-tolerant setup. BB codes belong to the broader class of generalized bicycle (GB) codes [ 5 ] , which are constructed from pairs of circulant matrices. While GB codes lack the strong asymptotic properties of those in [ 1 , 2 , 3 ] , their suitability for hardware implementation, along with favorable minimum distance and code rate at finite blocklengths, motivates further investigation. Building on GB codes, a more general framework known as two-block group algebra (2BGA) codes was recently proposed [ 6 ] . These codes are defined through parity-check matrices derived from the Cayley graphs of certain groups. Notably, GB codes emerge as a special case of this construction. The authors of [ 6 ] provided minimum distance bounds and enumerated all 2BGA codes with optimal parameters (up to permutation equivalence) for blocklengths below 200, demonstrating that their minimum distance scales with the square root of the blocklength. The groups considered in these constructions include direct and semidirect products of cyclic and dihedral groups. We observe that the 2BGA framework naturally extends Margulis’ classical LDPC construction [ 7 ] to quantum codes. The classical counterparts of these codes achieve a rate of R=1/2 , with parity-check matrices structured as two square blocks corresponding to the incidence matrices of Cayley graphs of the special linear group SL(2,\mathbb{Z}) . In this work, we revisit 2BGA codes and introduce their construction through the left-right Cayley complex , highlighting their connections to other quantum LDPC families, such as lifted product (LP) codes [ 1 ] and quantum Tanner codes [ 2 ] , both of which rely on similar algebraic tools. Through group-theoretic analysis, we demonstrate that, under specific conditions, the group defining a 2BGA code is a subgroup of the automorphism group of its Tanner graph. While this structure has implications for fault-tolerant logical operations [ 8 ] , our focus is on its impact on decoding performance. We conjecture that QLDPC codes with weaker symmetries 1 1 1 By weak symmetry we informally mean that the order of the graph automorphism group is small. perform better under message-passing decoding. Empirical results support this hypothesis, showing that quantum Margulis codes achieve BB-like error rates without requiring ordered statistics decoding (OSD) when decoding on the depolarizing channel. This allows them to be decoded with linear complexity \mathcal{O}(n) , in contrast to BB codes, which typically require \mathcal{O}(n^{3}) . More broadly, this suggests that designing Tanner graphs with a low degree of symmetry could mitigate the performance degradation due to error degeneracy in message-passing decoders. Since decoder performance is also heavily influenced by the Tanner graph’s girth, we develop an algorithm to generate 2BGA codes with controlled girth (up to 8). In this paper, we focus on a specific subclass of 2BGA codes, the quantum Margulis codes [ 9 ] , and apply our algorithm to construct several instances, including codes of length 240 with girth 6, and length 642 with girth 8. Finally, we evaluate their decoding performance under min-sum (MS) decoding with depolarizing noise through numerical simulations, and show that they perform much better than BB codes when decoded with the same decoder. Finally, we compare the performance of quantum Margulis codes and BB codes under circuit-level noise. All the codes constructed in this paper are available on GitHub [ 10 ] . The remainder of this paper is organized as follows. In Section 2 , we provide the necessary preliminaries. Section 3 introduces the (2BGA) code construction. Section 4 presents the construction of quantum Margulis codes, starting with a review of the classical Margulis construction and extending it to the quantum domain. In Section 5 , we describe an algorithm for constructing 2BGA codes with desired girth. Section 6 analyzes the decoding of quantum Margulis codes using message-passing algorithms and investigates the impact of graph symmetries on decoding efficiency. Section 7 provides numerical results on the performance of quantum Margulis codes. Finally, Section 8 concludes the paper with a discussion of key findings and potential directions for future research. 2 Preliminaries 2.1 CSS codes, Tanner graphs, Cayley graphs Let \mathbb{F}_{2}^{n} be the field of the binary vectors of length n ; the Hamming weight (or simply weight) of an element in \mathbb{F}_{2}^{n} is the number of its non-zero entries, and we denote it with |.| ; we will use the same notation to indicate the cardinality of a set, with the intended meaning clear from context. An [n,k,d] linear code C\subset\mathbb{F}_{2}^{n} is a linear subspace of \mathbb{F}_{2}^{n} generated by k elements, such that each element in C has Hamming weight at least d . A code C can be represented by an (n-k)\times n parity check matrix \mathbf{H} such that C=\ker\mathbf{H} . The code rate of C is defined as R=k/n . With C^{\perp}=\mathrm{im}\mathbf{H}^{T} we denote dual of the code C with parameters [n,k^{\perp}=n-k,d^{\perp}] . If \mathbf{H} is sparse , i.e. , its row and column weights are constant with n , the code C is a low-density parity check code. A graph \mathcal{G}=(\mathcal{V},\mathcal{E}) is a collection of vertices \mathcal{V} and edges \mathcal{E} , such that each edge connects two distinct vertices v_{i},v_{j} and can be represented by the pair (v_{i},v_{j}) . A bipartite graph \mathcal{G}=(\mathcal{U}\cup\mathcal{V},\mathcal{E}) is a graph where the vertices can