# Techniques: An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

## What the paper contributes (one paragraph)
The paper introduces the belief propagation plus ordered Tanner forest (BP+OTF) decoder for quantum LDPC codes, an almost-linear time alternative to inversion-based post-processors such as BP+OSD. When an initial round of belief propagation fails, the OTF post-processor uses a modified Kruskal spanning-tree algorithm to delete qubit nodes from the decoding graph until it becomes loop free, after which a second round of BP is guaranteed to converge if a solution exists. To handle circuit-level noise, the authors add a sparsification routine that maps a dense detector error model to a sparser one, using a transfer matrix that carries the soft information from the full graph onto the sparsified graph. The resulting three-stage BP+BP+OTF decoder matches state-of-the-art logical error suppression for bivariate bicycle and surface codes while retaining almost-linear runtime, making it attractive for real-time hardware decoding.

## Techniques offered
- **qLDPC decoder (BP+OTF / BP+BP+OTF)** - an almost-linear time belief-propagation decoder whose ordered Tanner forest post-processor prunes the decoding graph to a loop-free structure so a second BP pass can converge without matrix inversion.
  - guarantee: convergence guarantee for the second BP pass when the syndrome lies in the image of the pruned graph; almost-linear O(n log n) worst-case runtime; no logical-error bound (empirical parity with BP+OSD and MWPM).
  - quote: "In this work, we introduce the belief propagation plus ordered Tanner forest (BP+OTF) algorithm as an almost-linear time decoder for quantum low-density parity-check codes."
- **Detector error model sparsification (transfer-matrix soft-information mapping)** - a routine that re-expresses a dense circuit-level detector error model as a sparser graph and uses a transfer matrix to carry BP soft information onto it, improving post-processor success and accelerating other decoders.
  - guarantee: preserves the column space of the detector matrix (image equality) and bounds maximum column weight by that of the CSS matrices; no logical-error bound.
  - quote: "To enhance performance under circuit-level noise, we introduce a technique for sparsifying detector error models."

## Where it could apply
- Target primitive(s): none (decoder applies to any QEC syndrome stream rather than a specific algorithmic primitive)
- Target application group(s): error_correction, platforms_tooling
- Code family / hardware assumptions: qLDPC codes generally; benchmarked on bivariate bicycle codes and surface codes under circuit-level noise; suited to high-connectivity hardware and real-time FPGA or ASIC implementation.

## Caveats
None.