Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.03128

Belief Propagation-Informed Tesseract Decoding of Quantum LDPC Codes

Sana Javed, Francisco Garcia-Herrero, Bane Vasić, Mark F. Flanagan

quant-phcs.ITSubmitted Nov 2, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

Abstract

In quantum error correction, the decoder must estimate the errors from the measurement data accurately and fast enough to avoid a backlog. Search-based decoders such as Tesseract achieve high accuracy by finding a minimum-weight set of error events with an A* search, but their search effort grows rapidly with the physical error rate and the code size. To reduce this search effort while maintaining a logical error rate close to that of Tesseract, we propose a belief propagation (BP)-guided modification of the Tesseract decoder for quantum low-density parity-check (LDPC) codes. Damped sum-product BP is applied to the triggered detectors before the Tesseract search. If the detectors triggered by the BP hard decision match the triggered detectors, this hard decision is accepted directly, and the Tesseract search is skipped. Otherwise, the BP marginal probability estimates, weighted by a trust coefficient, modify the search priority, while the path cost keeps the channel-prior weights so that the decoding objective is unchanged. The framework also supports BP-based initialization, in which selected BP decisions form the starting point of a residual search whose signed-cost objective allows incorrect initial decisions to be removed. A node-exploration limit bounds this residual search; if the limit is reached, the decoder falls back to the BP-guided search on the original triggered detector set. The method is evaluated on the [[72,12,6]], [[90,8,10]], and [[144,12,12]] bivariate bicycle codes under circuit-level noise. With BP-based initialization and a global trust coefficient, the number of Tesseract search nodes expanded is reduced by up to more than two orders of magnitude at low physical error rates, while the logical error rate remains close to that of Tesseract.

AI Summary

The paper asks whether belief propagation (BP) can reduce Tesseract’s search effort for circuit-level quantum LDPC decoding while retaining similar logical error rates. It combines damped sum-product BP with the pruned A* search: detector-matching BP hard decisions are accepted directly; otherwise, BP marginals modify the search heuristic through trust coefficients, while path costs retain channel-prior weights. An optional BP initialization starts a residual search with signed costs, allowing initialized events to be removed without changing the underlying minimum-weight objective. After 50 residual-search expansions, decoding falls back to BP-guided search on the original syndrome. Simulations cover the $[[72,12,6]]$, $[[90,8,10]]$, and $[[144,12,12]]$ bivariate bicycle codes, using $d$ measurement rounds and physical error rates $p=0.002$–$0.007$. With global trust coefficient $\alpha=0.5$, initialization reduces average expanded nodes relative to Tesseract by approximately $157\times$, $46\times$, and $254\times$ at $p=0.002$, and $8.2\times$, $5.0\times$, and $4.4\times$ at $p=0.007$. Measured logical error rates remain close to the baseline. At the lowest rate, BP alone supplies detector-matching decisions on 97.4–99.3% of shots, accounting for much of the search reduction. Evaluation uses only $Z$-type detectors in $Z$-basis memory experiments with uncorrelated DEMs. Search-node counts exclude BP computational overhead and do not establish end-to-end runtime. Pruning, potentially inadmissible BP heuristics, and negative residual costs prevent global-optimality guarantees. Stability-based per-event trust coefficients perform worse on the larger codes; low-rate logical-error estimates can have wide confidence intervals.

Little sign of AI-generated textIncrementalMissing comparison

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
12 pages, 4 figures, 5 tables. Submitted to IEEE Transactions on Quantum Engineering

Related papers

Accelerating A*-Based Algorithms for Decoding Quantum Low-Density Parity-Check Codes

Lamia Yous, Francisco Garcia Herrero, Mark F. Flanagan

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.

quant-pharXiv:2609.10056•IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 10, 2026•0 citations

Beam search decoder for quantum LDPC codes

