Source-linked AI summary
Tesseract: A Search-Based Decoder for Quantum Error Correction
Laleh Aghababaie Beni, Oscar Higgott, Noah Shutty
TL;DR
Quantum error correction needs fast, accurate decoders, but exact most-likely-error decoding is computationally difficult. Tesseract searches an error-subset graph using A* and pruning heuristics. It is faster than integer-programming decoding with comparable accuracy at moderate error rates, while its code-efficiency advantage depends on the noise model and decoder.
Problem
Quantum error correction requires fast and accurate decoders, while decoding is NP-hard in the worst case and existing approaches provide partial solutions for specific codes.
Method
Tesseract formulates most-likely-error decoding as graph search over error subsets and accelerates it using pruning, admissible A*, and beam-search heuristics.
Results
Tesseract is approximately five times faster than integer-programming decoding with nearly identical accuracy for topological-code benchmarks at p ≤ 0.001, while showing an error floor at p = 0.002 for larger codes.
Takeaways & Limitations
Using Tesseract, the [[288,12,10]] bivariate bicycle circuit shows 14×–19× qubit savings over surface-code circuits under SI1000 noise, versus 10× with correlated matching and BP+OSD.
Takeaways & Limitations
The decoder assumes each error occurs independently with nonzero probability at most 1/2.
Abstract
from arXiv · showhide
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.
1 Introduction
Tesseract addresses the need for fast, accurate decoding in quantum error correction by starting from an exact most-likely-error algorithm and using heuristics to make it practical for LDPC codes.
- QEC requires fast and accurate decoders to achieve low logical error rates.
- Tesseract begins with an exponential-time algorithm that always identifies the most-likely error.
- Heuristics are then used to accelerate this exact decoding approach in practice.
2 Notation
The notation represents quantum decoding as a weighted search over subsets of errors, where valid syndrome-consistent sets are exit nodes and the most-likely solution is the minimum-cost one.
- The error model assigns probabilities to errors and defines their costs as w(e) = −log(p/(1−p)).
- The decoder receives a set S of activated detectors, also called detection events, as input.
- The graph G has all error subsets as vertices, with edges adding one error subject to predicate P.
- Restricting the predicate can reduce graph degree and improve implementation efficiency, while precedence pruning preserves exactness.
- The empty error set is the START node, while EXIT contains error sets whose activated detectors equal the input syndrome.
- A path exists from F to F′ exactly when F′ contains F, and all such paths have the same total edge cost.
3 Decoding as Optimized Path-Finding in G
Tesseract turns most-likely-error decoding into shortest-path search, then accelerates it through graph pruning, admissible A* heuristics, beam search, and resource limits.
- The Most-Likely Error problem is equivalent to finding a shortest path in G.
- Pruning the graph: Canonicalizing error-addition order removes redundant paths, while additional pruning can make G a tree and simplify traversal.
- A*: A* prioritizes nodes using an admissible heuristic that strictly lower-bounds the remaining distance to EXIT, preserving exactness.
- Beam search: Beam search rejects nodes whose residual detection events exceed the current minimum by more than beam; a moderate beam of approximately 20 works well in practice.
- Beam search: A priority-queue limit prevents unbounded runtime and memory use, with exceeded limits producing a heralded low-confidence outcome treated as a logical error.
4 Results
Tesseract matches integer-program decoding accuracy at moderate error rates while running faster, and improves the measured advantage of bivariate bicycle codes over surface codes. Its advantage decreases when long-range couplers are substantially noisier.
- At p ≤ 0.001, Tesseract achieves nearly identical accuracy to integer-program decoding across topological-code benchmarks while running approximately five times faster.At p = 0.002, larger codes show an error floor indicating a slight speed–accuracy trade-off.
- Tesseract and integer-program decoding achieve logical error rates one to two orders of magnitude lower than uncorrelated BP+OSD on non-topological codes.
- Using Tesseract, the [[288,12,10]] bivariate bicycle circuit has significantly better performance than distance-13 surface codes, corresponding to 14× qubit savings and possibly matching distance-15 performance, corresponding to 19× savings.With less accurate decoders, the comparison instead showed a 10× qubit saving relative to distance-11 surface codes.
- Under NLR10 noise at p = 0.1%, qubit savings fall from 14×–19× to 4× with Tesseract and from 10× to 2× with correlated matching and BP+OSD.The [[288,12,10]] bivariate bicycle circuit is then equivalent to distance-7 surface codes with Tesseract and distance-5 surface codes with BP+OSD.
- Figure 3 compares the [[144,12,12]] bivariate bicycle code, implemented with 288 qubits including ancillas, against 12 copies of surface codes under SI1000, NLR5, and NLR10 noise models.
5 Comparison with [OHB25]
The paper compares Tesseract with DTD, MaxSAT, and integer-program decoders using exact timing data, while noting that practical cutoffs can accelerate search-based decoders with limited accuracy loss.
- Figure 4 compares timing data for DTD and MaxSAT with the paper’s integer-program and Tesseract implementations.
- All compared decoders are exact in this benchmark, so each returns the most likely error.Tesseract’s beam cutoffs were disabled for the comparison.
- In practice, judicious beam cutoffs can make Tesseract and DTD significantly faster without compromising much accuracy.
A The challenge of handling Y errors using BPOSD
The section explains why uncorrelated BP+OSD can outperform correlated decoding for bivariate bicycle circuits: annotating both detector bases introduces structures associated with Y-type errors.
- Uncorrelated BP+OSD decodes X- and Z-type errors separately, annotating only detectors matching the benchmarked observable.
- Correlated BP+OSD annotates both X- and Z-type detectors, producing a larger Tanner graph and lower observed accuracy than uncorrelated BP+OSD.The comparison uses a six-round X-memory experiment for the [[72,12,6]] bivariate bicycle code.
- Overlapping X and Z stabilizers necessarily create 4-cycles involving Y-type errors in the full detector-error-model Tanner graph.These structures can create trapping sets in belief-propagation decoders.
B Full results and benchmarking details
The benchmarking evaluates Tesseract across several physical error rates using short- and long-beam configurations, with parameter choices varying by protocol. Reported timings are representative rather than tightly controlled measurements.
- Benchmark range: Tesseract was benchmarked at SI1000 physical error rates p ∈ {0.0005, 0.001, 0.002}.
- Beam settings: The long-beam setting uses beam 20, 21 detector orderings, and pqlimit 1,000,000, while the short-beam setting uses beam 15, 16 orderings, and pqlimit 200,000.
- Protocol settings: Long-beam settings were used for surface-code transversal CX protocols, selected color-code cases, and selected surface-code cases at p = 0.002.
- Protocol settings: Short-beam settings were used for all other protocols, including all bicycle-code benchmarks, with no-revisit detection enabled and no detection penalty.
- Timing caveat: Execution times are representative estimates because each decoder used one physical core without explicit resource isolation to control system load.
C Technical differences from [OHB25]
Tesseract and DTD each provide a slower optimality-guaranteed decoder and a faster decoder that sacrifices some accuracy. Their A* searches, heuristics, cutoffs, and target operating regimes differ.
- Both works provide a slower decoder with a rigorous optimality guarantee and a faster decoder that trades accuracy for performance.
- Both algorithms use A* search, but Tesseract traverses error-set graphs with canonicalized path ordering and uses a simpler heuristic plus beam cutoff.
- Figure 7 compares correlated sparse blossom for surface codes with BP+OSD for bivariate bicycle codes under SI1000, NLR5, and NLR10 noise models.
- Tesseract focuses on high-accuracy decoding for circuit-level noise models, including color, surface, bicycle, and transversal CNOT protocols.
- At p = 0.001, Tesseract achieves 100x lower logical error rates than BP+OSD for bicycle codes.
D Additional results comparing surface codes and bivariate bicycle codes
The paper compares four small bivariate bicycle codes with surface codes using both mixed decoder choices and Tesseract, while verifying selected circuit distances with MaxSAT.
- The section compares surface codes with the four smallest bivariate bicycle codes from [BCG+24].
- The [[72,12,6]] code has verified circuit distance 6, while the [[90,8,10]] code has verified circuit distance 8.
- The circuit-distance verification used Stim’s Circuit.shortest error sat problem method combined with a MaxSAT solver.
- Figure 8 decodes both surface and bivariate bicycle code circuits with Tesseract under SI1000, NLR5, and NLR10 noise models.