UC Riverside

Belief-propagation (BP) decoding is known to underperform on degenerate quantum low-density parity-check (qLDPC) codes, where short cycles and error degeneracy induce early error floors—especially under realistic circuit-level noise. This dissertation systematically studies how to improve BP’s accuracy and runtime across multiple code families (rotated surface, toric, and generalized bicycle/GB codes) and noise models (Pauli/channel-capacity, phenomenological, and circuit-level). We provide a unified evaluation of previously proposed BP refinements—including BP+ordered-statistics decoding (OSD), randomized message-update schedules, randomized priors, freezing/decimation, and memory-augmented variants—and clarify when each method helps, how gains scale with code distance, and what computational costs are incurred.Our simulations show that BP+OSD remains a strong baseline, often recovering the optimal or near-optimal log-log slope of logical-error rate versus physical-error rate (e.g., approaching ⌊(d+ 1)/2⌋), while purely BP-based modifications improve accuracy only partially on surface and toric codes as d increases. For low-degeneracy GB codes, however, standard BP already approaches BP+OSD, leaving limited room for further gains. Motivated by the locality of checks and sub-threshold error clustering in many qLDPCs, we introduce a cluster-based pre-decoder that: (i) decomposes the measured syndrome into connected components on the syndrome-connectivity graph; (ii) attempts independent correction of each component via a precomputed hash lookup; and (iii) hands only the residual to BP(+OSD). This design reduces the number of OSD invocations and the problem size seen by OSD, yielding orders-of-magnitude speedups in the practically relevant low-error-rate regime with minimal accuracy loss. We characterize the trade-off via tunable parameters (e.g., component-width and exploration limits), showing that conservative settings preserve accuracy across codes and noise models, while more aggressive settings further accelerate decoding at the cost of a slight accuracy decrease in specific surface-code and circuit-level cases. To mitigate extreme degeneracy, we also employ degeneracy-reducing matrix transformations (inverse-decoration and star-polygon) as a preprocessing step, ensuring BP corrects all weight-1 errors on transformed rotated-surface-code instances without altering maximum-likelihood performance. Overall, our results establish when BP refinements meaningfully improve accuracy, when OSD is indispensable, and how a simple cluster pre-decoder can act as an efficient front-end to modern qLDPC decoding pipelines. The methods and benchmarks presented here offer practical guidance for low-latency decoders needed in real-time fault-tolerant quantum computing under circuit-level noise.