Min Ye, Dave Wecker, Nicolas Delfosse

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\times$ 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\times$ 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\times$ reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1ms at $p=5 \times10^{-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.

quant-pharXiv:2512.07057•PRX Quantum•Dec 9, 2025•28 citations

Adaptive decoding of quantum LDPC codes through decoder disagreement

Maida Wang, Peter V. Coveney

Accurate decoding of quantum low-density parity-check (qLDPC) codes often relies on expensive post-processing search, although decoding difficulty varies strongly between syndromes. We find that the benefit of deeper post-processing search is highly concentrated in a small subset of decoding instances, and that these instances can be identified directly from the decoder itself. To this end, we introduce an adaptive decoder based on belief propagation (BP) and ordered-statistics decoding (OSD), using the disagreement between the BP hard decision and the syndrome-consistent order-zero OSD solution as an internal risk signal to determine where deeper search is required. On a $[[144,12,12]]$ bivariate bicycle code under circuit-level depolarising noise, encoding $12$ logical qubits in $144$ data qubits with distance $12$, escalating only the highest-risk $20\%$ of instances recovers $85\%$ to $92\%$ of the improvement in logical error rate available from a full one-free-variable sweep, while reducing the mean serial decoding cost by a factor of $3.6$ relative to applying the same truncated search to every instance. At matched budget, disagreement-guided routing also outperforms routing based on the BP syndrome residual, syndrome weight and random selection. The same behaviour reappears on a structurally distinct radial qLDPC code obtained from a lifted-product construction, where escalating $20\%$ of instances recovers $87\%$ to $94\%$ of the available gain. A $Z$-memory experiment on the Quantinuum H2 trapped-ion processor, implementing both $X$-type and $Z$-type checks, further shows that the signal remains predictive under device noise. These results show that decoder-internal disagreement can expose where additional decoding effort is valuable, allowing classical computation to be concentrated on the instances most likely to benefit from it.

quant-pharXiv:2609.37629•Sep 30, 2026•0 citations

Tesseract: A Search-Based Decoder for Quantum Error Correction

Laleh Aghababaie Beni, Oscar Higgott, Noah Shutty

Tesseract is a Most-Likely Error decoder designed for low-density-parity-check quantum error-correcting codes. Tesseract conducts a search through a graph on the set of all subsets of errors to find the lowest cost subset of errors consistent with the input syndrome. Although this graph is exponentially large, the search can be made efficient in practice for random errors using $A^*$ search technique along with a few pruning heuristics. We show through benchmark circuits for surface, color, and bivariate-bicycle codes that Tesseract is significantly faster than integer programming-based decoders while retaining comparable accuracy at moderate physical error rates. We also find that Tesseract can decode transversal CNOT protocols for surface codes on neutral atom quantum computers. Finally, we compare surface code and bivariate bicycle code circuits, finding that the [[144,12,12]] bivariate bicycle code is $14\times$ to $19\times$ more efficient than surface codes using our most-likely error decoding, whereas using correlated matching and BP+OSD decoders would have implied only a $10\times$ improvement. Assuming instead that long-range couplers are $10\times$ noisier, the improvement drops to around $4\times$ using Tesseract or $2\times$ using correlated matching and BP+OSD.

arXiv:2503.10988•Mar 14, 2025•120 citations

PriorTilt: Decoding quantum LDPC codes with sparse perturbations of belief propagation priors

Min Ye, Nicolas Delfosse

Although belief propagation (BP) is a widely adopted decoder for classical low-density parity-check (LDPC) codes, its accuracy is limited in the quantum setting. We introduce \PriorTilt{}, a variant of BP obtained by selectively perturbing a small fraction of its prior log-likelihood ratios using offsets determined by recent posterior and outgoing-message statistics, while preserving the same message-passing rules. We compare \PriorTilt{} with Relay-BP and beam search decoders for circuit-level decoding of three benchmark codes. \PriorTilt{} achieves a lower logical error rate (LER) than both baselines at every tested data point. For the $[[144,12,12]]$ Gross code BB144 at noise rate $p=10^{-3}$, the LER reductions reach $4.3\times$ relative to Relay-BP and $3.1\times$ relative to the beam search decoder. At $p=10^{-3}$, \PriorTilt{} has lower mean decoding times than Relay-BP on all three codes and achieves mean decoding speedups of approximately $2.6\times$--$3.0\times$ over the beam search decoder. For BB144 at $p=10^{-3}$, \PriorTilt{} achieves an LER approximately $610\times$ lower than the standard min-sum BP decoder with the same iteration budget, while perturbing fewer than $0.5\%$ of its priors per round on average.

arXiv:2611.13373•Nov 9, 2026•0 citations

List Decoding and New Bicycle Code Constructions for Quantum LDPC Codes

Rabeti, Sheida, Hessam Mahdavifar

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.

arXiv:2511.02951•Nov 4, 2025•7 citations
In quantum error correction, the decoder must estimate the errors from the measurement data accurately and fast enough to avoid a backlog. Search-based decoders such as Tesseract achieve high accuracy by finding a minimum-weight set of error events with an A* search, but their search effort grows rapidly with the physical error rate and the code size. To reduce this search effort while maintaining a logical error rate close to that of Tesseract, we propose a belief propagation (BP)-guided modification of the Tesseract decoder for quantum low-density parity-check (LDPC) codes. Damped sum-product BP is applied to the triggered detectors before the Tesseract search. If the detectors triggered by the BP hard decision match the triggered detectors, this hard decision is accepted directly, and the Tesseract search is skipped. Otherwise, the BP marginal probability estimates, weighted by a trust coefficient, modify the search priority, while the path cost keeps the channel-prior weights so that the decoding objective is unchanged. The framework also supports BP-based initialization, in which selected BP decisions form the starting point of a residual search whose signed-cost objective allows incorrect initial decisions to be removed. A node-exploration limit bounds this residual search; if the limit is reached, the decoder falls back to the BP-guided search on the original triggered detector set. The method is evaluated on the [[72,12,6]], [[90,8,10]], and [[144,12,12]] bivariate bicycle codes under circuit-level noise. With BP-based initialization and a global trust coefficient, the number of Tesseract search nodes expanded is reduced by up to more than two orders of magnitude at low physical error rates, while the logical error rate remains close to that of Tesseract.
The paper asks whether belief propagation (BP) can reduce Tesseract’s search effort for circuit-level quantum LDPC decoding while retaining similar logical error rates. It combines damped sum-product BP with the pruned A* search: detector-matching BP hard decisions are accepted directly; otherwise, BP marginals modify the search heuristic through trust coefficients, while path costs retain channel-prior weights. An optional BP initialization starts a residual search with signed costs, allowing initialized events to be removed without changing the underlying minimum-weight objective. After 50 residual-search expansions, decoding falls back to BP-guided search on the original syndrome.
Simulations cover the [[72,12,6]][[72,12,6]][[72,12,6]], [[90,8,10]][[90,8,10]][[90,8,10]], and [[144,12,12]][[144,12,12]][[144,12,12]] bivariate bicycle codes, using ddd measurement rounds and physical error rates p=0.002p=0.002p=0.002–0.0070.0070.007. With global trust coefficient α=0.5\alpha=0.5α=0.5, initialization reduces average expanded nodes relative to Tesseract by approximately 157×157\times157×, 46×46\times46×, and 254×254\times254× at p=0.002p=0.002p=0.002, and 8.2×8.2\times8.2×, 5.0×5.0\times5.0×, and 4.4×4.4\times4.4× at p=0.007p=0.007p=0.007. Measured logical error rates remain close to the baseline. At the lowest rate, BP alone supplies detector-matching decisions on 97.4–99.3% of shots, accounting for much of the search reduction.
Evaluation uses only ZZZ-type detectors in ZZZ-basis memory experiments with uncorrelated DEMs. Search-node counts exclude BP computational overhead and do not establish end-to-end runtime. Pruning, potentially inadmissible BP heuristics, and negative residual costs prevent global-optimality guarantees. Stability-based per-event trust coefficients perform worse on the larger codes; low-rate logical-error estimates can have wide confidence intervals.
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.
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]][[144, 12, 12]][[144,12,12]] bivariate bicycle (BB) code at noise rate p=10−3p=10^{-3}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×17\times17× 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×26.2\times26.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×5.6\times5.6× reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1ms at p=5×10−4p=5 \times10^{-4}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.
Accurate decoding of quantum low-density parity-check (qLDPC) codes often relies on expensive post-processing search, although decoding difficulty varies strongly between syndromes. We find that the benefit of deeper post-processing search is highly concentrated in a small subset of decoding instances, and that these instances can be identified directly from the decoder itself. To this end, we introduce an adaptive decoder based on belief propagation (BP) and ordered-statistics decoding (OSD), using the disagreement between the BP hard decision and the syndrome-consistent order-zero OSD solution as an internal risk signal to determine where deeper search is required. On a [[144,12,12]][[144,12,12]][[144,12,12]] bivariate bicycle code under circuit-level depolarising noise, encoding 121212 logical qubits in 144144144 data qubits with distance 121212, escalating only the highest-risk 20%20\%20% of instances recovers 85%85\%85% to 92%92\%92% of the improvement in logical error rate available from a full one-free-variable sweep, while reducing the mean serial decoding cost by a factor of 3.63.63.6 relative to applying the same truncated search to every instance. At matched budget, disagreement-guided routing also outperforms routing based on the BP syndrome residual, syndrome weight and random selection. The same behaviour reappears on a structurally distinct radial qLDPC code obtained from a lifted-product construction, where escalating 20%20\%20% of instances recovers 87%87\%87% to 94%94\%94% of the available gain. A ZZZ-memory experiment on the Quantinuum H2 trapped-ion processor, implementing both XXX-type and ZZZ-type checks, further shows that the signal remains predictive under device noise. These results show that decoder-internal disagreement can expose where additional decoding effort is valuable, allowing classical computation to be concentrated on the instances most likely to benefit from it.
Tesseract is a Most-Likely Error decoder designed for low-density-parity-check quantum error-correcting codes. Tesseract conducts a search through a graph on the set of all subsets of errors to find the lowest cost subset of errors consistent with the input syndrome. Although this graph is exponentially large, the search can be made efficient in practice for random errors using A∗A^*A∗ search technique along with a few pruning heuristics. We show through benchmark circuits for surface, color, and bivariate-bicycle codes that Tesseract is significantly faster than integer programming-based decoders while retaining comparable accuracy at moderate physical error rates. We also find that Tesseract can decode transversal CNOT protocols for surface codes on neutral atom quantum computers. Finally, we compare surface code and bivariate bicycle code circuits, finding that the [[144,12,12]] bivariate bicycle code is 14×14\times14× to 19×19\times19× more efficient than surface codes using our most-likely error decoding, whereas using correlated matching and BP+OSD decoders would have implied only a 10×10\times10× improvement. Assuming instead that long-range couplers are 10×10\times10× noisier, the improvement drops to around 4×4\times4× using Tesseract or 2×2\times2× using correlated matching and BP+OSD.
Although belief propagation (BP) is a widely adopted decoder for classical low-density parity-check (LDPC) codes, its accuracy is limited in the quantum setting. We introduce \PriorTilt{}, a variant of BP obtained by selectively perturbing a small fraction of its prior log-likelihood ratios using offsets determined by recent posterior and outgoing-message statistics, while preserving the same message-passing rules. We compare \PriorTilt{} with Relay-BP and beam search decoders for circuit-level decoding of three benchmark codes. \PriorTilt{} achieves a lower logical error rate (LER) than both baselines at every tested data point. For the [[144,12,12]][[144,12,12]][[144,12,12]] Gross code BB144 at noise rate p=10−3p=10^{-3}p=10−3, the LER reductions reach 4.3×4.3\times4.3× relative to Relay-BP and 3.1×3.1\times3.1× relative to the beam search decoder. At p=10−3p=10^{-3}p=10−3, \PriorTilt{} has lower mean decoding times than Relay-BP on all three codes and achieves mean decoding speedups of approximately 2.6×2.6\times2.6×--3.0×3.0\times3.0× over the beam search decoder. For BB144 at p=10−3p=10^{-3}p=10−3, \PriorTilt{} achieves an LER approximately 610×610\times610× lower than the standard min-sum BP decoder with the same iteration budget, while perturbing fewer than 0.5%0.5\%0.5% of its priors per round on average.
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]][[144,12,12]][[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,8w=6,8w=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.