Source-linked AI summary
Improved belief propagation is sufficient for real-time decoding of quantum memory
Tristan Müller, Thomas Alexander, Michael E. Beverland, Markus Bühler, Blake R. Johnson, Thilo Maurer, Drew Vandeth
TL;DR
Real-time decoding for large-scale quantum computers requires accurate, lightweight methods compatible with hardware implementation. The paper introduces Relay-BP, which chains BP runs with disordered memory strengths, and reports strong performance across LDPC and surface-code circuit decoding. Its broader scalability and performance beyond memory experiments remain open questions.
Problem
Real-time quantum decoding needs accurate decoders compatible with compact, fast FPGA or ASIC implementations.
Method
Relay-BP chains multiple BP runs using different, problem-dependent memory strengths and passes information between successive runs.
Results
Relay-BP achieves orders of magnitude better logical error rates than BP+OSD+CS-10 for LDPC codes and comparable rates to matching-based decoders for the rotated surface code.
Takeaways & Limitations
Evidence suggests Relay-BP is fast enough for real-time FPGA decoding while maintaining very low logical error rates.
Takeaways & Limitations
The paper leaves open how Relay-BP performs beyond memory experiments and how a full FPGA implementation performs.
Abstract
from arXiv · showhide
We introduce a new heuristic decoder, Relay-BP, targeting real-time quantum circuit decoding for large-scale quantum computers. Relay-BP achieves high accuracy across circuit-noise decoding problems: significantly outperforming BP+OSD+CS-10 for bivariate-bicycle codes and comparable to min-weight-matching for surface codes. As a lightweight message-passing decoder, Relay-BP is inherently parallel, enabling rapid low-footprint decoding with FPGA or ASIC real-time implementations, similar to standard BP. A core aspect of our decoder is its enhancement of the standard BP algorithm by incorporating disordered memory strengths. This dampens oscillations and breaks symmetries that trap traditional BP algorithms. By dynamically adjusting memory strengths in a relay approach, Relay-BP can consecutively encounter multiple valid corrections to improve decoding accuracy. We observe that a problem-dependent distribution of memory strengths that includes negative values is indispensable for good performance.
DMem-BP—
DMem-BP extends belief propagation with node-specific memory strengths and flexible initialization. Its relay-compatible message-passing design updates beliefs until a valid correction is found or an iteration limit is reached.
- Message passing: Check-to-error messages encode syndrome-consistent beliefs using a sign determined by κi,j(t) (−1)σi and a magnitude set by the least confident contributing message.The message µi→j(t) represents check i’s belief that error j occurred based on messages from its other neighboring error nodes.
- Message passing: Error-to-check messages combine beliefs from other check nodes with a time-dependent bias term Λj(t).The bias term shifts messages received by error node j and is updated in DMem-BP rather than remaining fixed as in standard BP.
- Initialization and stopping: DMem-BP initializes beliefs and biases from error-prior log-likelihoods, while initial marginals may be supplied separately.After each message-passing iteration, the algorithm computes updated marginals and a hard decision for each error node.
- Initialization and stopping: The algorithm returns a hard decision when it satisfies Hê(t) = σ; otherwise it continues until the maximum iteration count T, after which it is unsuccessful.This stopping rule makes convergence depend on finding a parity-check-consistent error estimate within the available iterations.
- Memory strengths: DMem-BP parameterizes decoding by real-valued, node-specific memory strengths Γ = {γj}j∈[N].Setting all γj to zero recovers standard BP, while a constant value between zero and one recovers Mem-BP.
- Relay integration: DMem-BP instances can run in parallel, but sequentially connecting them into a relay ensemble typically improves performance.Each DMem-BP instance is treated as one leg of Relay-BP.
Relay-BP-S—
Relay-BP-S chains multiple DMem-BP legs with configurable memory strengths, iteration limits, and solution targets. Each leg passes its final marginals forward, and the decoder returns the lowest-weight solution found.
- Relay specification: Relay-BP-S is specified by the number of solutions sought S, maximum relay legs R, per-leg iteration limits Tr, and memory strengths Γr.These parameters define both the relay budget and the memory-strength schedule across legs.
- Relay initialization: The first relay leg applies DMem-BP using initial marginals and memory strengths derived from the error priors.The initialization is written as Mj(0) = log 1−pj in the supplied description.
- Relay execution: Each later leg initializes its marginals with the previous leg’s final marginals, passing information forward through the relay.A leg stops after finding a solution or reaching its iteration limit Tr.
- Selection and stopping: The algorithm stops after R legs or S solutions and returns the lowest-weight solution found among all legs.The solution weight is defined as w(ê) = P pj in the supplied passage.
- Evaluation: The experiments evaluate Relay-BP under circuit-level noise on two bivariate-bicycle codes and a distance-11 rotated surface code.The examples use CSS-type circuits and noisy QEC cycles followed by one perfect cycle.
Decoding examples—
The evaluation uses either direct XYZ decoding or decomposed XZ decoding, with Relay-BP simulations configured through fixed first-leg and randomized later-leg memory strengths. XZ reduces object sizes but may degrade performance by treating X and Z errors independently.
- Decoding strategies: XYZ-decoding directly computes a correction from H and σ, whereas XZ-decoding independently decodes σX and σZ before combining the partial corrections.The decomposed strategy uses derived check matrices HX and HZ.
- Decoding strategies: XZ-decoding simplifies computation with smaller decoding objects but may degrade performance by modeling X and Z errors as independent.The supplied evaluation description states that XZ-decoding is used throughout unless otherwise indicated.
- Simulation configuration: Relay-BP uses Tr = 60 iterations per leg except the first, which uses T0 = 80 because initial convergence is slower.The iteration settings are shared across the reported simulations.
- Simulation configuration: The first leg uses γ = 0.125 for the gross and two-gross codes and γ = 0.35 for the surface code.These values were selected from preliminary sweep results.
- Simulation configuration: Subsequent-leg memory strengths are sampled independently and uniformly from a range centered at γcenter with width γwidth.This produces randomized memory-strength instances after the initial leg.
Memory strength selection—
Relay-BP’s accuracy depends strongly on the selected memory-strength distribution. For the bivariate-bicycle codes, the best-performing intervals include negative memory strengths, with a weaker version of this pattern for the surface code.
- Memory-strength landscape: The gross and two-gross code heatmaps show performance hotspots for intervals that include negative memory strengths.A similar but less pronounced hotspot appears for the surface code.
- Memory-strength landscape: The selected memory-strength intervals were obtained through gradient-free optimization and used for subsequent simulations.The heatmaps mark these optimized intervals with circles.
- Decoding performance: Relay-BP achieves low logical error rates across all three decoding examples.The result is reported for the two bivariate-bicycle codes and the rotated surface-code example evaluated in the study.
Flexible decoding—
Relay-BP improves circuit-noise decoding across BB and surface-code examples while using relay ensembling to improve solution quality. Its comparisons span BP+OSD+CS-10, Matching, and independent ensembling.
- Relay-BP compares circuit-noise decoding on two BB codes and a distance-11 rotated surface code using circuit-level noise simulations.
- At p = 3 × 10−3, Relay-BP-5 and XYZ-Relay-BP-5 outperform BP+OSD+CS-10 on the gross code by approximately one and two orders of magnitude, respectively.
- For the two-gross code at p = 3 × 10−3, Relay-BP-5 shows even larger improvements over BP+OSD+CS-10.
- XYZ-Relay-BP-5 outperforms Relay-BP-5 and performs comparably to Matching on the surface code.
- Relay ensembling improves both convergence rate and solution quality compared with independently restarting each leg from the original priors.On the gross code, the relay version reaches (7 ± 1) × 10−6 in 330.8 ± 0.5 iterations, versus (1.4 ± 0.2) × 10−5 in 578 ± 2 iterations for independent ensembling.
Real-time decoding—
Relay-BP achieves substantially lower error rates than other BP-based decoders within an estimated real-time iteration budget. Increasing the relay ensemble size improves performance, while larger-code and XYZ-decoding settings may reduce that budget.
- Relay-BP-1 achieves error rates orders of magnitude lower than BP and Mem-BP within 30 iterations, and outperforms high-resource BP+OSD+CS-10 by a factor of three.
- Within the estimated 600-iteration real-time budget, Relay-BP achieves substantially lower error rates than other decoders.
- At 300 iterations, Relay-BP-9 achieves a twofold improvement over Relay-BP-1 and nearly matches Relay-BP-100, indicating diminishing returns beyond S = 9 in this scenario.
- For larger codes, increased problem size may raise iteration time and exceed a single FPGA’s capacity under the fully parallel implementation strategy considered.
Discussions and Outlook—
The paper reports strong decoding performance and FPGA real-time feasibility, while identifying unresolved questions about memory strengths, broader settings, and full FPGA implementations.
- Relay-BP achieves orders of magnitude better logical error rates than BP+OSD+CS-10 for LDPC codes and comparable error rates to matching-based decoders for the rotated surface code.
- All evidence suggests that Relay-BP is fast enough for real-time FPGA decoding while achieving very low logical error rates.
- The paper leaves open why negative memory strengths matter, how Relay-BP performs beyond memory experiments, how to choose memory strengths, and how a full FPGA implementation performs.
Appendix Decoding objects for logical memory circuits—
The decoding objects define circuit-level logical-memory decoding through detector syndromes, residual Paulis, and error probabilities, with optional XZ decomposition and column compression.
- Graph representation: The decoding graph represents H with error nodes as columns and check nodes as rows, while the syndrome records each check’s parity.Filled nodes indicate matrix value 1; unfilled nodes indicate 0.
- Circuit construction: Each QEC cycle measures fixed stabilizer generators, producing detector outcomes from parity across successive rounds.The simulations use d noisy cycles followed by one error-free final cycle.
- Noise model: The circuit-level noise model independently samples discrete error modes, whose detector flips and residual Paulis define H and A.Each error mode corresponds to a column in H and A, with its probability stored in p.
- Decoding objects: XYZ decoding uses H, A, and p directly, whereas XZ decoding extracts type-specific objects and independently decodes X- and Z-associated syndromes.The partial corrections are later combined into a full correction.
- Column compression: Identical columns of H are compressed by retaining one representative and replacing their probabilities with the probability of an odd number of errors in the group.The process repeats until all columns of H are unique.
Decoding—
The decoding formulation assumes independent bit errors, estimates bit-wise most likely corrections from BP marginals, and compares iteration behavior for XYZ decoding.
- Probability model: The noise model assumes each bit is drawn independently according to the probability vector p.This independence assumption enables factorization of the conditional error distribution.
- BP decoding: BP computes marginals of the conditional error distribution, which are used to estimate the bit-wise most likely error rather than the maximum-likelihood error.The marginals are calculated using a suitable factorization for BP.
- XYZ-decoding analysis: Figure 5 plots logical error rate against average BP iterations at p = 3 × 10^-3 for XYZ-Relay-BP-S, XYZ-BP, and XYZ-Mem-BP.Relay-BP-S varies the maximum number of legs R, while the other curves vary maximum iteration count.
- Probability model: The factorization uses each row H_k of H and Iverson’s notation to express parity-check constraints.Iverson’s bracket is 1 when its enclosed proposition is true and 0 otherwise.
XYZ-decoding real-time analysis—
The pseudo-code omits the universal quantifier ∀j whenever its intended scope is clear.
- Notation: The pseudo-code suppresses ∀j for brevity when the intended quantification is clear.This is a notational simplification rather than an algorithmic change.
- Notation: The omitted universal quantifier applies to indexed operations whose scope is evident from the surrounding pseudo-code.The convention keeps the displayed algorithm shorter.
- Notation: Readers should restore ∀j mentally where the pseudo-code makes universal indexing implicit.The stated convention concerns presentation only.
Pseudo-Code for Relay Algorithm—
Relay-BP-S runs memory-based BP across relay legs, reuses final marginals between legs, and stops when enough valid solutions have been found or the relay ends.
- Inputs and output: Relay-BP-S accepts a target number of solutions S, relay-leg limit R, per-leg iteration limit T_r, and leg-specific memory strengths Γ_r.It returns whether a solution was found together with the estimated error.
- Stopping conditions: The algorithm proceeds to another leg when a leg ends without satisfying the stopping condition and breaks when enough solutions have been found.The solution count is compared with S.
- Relay legs: Final memory values are reused as the initial memory state for the next relay leg.This carries information across consecutive DMem-BP runs.
- Inputs and output: Relay-BP-S returns a Boolean indicating whether at least one solution was found, together with the estimated error vector.The return condition is s > 0.