CS Paper Radar

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

Guanyu Zhu, Shi Jie Samuel Tan, Ryohei Kobayashi, Po-Shen Hsin

cs.IT quant-phcond-mat.str-elhep-thmath-ph ·submitted 2026-09-25 17:12 UTC · v2

Abstract

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.

Comment
68 pages of main text and 17 figures + appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Non-Abelian sheaf quantum LDPC codes: good and magical

cs.IT quant-phmath-ph ·2026-09-24 ·Zimu Li, Fuchuan Wei, Zhengyi Han, Zi-Wen Liu
similarity 0.72
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.

0.40

Parallelizable and addressable transversal non-Clifford gates on good quantum LDPC codes

cs.IT quant-phmath-ph ·2026-09-22 ·Yiming Li, Zimu Li, Zhengyi Han, Zi-Wen Liu
similarity 0.59
Abstract

We achieve linearly many parallelizable and addressable transversal logical multi-controlled-Z gates with asymptotically optimal parameters simultaneously on good quantum low-density parity check codes and quantum locally testable codes, by applying the gate framework of [arXiv:2604.01874] to good qLTC constructions. To establish the nontriviality of the logical operation, we express the cup product pairing as a coefficient in a product of Moore determinants and prove that this coefficient is nonzero. Moreover, we use the symmetries of the covering spaces to construct large spaces of cocycles. By multiplying the initial cocycles by suitable elements of these spaces, we obtain linearly many independent pairings, each selected by a corresponding cycle constructed using Poincaré duality. This yields linearly many parallelizable and addressable multi-controlled-Z gates and enables asymptotically constant-overhead magic state distillation with good qLDPC codes.

0.44

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.55
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

Addressable transversal CCZ gates on almost good quantum LDPC codes and nearly optimal magic state protocols

cs.CC quant-phcond-mat.str-elcs.IT+1 ·2026-11-18 ·Shi Jie Samuel Tan, Guanyu Zhu
similarity 0.54
Abstract · 69 pages + Appendices

Assuming uniform subfield product expansion, we construct quantum low-density parity-check (qLDPC) codes with distances $Ω_ε(N/\log^2N)$ and at least $N^{1-ε}$ individually addressable logical CCZ gates on pairwise disjoint triples of logical qubits, for every fixed $0<ε<1$. With all logical qubits outside these triples initialized to $|0\rangle$, any subset of the corresponding logical CCZ gates can be implemented with a transversal physical CCZ circuit. As applications, we obtain two nearly optimal magic state protocols: CCZ distillation with arbitrarily small overhead exponent $γ\rightarrow 0$ and error suppression of nearly linear order, and a magic state fountain that directly prepares $N^{1-ε}$ encoded CCZ magic states with nearly linear distance $Ω_ε(N/\log^2N)$. The construction uses balanced products of expanding graph covers. The assumption concerns Reed--Solomon codes on three subfields of characteristic two and pairwise coprime extension degrees, a local hypothesis studied in a companion manuscript. We design the expanding graph covers to admit many common classical codewords, which yield logical operators whose pairings select the logical CCZ gates independently. Without the product expansion assumption, the graph covers also yield classical LDPC codes over a fixed field with almost linear dimension and linear distance that satisfy a multiplication property: the coordinatewise product of any three codewords lies in a second LDPC code of linear distance.

0.40

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

cs.IT ·2026-09-01 ·Hessam Mahdavifar
similarity 0.54
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

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

cs.CC quant-phcs.IT ·2026-09-30 ·Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, Elad Tzalik
publishedtheoryhighly cited similarity 0.54
Abstract · 44 pages, 5 figures; cleaned up misplaced editorial comments

Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.

0.64

Non-Binary Quasi-Cyclic LDPC Codes with Entanglement Assistance

cs.IT ·2026-08-17 ·Pavan Kumar, Shayan Srinivasa Garani
similarity 0.53
Abstract · 6 pages

We construct two families of non-binary entanglement assisted (EA) quasi-cyclic (QC) quantum low-density parity-check (QLDPC) codes over arbitrary finite fields, each possessing a precisely determined code rate. The first family is derived from a pair of non-binary classical QC-LDPC codes, designed such that the unassisted portion of the overall Tanner graph of the resulting EA-QC-QLDPC code is free of 4-cycles. The second family, on the other hand, is constructed from a single non-binary classical QC-LDPC code whose Tanner graph itself is 4-cycle-free. In developing the codes belonging to the first family, we employ a \emph{single Bell pair} to establish entanglement between the transmitter and the receiver, thereby minimizing the required entanglement resources. Furthermore, these constructions demonstrate that careful graph-based design can effectively balance error-correction performance with entanglement consumption, providing a practical approach for realizing efficient non-binary EA-QC-QLDPC codes.

0.11

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.53
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