We introduce Ambiguity Clustering, a new decoder for general quantum low-density parity check codes. On the recently proposed bivariate bicycle codes we find an order of magnitude speedup compared to the state-of-the-art BP-OSD decoder with no reduction in logical fidelity at physically realistic error rates. In particular, a single-threaded CPU implementation of Ambiguity Clustering is fast enough to decode the 144-qubit Gross code in real time for neutral atom and trapped ion systems.
We introduce Ambiguity Clustering, a new decoder for general quantum low-density parity check codes. On the recently proposed bivariate bicycle codes we find an order of magnitude speedup compared to the state-of-the-art BP-OSD decoder with no reduction in logical fidelity at physically realistic error rates. In particular, a single-threaded CPU implementation of Ambiguity Clustering is fast enough to decode the 144-qubit Gross code in real time for neutral atom and trapped ion systems.
We propose a decoder for quantum low density parity check (LDPC) codes based on a beam search heuristic guided by belief propagation (BP). Our beam search decoder applies to all quantum LDPC codes and achieves different speed-accuracy tradeoffs by tuning its parameters such as the beam width. We perform numerical simulations under circuit level noise for the [[144,12,12]] bivariate bicycle (BB) code at noise rate p=10−3 to estimate the logical error rate and the 99.9 percentile runtime and we compare with the BP-OSD decoder which has been the default quantum LDPC decoder for the past six years. A variant of our beam search decoder with a beam width of 64 achieves a 17× reduction in logical error rate. With a beam width of 8, we reach the same logical error rate as BP-OSD with a 26.2× reduction in the 99.9 percentile runtime. We identify the beam search decoder with beam width of 32 as a promising candidate for trapped ion architectures because it achieves a 5.6× reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1ms at p=5×10−4. Remarkably, this is achieved in software on a single core, without any parallelization or specialized hardware (FPGA, ASIC), suggesting one might only need three 32-core CPUs to decode a trapped ion quantum computer with 1000 logical qubits.
Error correction allows a quantum computer to preserve states long beyond the decoherence time of its physical qubits. Key to any scheme of error correction is the decoding algorithm, which estimates the error state of qubits from the results of syndrome measurements. The leading proposal for quantum error correction, the surface code, has fast and accurate decoders, but several recently proposed quantum low-density parity check (qLDPC) codes allow more logical information to be encoded in significantly fewer physical qubits. The state-of-the-art decoder for general qLDPC codes, BP-OSD, has a cheap Belief Propagation stage, followed by linear algebra and search stages which can each be slow in practice. We introduce the Ambiguity Clustering decoder (AC) which, after the Belief Propagation stage, divides the measurement data into clusters that can be decoded independently. We benchmark AC on the recently proposed bivariate bicycle qLDPC codes and find that, with 0.3% circuit-level depolarising noise, AC is up to 27x faster than BP-OSD with matched accuracy. Our implementation of AC decodes the 144-qubit Gross code in 135us per round of syndrome extraction on an M2 CPU, already fast enough to keep up with neutral atom and trapped ion systems.
Quantum low-density parity-check (QLDPC) codes represent a promising approach for error correction in quantum computing. The recently proposed Tesseract decoder uses the A* search algorithm that guarantees finding the most likely error pattern. However, practical implementations of Tesseract often involve an extremely large graph, and the inherently sequential nature of the search results in high computational overhead and long runtime. To improve decoding efficiency, we propose a two-stage decoding framework. First, a belief propagation (BP) decoder efficiently processes the syndrome. This step generates hard decisions (a binary error vector) and soft information (per-qubit confidence levels). In non-convergent BP cases, a gating mechanism examines the BP decoder's output to identify and filter out qubits with oscillating confidence values. In these cases, the refined output serves as input to Tesseract, which then attempts to identify and correct any residual errors. This hybrid approach leverages the high speed of BP decoding and delegates the more challenging decoding instances to Tesseract. Numerical results demonstrate a substantial reduction in overall decoding complexity while maintaining the logical error rate (LER) of the stand-alone Tesseract. Across all tested physical error rates, the proposed method achieves at least 5x reduction in the number of expanded nodes in the Tesseract, with a peak reduction of nearly 15x at a physical error rate of p = 0.05 for the [[126, 12, d < 11]] T1 code, and approximately 8.8x at p = 0.05 for the [[72, 12, 6]] bicycle bivariate (BB) code.
Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.
In this paper, we propose a new decoder, called the Multiple-Bases Belief-Propagation List Decoder (MBBP-LD), for Quantum Low-Density Parity-Check (QLDPC) codes. It extends the Multiple-Bases Belief-Propagation (MBBP) framework, originally developed for classical cyclic LDPC codes. The proposed method preserves the linear-time complexity of standard BP decoder while improving the logical error rate. To further reduce the logical error rate, a new decision rule is introduced for the post-processing list decoder, outperforming the conventional least-metric selector (LMS) criterion. For the recently developed and implemented bivariate bicycle (BB) code with parameters [[144,12,12]], our proposed MBBP-LD decoder achieves up to 40\% lower logical error rate compared to the state-of-the-art decoder for short QLDPC codes, i.e., BP with ordered-statistics decoding (BP-OSD), while retaining the linear-time complexity of the plain BP decoder. In addition, we explore a new subclass of BB codes, that we refer to as the univariate bicycle (UB) codes, specifically with lower-weight parity checks (w=6,8). This reduces the polynomial search space for the code compared to general BB codes, i.e., by reducing the search space over two polynomial components in BB codes to just a single polynomial component in UB codes. Simulations demonstrate the promising performance of these codes under various types of BP decoders.
Quantum low-density parity-check (qLDPC) codes are promising candidates for realizing large-scale fault-tolerant quantum computing. Although many codes with favorable theoretical parameters have been developed, their practical adoption must take hardware implementability into account. For mainstream quantum platforms such as superconductors and neutral atoms, the connectivity, the length of non-local couplings, and the complexity of wiring or atom rearrangement are key factors that dictate the difficulty of hardware realization. Here, we propose a new family of qLDPC codes, termed routing codes. Within this family, we find explicit instances whose encoding rates are competitive to those of bivariate bicycle (BB) codes, while systematically reducing qubit connectivity, shortening the length of non-local couplings, and, crucially, making all non-local couplings mutually parallel. This parallelism translates into quantifiable benefits, substantially reducing wiring crossings in superconducting multi-layer architectures and simplifying the scheduling of atom movement in neutral-atom arrays. The weight-7 routing codes maintain a high threshold of 0.7\% and reduce the physical qubit overhead by approximately a factor of 8, compared to surface codes achieving a same logical error rate. Further increasing the weight to 11 yields a [[200, 24, 14]] and [[200, 16, 17]] codes with an encoding rate over 23 times that of the surface code, at the cost of a higher logical error rate. These results establish routing codes as a hardware-centric qLDPC family that bridges the gap between theoretical optimality and near-term physical feasibility.