CS Paper Radar

Non-Abelian sheaf quantum LDPC codes: good and magical

Zimu Li, Fuchuan Wei, Zhengyi Han, Zi-Wen Liu

cs.IT quant-phmath-ph ·submitted 2026-09-24 17:17 UTC · v2

Abstract

Non-Abelian quantum codes connect quantum error correction, phases of matter, and computational resources. In this work, we develop a general framework for constructing non-Abelian quantum low-density parity-check (qLDPC) codes by gauging sheaf codes via cup products and use it to establish code families with constant encoding rate and linear distance, simultaneously achieving optimal asymptotic scaling in both parameters. In particular, we characterize explicit logical representatives of the full gauged code space, and provide a fundamental treatment of non-Abelian code distance in the sense of Knill--Laflamme based on combining expansion with cleaning to establish protection against arbitrary errors. We further construct an almost-good family with entire code spaces exhibiting long-range magic. Moreover, we use linearly addressable cup product to directly generate linearly many encoded magic states from gauging measurements of Clifford operators. These results extend good qLDPC codes beyond the Pauli stabilizer setting, lay the foundation for pursuing the no low-energy trivial magic conjecture and shed light on non-Abelian quantum phases and orders beyond geometric locality.

Closest papers

Nearest neighbours by meaning across the whole index.

Quasi-Cyclic Qudit Lifted Product Codes with Almost Linear Minimum Distance

cs.IT quant-ph ·2026-11-11 ·Shantom K. Borah, Abhinav Vaishya, V. Lalitha, Asit Kumar Pradhan, Bane Vasic +1 more
similarity 0.73
Abstract · 43 pages, 6 figures

Quantum low-density parity-check (QLDPC) codes are a promising route to fault-tolerant quantum computation with low overhead, and qudits offer advantages over qubits including more efficient information representation, improved magic state distillation, and richer algebraic structure for code design. Asymptotically good QLDPC codes arise from the lifted product (LP) construction with non-abelian lifts, but cyclic lifts remain attractive in practice because the resulting quasi-cyclic codes have circulant structure that hardware decoders exploit, which matters especially for non-binary decoders with costly check node operations. We introduce a qudit generalization of the LP construction over cyclic group algebras, which extends hypergraph product and LP codes to arbitrary prime-power dimensions and yields quasi-cyclic qudit CSS codes for every stacking order. We bound encoding rates via a connection to additive codes, and show that in the fully stacked case, qudit LP codes built from lifted Tanner codes on expander graphs form families with $Θ(\log N)$ logical qudits and almost linear minimum distance $Θ(N/\log N)$, via a distance bound that holds for a general class of LP factors. We also study an additive decoder for general qudit codes and a linear merged-syndrome decoder for fully stacked codes. Monte Carlo simulations under a depolarizing channel with equal symbol error probability show that qudit codes achieve lower frame error rates than comparable qubit codes, and that the linear decoder gives further gains for fully stacked codes.

0.24

Quantum LDPC and High-Rate CSS Codes from Fair-Density Parity-Check Codes

cs.IT ·2026-09-01 ·Hessam Mahdavifar
similarity 0.72
Abstract

We construct quantum LDPC (qLDPC) and high-rate CSS codes from our recently introduced classical fair-density parity-check (FDPC) codes. To this end, we introduce a structured sparsification of FDPC parity-check matrices, which reduces their check weights while preserving the underlying combinatorial structure and distance guarantees. Combined with the hypergraph-product construction, this yields finite-length qLDPC codes with analytically controlled blocklength, dimension, certified distance, and stabilizer weight. For quantum blocklengths $N<10^5$, the constructions introduced here span guaranteed rates from approximately $0.35\%$ to $25.8\%$ and certified quantum distances from $12$ to $69$, with stabilizer weights between $8$ and $16$. In the large-blocklength regime, allowing the FDPC order and sparsified check weight to scale moderately with blocklength yields a family of high-rate CSS codes, which we refer to as quantum FDPC (qFDPC) codes, with rate $R_Q$ and minimum distance $D$ satisfying \[ R_Q = 1-O\left(\frac{1}{\log\log N}\right), \ \ D=Ω(N^{1/4}), \] and stabilizer weight $O(\log N\log\log N)$. Finally, the analytically available FDPC weight distribution provides explicit information about the logical operators of the resulting hypergraph-product codes. Over the quantum erasure channel, this structure yields rigorous first-order maximum likelihood (ML) expressions and a higher-order weight-distribution approximation to the ML logical block error probability. This enables estimation of finite-length operating points and the onset of the error-floor regime. To the best of our knowledge, beyond surface-code-type constructions, this is the first finite-rate qLDPC framework to provide both finite-length certified minimum-distance information and an analytical characterization of low-weight logical multiplicities.

0.08

Sipser-Spielman meets Dijkgraaf-Witten: non-Abelian qLDPC codes via twisted sheaf gauge theory and almost-constant-overhead magic state fountain

cs.IT quant-phcond-mat.str-elhep-th+1 ·2026-09-25 ·Guanyu Zhu, Shi Jie Samuel Tan, Ryohei Kobayashi, Po-Shen Hsin
similarity 0.72
Abstract · 68 pages of main text and 17 figures + appendices

