BF-Max: an Efficient Bit Flipping Decoder with Predictable Decoding Failure Rate

• URL: http://arxiv.org/abs/2506.09689v1
• Date: Wed, 11 Jun 2025 13:04:05 GMT
• Title: BF-Max: an Efficient Bit Flipping Decoder with Predictable Decoding Failure Rate
• Abstract summary: Bit-Flipping (BF) decoder is widely employed in post-quantum cryptographic schemes.<n>For security concerns, one must guarantee that the Decoding Failure Rate (DFR) is negligible.<n>We introduce a new version of the BF decoder, that we call BF-Max, characterized by the fact that in each iteration only one bit (the least reliable) is flipped.
• Score: 6.209770040937912
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The Bit-Flipping (BF) decoder, thanks to its very low computational complexity, is widely employed in post-quantum cryptographic schemes based on Moderate Density Parity Check codes in which, ultimately, decryption boils down to syndrome decoding. In such a setting, for security concerns, one must guarantee that the Decoding Failure Rate (DFR) is negligible. Such a condition, however, is very difficult to guarantee, because simulations are of little help and the decoder performance is difficult to model theoretically. In this paper, we introduce a new version of the BF decoder, that we call BF-Max, characterized by the fact that in each iteration only one bit (the least reliable) is flipped. When the number of iterations is equal to the number of errors to be corrected, we are able to develop a theoretical characterization of the DFR that tightly matches with numerical simulations. We also show how BF-Max can be implemented efficiently, achieving low complexity and making it inherently constant time. With our modeling, we are able to accurately predict values of DFR that are remarkably lower than those estimated by applying other approaches.

Related papers

• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• Optimal Decoding of Small Codes by Density Matrix Propagation [0.0]
  We study the accuracy of practical decoding algorithms under circuit-level noise.<n>We apply this framework to small instances of the repetition code and a cellular automaton code.<n>We find significant deviations for the cellular code, with BP+OSD deteriorating already in experimentally relevant noise regimes.
  arXiv  Detail & Related papers  (2026-06-12T13:43:44Z)
• Coset Ensemble Decoder for Quantum Error Correction with Algorithm-Hardware Co-Design [16.143601808851162]
  quantum error correction (QEC) continuously extracts and decodes error syndromes in real time.<n>A critical component in QEC is the decoder, a classical subsystem that must simultaneously deliver high logical accuracy and ultra-low latency.<n>This paper presents a novel algorithm-hardware co-design that improves the accuracy-latency trade-off over existing approaches.
  arXiv  Detail & Related papers  (2026-06-09T16:37:13Z)
• Optimal Decoding with the Worm [4.970364068620607]
  We propose a new decoder for matchable'' qLDPC codes that uses a MarkovChain MonteCarlo algorithm.<n>The algorithm is applicable to decoding random errors for the surface code, the honeycomb Floquet code, and hyperbolic surface codes with constant rate.
  arXiv  Detail & Related papers  (2026-03-05T17:51:27Z)
• Proof of a finite threshold for the union-find decoder [0.9558392439655014]
  We provide a proof of a finite threshold for the union-find (UF) decoder on the surface code under the circuit-level local error model.<n>We also show that this framework yields a finite threshold for the greedy decoder, a simpler decoder with lower complexity but weaker empirical error suppression.<n>These results provide a solid theoretical foundation for the practical use of UF-based decoders in the development of fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2026-02-23T19:00:00Z)
• Threshold Selection for Iterative Decoding of $(v,w)$-regular Binary Codes [84.0257274213152]
  Iterative bit flipping decoders are an efficient choice for sparse $(v,w)$-regular codes.<n>We propose concrete criteria for threshold determination, backed by a closed form model.
  arXiv  Detail & Related papers  (2025-01-23T17:38:22Z)
• Efficient Layered New Bit-Flipping QC-MDPC Decoder for BIKE Post-Quantum Cryptography [6.583725235299022]
  Bit Flipping Key Encapsulation mechanism is a candidate of post-quantum cryptography standardization.<n>New bit-flipping (BF) decoding algorithm decides the BF threshold by an affine function with high-precision coefficients.<n>This paper proposes a column-layered decoder for the new BIKE BF decoding algorithm to substantially reduce the memory requirement.
  arXiv  Detail & Related papers  (2024-12-16T17:23:41Z)
• Let the Code LLM Edit Itself When You Edit the Code [50.46536185784169]
  underlinetextbfPositional textbfIntegrity textbfEncoding (PIE)<n>PIE reduces computational overhead by over 85% compared to the standard full recomputation approach.<n>Results demonstrate that PIE reduces computational overhead by over 85% compared to the standard full recomputation approach.
  arXiv  Detail & Related papers  (2024-07-03T14:34:03Z)
• Progressive-Proximity Bit-Flipping for Decoding Surface Codes [8.971989179518214]
  Topological quantum codes, such as toric and surface codes, are excellent candidates for hardware implementation. Existing decoders often fall short of meeting requirements such as having low computational complexity. We propose a novel bit-flipping (BF) decoder tailored for toric and surface codes.
  arXiv  Detail & Related papers  (2024-02-24T22:38:05Z)
• The closed-branch decoder for quantum LDPC codes [0.0]
  Real-time decoding is a necessity for implementing arbitrary quantum computations on the logical level. We present a new decoder for Quantum Low Density Parity Check (QLDPC) codes, named the closed-branch decoder.
  arXiv  Detail & Related papers  (2024-02-02T16:22:32Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Fault-Tolerant Quantum Memory using Low-Depth Random Circuit Codes [0.24578723416255752]
  Low-depth random circuit codes possess many desirable properties for quantum error correction. We design a fault-tolerant distillation protocol for preparing encoded states of one-dimensional random circuit codes. We show through numerical simulations that our protocol can correct erasure errors up to an error rate of $2%$.
  arXiv  Detail & Related papers  (2023-11-29T19:00:00Z)
• Modular decoding: parallelizable real-time decoding for quantum computers [55.41644538483948]
  Real-time quantum computation will require decoding algorithms capable of extracting logical outcomes from a stream of data generated by noisy quantum hardware. We propose modular decoding, an approach capable of addressing this challenge with minimal additional communication and without sacrificing decoding accuracy. We introduce the edge-vertex decomposition, a concrete instance of modular decoding for lattice-surgery style fault-tolerant blocks.
  arXiv  Detail & Related papers  (2023-03-08T19:26:10Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
  arXiv  Detail & Related papers  (2022-03-09T18:48:54Z)
• Combining hard and soft decoders for hypergraph product codes [0.3326320568999944]
  Hypergraph product codes are constant-rate quantum low-density parity-check (LDPC) codes equipped with a linear-time decoder called small-set-flip (SSF) This decoder displays sub-optimal performance in practice and requires very large error correcting codes to be effective. We present new hybrid decoders that combine the belief propagation (BP) algorithm with the SSF decoder.
  arXiv  Detail & Related papers  (2020-04-23T14:48:05Z)

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.