Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding

• URL: http://arxiv.org/abs/2606.32001v1
• Date: Tue, 30 Jun 2026 17:34:54 GMT
• Title: Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding
• Abstract summary: We show that hard-erasure CSS codes can reach the hashing bound on the quantum erasure channel under seeded BP decoding.<n>The paper gives a DE-level proof that seeded BP decoding with finite-degree factor graphs achieves the hashing bound for the X/Z equal-rate family.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In classical sparse-graph coding, spatial coupling is a mechanism by which belief-propagation (BP) decoding attains the maximum-a-posteriori (MAP) or area-threshold performance of the uncoupled system. Since MacKay-Neal/Hsu-Anastasopoulos (MN/HA) punctured sparse ensembles achieve capacity under MAP decoding, it is natural to ask whether spatially coupled MN/HA-type Calderbank-Shor-Steane (CSS) codes can reach the hashing bound on the quantum erasure channel under seeded BP decoding. We answer this question at the density evolution (DE) level for hard-erasure CSS decoding. On an erased coordinate, the two binary Pauli components remain unresolved, equivalently the erased qubit is represented by the four Pauli possibilities. We first define the CSS ensemble through sparse punctured matrices and the corresponding dense parity-check matrices. For fixed finite Z-side, X-side, and check degrees, we then derive a five-message uncoupled DE recursion, decompose it into Z-side and X-side constituent systems, and define the two constituent potentials. Applying the coupled-vector potential method to the two constituents separately proves that seeded BP decoding on the resulting finite-degree factor graphs reaches the smaller of the Z-side degree ratio and the X-side complementary degree ratio. In the X/Z equal-rate specialization, where the Z-side and X-side constituent design rates are equal, this BP threshold is the hashing-bound channel parameter determined by the design rate. Thus the paper gives a DE-level proof that seeded BP decoding with finite-degree factor graphs achieves the hashing bound for the X/Z equal-rate family. Finite-length BP concentration, block-error convergence, and a finite-code realization of the ideal DE seed are separate questions.

Related papers

• Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes [9.855041870231533]
  Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels.<n>We construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels.<n>We prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity.
  arXiv  Detail & Related papers  (2026-09-05T03:36:03Z)
• Entropic Rigidity in Quantum Memories: How Geometry and Algebra Control the Onset of Degeneracy Corrections [4.226475360842309]
  We determine the first physical error weight $m$ at which their logical winner sets become disjoint.<n>The onset fixes the leading operational failure gap, proportional to the $m$th power of the physical noise strength.
  arXiv  Detail & Related papers  (2026-08-19T01:17:59Z)
• Quantum XYZ Stabilizer Codes [5.383800628085301]
  We introduce quantum XYZ stabilizer codes, whose parity-check matrix (PCM) is built from three pairwise binary PCMs.<n>A nontrivial point is that an XYZ code instance is not automatically genuinely non-CSS.<n>We also derive upper and lower bounds on the quantum minimum distance, including bounds for mixed Pauli logical operators.
  arXiv  Detail & Related papers  (2026-07-16T13:38:00Z)
• Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes [39.146761527401424]
  Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems.<n>We extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry.<n>We find solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample.
  arXiv  Detail & Related papers  (2026-06-03T13:12:15Z)
• A Two-Branch Finite-Field Construction for Regular CSS LDPC Bases [0.0]
  This paper develops a two-branch multiplicativecoset construction for regular CalderbankShorSteane (CSS) quantum lowdensity parity-check base matrices.<n>For decoding, we use joint logdomain belief propagation together with low-complexity post-processing rules for small residual syndromes.
  arXiv  Detail & Related papers  (2026-05-22T17:56:26Z)
• A Factor-Graph Formulation of CSS Syndrome Decoding: Joint BP and Four-State BP [0.0]
  We call the sum-product algorithm on this factorization joint belief propagation (joint BP)<n>This note compares joint BP with the four-state Pauli-label factor graph used for four-state BP.
  arXiv  Detail & Related papers  (2026-05-06T17:05:36Z)
• Efficient Complex-Valued State Preparation on Bucket Brigade QRAM [47.72095699729477]
  Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data.<n>We present two improvements within the same architecture-aware framework.
  arXiv  Detail & Related papers  (2026-04-28T13:43:29Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Probability distributions over CSS codes: two-universality, QKD hashing, collision bounds, security [0.0]
  We describe novel probability distributions for CSS codes and two-universal hashing protocols.<n>The security of the two-universal QKD hashing protocol is a factor of $2 frac52 ( 5 - frac32 ) + mathrmqrlog stC$ less secure, for some strictly positive constant $C$.
  arXiv  Detail & Related papers  (2025-10-01T21:52:00Z)
• Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [49.126395046088014]
  We consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets.<n>Our main findings are that the maximum length of messages thus identifiable scales superlinearly as $R,nlog n$ with the block length $n$.<n>We show that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code.
  arXiv  Detail & Related papers  (2024-02-14T11:59:30Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Log-domain decoding of quantum LDPC codes over binary finite fields [4.340338299803562]
  We study the decoding of quantum low-density parity-check (LDPC) codes over binary finite fields GF$(q=2l)$ by the sum-product algorithm, also known as belief propagation (BP) We show that scalar messages suffice for BP decoding of nonbinary quantum codes, rather than vector messages necessary for the conventional BP.
  arXiv  Detail & Related papers  (2021-04-01T07:15:41Z)
• 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.