Sipser-Spielman codes and Dijkgraaf-Witten twisted gauge theories are among the most profound ideas in the last few decades in the areas of computer science and mathematical physics respectively. This work unifies them in the same framework using the language of sheaf cohomology, and produces a new framework of twisted sheaf gauge theories describing a class of quantum low-density parity-check (qLDPC) codes with non-Abelian $D_4$ topological order. The corresponding twisted Clifford-stabilizer qLDPC code can be obtained from gauging a new type of 0-form sub-complex symmetry from a qLDPC code defined on a general sheaf complex, and can be interpreted as a topological defect network of non-Abelian $D_4$ patches glued together with proper gapped interfaces. As an application, one can use this to realize a magic state fountain via the gauging measurement of the addressable logical CZ gates as 0-form subcomplex symmetries in a 2D hypergraph-product (HGP) sheaf code. This includes a scheme of subdividing an arbitrary constant-rate 2D HGP code with parameters $[[n,Θ(n), Ω(n^{1/2})]]$ into a quantum sheaf code which allows preparation of $Θ(n^{1/2})$ logical CZ magic states in parallel, equivalent to the recent geometric construction using the code-to-manifold mapping in (arXiv:2601.06736). Moreover, using the recent sheaf complex and algebraic code constructions by Golowich-Tamo-Zhu (arXiv:2609.27801) with parameters $[[n,Θ(n^{1-ε}), Ω(n^{(1-ε)/2})]]$ for arbitrary small $ε$, one can prepare $Θ(n^{1-ε})$ CZ magic states in parallel and hence achieve an almost-constant magic rate.

0.50

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

cs.IT quant-ph ·2026-10-02 ·Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
highly cited similarity 0.71
Abstract

We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

0.44

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

cs.IT quant-ph ·2026-11-02 ·Gulnihal Mercanoglu, Achilleas Anastasopoulos, S. Sandeep Pradhan
similarity 0.69
Abstract · 45 pages, 9 figures

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.

0.20

Quantum codes in the Lee metric

cs.IT quant-phmath.COmath.MG ·2026-10-04 ·Jinkang Guo, Yiqiu Han, Aranya Chakraborty, Shubham P. Jain, Tianhao Liu +2 more
theory similarity 0.68
Abstract

We introduce a quantum coding framework for discrete small-shift noise, in which errors on qudits are modeled as low-weight $X$- and $Z$-type Pauli shifts, analogous to small phase-space displacements in continuous-variable systems. This structure is approximately respected by nuclear-spin noise and captured by the Lee metric, motivating a quantum extension of classical Lee-metric coding theory. We develop such a formalism for stabilizer codes over $\mathbb{Z}_q$ for arbitrary $q$, using joint and separate Lee metrics for the $X$- and $Z$-components of errors. For qubits, the joint metric counts $Y$ errors twice and can yield codes that detect and correct $X$ and $Z$ errors with fewer physical qubits than codes designed for the conventional Hamming metric. We discuss Lee-weight spreading under Clifford gates and qubitize codes over $\mathbb{Z}_4$ via the Gray map, finding codes with two-fold transversal non-qubit-Clifford gates. For quantum CSS Lee-LDPC codes on $n$ qudits, we prove that the Lee distance cannot exceed $O(n)$, uniformly in $q$, demonstrating an unexpected obstruction to using the large internal Hilbert space of a large-$q$ qudit to make high-Lee-distance codes. Under local Metropolis dynamics, certain classical $q$-ary ``helical repetition codes'' have exponentially long memory times at fixed temperature for sufficiently large $q$ (that grows with system length), which can be understood as spontaneous symmetry breaking at finite temperature, even in local one-dimensional models. Hypergraph products of these helical repetition codes provide local two-dimensional quantum codes that inherit self-correction for $Z$ errors, but self-correction for $X$ errors remains an open question.

0.49

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

cs.IT quant-ph ·2026-09-30 ·William Gay, Fernando Granha Jeronimo, Abhi Shukul
top venue similarity 0.68
Abstract · SODA 2027, to Appear

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

0.38

Specifying & Verifying Quantum Error-Correcting Codes

cs.PL quant-ph ·2026-11-16 ·Stavan Jain, Nithin Raveendran, Aws Albarghouthi
theorycode/data similarity 0.68
Abstract · 30 pages

Building quantum computers is challenging due to the noise that affects qubits. Quantum error correction tackles noise by encoding information in quantum error-correcting (QEC) codes. These codes are often complex, increasingly found by computational search, presented in diverse formalisms with informal arguments, and hard to reason about algorithmically. Given that the rest of the quantum computing stack relies on a QEC code's properties for correct computation, we propose a formally verified foundation for QEC codes. We present QECLean, a Lean-based framework for formally specifying and verifying QEC codes. QECLean backs every claimed QEC-code property with a machine-checked proof, unifies the diverse presentations of codes in the literature through common abstractions, and makes new codes easy to specify. We present a new compositional technique, code combinators, for proving code distance analytically. Code combinators allow us to prove the distance of large codes that are out of reach for algorithmic techniques; for example, we show that IBM's $[[360, 12, \leq 24]]$ code has distance 24, which was previously only known as an upper bound. Furthermore, we show how our approach allows us to formalize and prove entire code families, such as the surface code. Our work lays the foundation required for reasoning about circuit-level implementations of codes on given architectures and for building end-to-end verified compilers for quantum computers. QECLean is available at https://github.com/Stavan-Jain/QECLean

0.40