Combinatorial Analysis of Dyadic and Quasi-Dyadic Codes

• URL: http://arxiv.org/abs/2605.01942v1
• Date: Sun, 03 May 2026 16:00:45 GMT
• Title: Combinatorial Analysis of Dyadic and Quasi-Dyadic Codes
• Abstract summary: This paper develops a framework for constructing and analyzing (Q)LDPC codes from dyadic and quasi-dyadic matrices.<n>We introduce dyadic-aware PEG-style construction algorithms that use forbidden sets of shifts to maximize attainable girth.<n>Motivated by error-floor phenomena, we characterize and explicitly enumerate absorbing sets in key dyadic layout boundary cases.
• Score: 5.193807663869809
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum low-density parity-check (QLDPC) codes offer a promising route to scalable fault-tolerant quantum computation, but their performance under iterative decoding is strongly influenced by short-cycle structure and other harmful subgraphs in the associated Tanner graphs. This paper develops an algebraic framework for constructing and analyzing (Q)LDPC codes from dyadic and quasi-dyadic matrices-translation-invariant $2^\ell \times 2^\ell$ binary matrices specified compactly by a signature row and forming a commutative ring with recursive block structure. Leveraging this structure, we relate cycles in lifted Tanner graphs to tailless backtrackless closed walks in the protograph and derive efficient, implementable methods to enumerate and control short cycles (notably $4$-, $6$-, and $8$-cycles). We introduce dyadic-aware PEG-style construction algorithms that use forbidden sets of shifts to maximize attainable girth when possible and otherwise minimize the multiplicity of the shortest cycles at the target girth. Motivated by error-floor phenomena, we further characterize and explicitly enumerate absorbing sets in key dyadic layout boundary cases, identifying configurations that induce abundant $(a,0)$-absorbing sets. Finally, we propose CSS-oriented dyadic constructions that satisfy commutation constraints by design and demonstrate via belief-propagation simulations that reducing short-cycle multiplicity can yield substantial decoding gains even when girth cannot be increased.

Related papers

• Structure-Aware Placement and Routing of Multi-Controlled Toffoli on Bivariate Bicycle Code Architectures [6.023860258848104]
  We introduce a targeted placement strategy that exploits the binary-tree structure of MCT decompositions to co-locate interacting subtrees.<n>We also evaluate the impact of factory placement across different topologies, demonstrating that grid-based layouts yield up to a $mathbf23.7%$ reduction in inter-module instructions.
  arXiv  Detail & Related papers  (2026-09-01T07:47:42Z)
• Generalized Efficient Quantum Circuit Implementation of Discrete-Time Quantum Walks on Cayley Graphs [0.0]
  We introduce a systematic multi-stage decomposition of the shift operator for 1D Cayley graphs.<n>We provide explicit circuit implementations for an 8-Cayley graph and a $mathbbZ_16 times mathbbZ_8$ torus graph.
  arXiv  Detail & Related papers  (2026-08-25T20:35:46Z)
• Measurement-Based Loss Tolerance in Graph-GKP Codes through Syndrome-Resolved Pauli-Frame Decoding [46.2474896050764]
  We develop a causal framework that unifies these mechanisms for measurement-based loss tolerance under pure loss.<n>We derive decoder-conditioned branch restriction, signed-outcome reconstruction, Pauli-frame updating, and syndrome-resolved logical fusion.<n>The resulting graph-GKP interface provides a unified causal control layer for fault-tolerant MBQC, fusion-based computation, and all-photonic repeaters.
  arXiv  Detail & Related papers  (2026-08-01T19:14:42Z)
• Optimized Compilation of Logical Clifford Circuits [41.67570087491999]
  Gate-by-gate compilation often yields deep circuits.<n>We focus on the compilation of primitives from quantum simulation as single blocks.<n>We introduce a methodology that lifts these primitives into size-invariant, depth-efficient compilation strategies.
  arXiv  Detail & Related papers  (2026-02-13T11:35:11Z)
• BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
  We propose Bit-Plane Decomposition Quantization (BPDQ), which constructs a variable quantization grid via bit-planes and scalar coefficients.<n>BPDQ enables serving Qwen2.5-72B on a single GTX 3090 with 83.85% GSM8K accuracy (vs. 90.83% at 16-bit)
  arXiv  Detail & Related papers  (2026-02-04T02:54:37Z)
• Single-Shot and Few-Shot Decoding via Stabilizer Redundancy in Bivariate Bicycle Codes [5.685589351789461]
  We prove that $g(z)$ dictates the code's stabilizer redundancy and the structure of the classical emphsyndrome codes required for single-shot decoding.<n>Within the coprime BB ansatz, high quantum rate imposes an upper bound on syndrome distance, limiting single-shot performance.
  arXiv  Detail & Related papers  (2026-01-03T09:49:58Z)
• Block-Recurrent Dynamics in Vision Transformers [42.261020313952976]
  We argue that trained ViTs admit a block-recurrent depth structure such that the computation of the original $L$ blocks can be accurately rewritten using only $k ll L$ distinct blocks applied recurrently.<n>We train a Raptor model to recover $96%$ of DINOv2 ImageNet-1k linear probe accuracy in only 2 blocks at equivalent computational cost.
  arXiv  Detail & Related papers  (2025-12-23T00:18:23Z)
• Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks [39.54576236079211]
  Speculative generation has emerged as a promising technique to accelerate inference in large language models.<n>In this work, we establish the first tight'' lower bounds on the runtime of any deterministic speculative generation algorithm.
  arXiv  Detail & Related papers  (2025-12-12T16:54:33Z)
• Pauli Stabilizer Models for Gapped Boundaries of Twisted Quantum Doubles and Applications to Composite Dimensional Codes [0.0]
  We provide new algorithms and provide example constructions of stabilizer models for the gapped boundaries, domain walls, and $0D$ defects of Abelian composite dimensional twisted quantum doubles.<n>Using the physically intuitive concept of condensation, our algorithm explicitly describes how to construct the boundary and domain-wall stabilizers.<n>We discuss the codes' utility in the burgeoning area of quantum error correction with an emphasis on the interplay between deconfined anyons, logical operators, error rates and decoding.
  arXiv  Detail & Related papers  (2025-08-26T17:59:45Z)
• R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning [80.104336426172]
  Chain-of-thought (CoT) enhances problem-solving ability of large language models.<n>CoT incurs substantial inference cost due to long autoregressive trajectories.<n>We introduce R-Stitch, a training-free hybrid decoding framework.
  arXiv  Detail & Related papers  (2025-07-23T08:14:36Z)
• Quantum Error Correction with Girth-16 Non-Binary LDPC Codes via Affine Permutation Construction [0.0]
  We propose a method for constructing quantum error-correcting codes based on non-binary low-density parity-check codes with Tanner graph girth 16.<n> Numerical experiments show that the proposed codes significantly reduce the number of low-weight codewords.
  arXiv  Detail & Related papers  (2025-04-24T17:59:58Z)
• Explicit Construction of Quantum Quasi-Cyclic Low-Density Parity-Check Codes with Column Weight 2 and Girth 12 [0.0]
  This study proposes an explicit construction method for quantum quasi-cyclic low-density parity-check codes with a girth of 12.<n>By utilizing algebraic techniques, short cycles are eliminated, which improves error correction performance.<n>The results of this study enable the design of high-performance quantum error-correcting codes without the need for random search.
  arXiv  Detail & Related papers  (2025-01-23T07:52:07Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Pruning Neural Belief Propagation Decoders [77.237958592189]
  We introduce a method to tailor an overcomplete parity-check matrix to (neural) BP decoding using machine learning. We achieve performance within 0.27 dB and 1.5 dB of the ML performance while reducing the complexity of the decoder.
  arXiv  Detail & Related papers  (2020-01-21T12:05:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.