PaperlayerView exact revision on arXiv

Source-linked AI summary

Tesseract: A Search-Based Decoder for Quantum Error Correction

Laleh Aghababaie Beni, Oscar Higgott, Noah Shutty

arXiv:2503.10988v2quant-ph

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.

    Source: §1 · p. 1

  • Method

    Tesseract formulates most-likely-error decoding as graph search over error subsets and accelerates it using pruning, admissible A*, and beam-search heuristics.

    Source: §3 · pp. 3–5

  • 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.

    Source: §4 · p. 5

  • 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.

    Source: §4 · p. 6

    The decoder assumes each error occurs independently with nonzero probability at most 1/2.

    Source: §2 · p. 2

Abstract

from arXiv · show

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.Source: §1 · p. 1
  • Tesseract begins with an exponential-time algorithm that always identifies the most-likely error.Source: §1 · p. 1
  • Heuristics are then used to accelerate this exact decoding approach in practice.Source: §1 · p. 1

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)).Source: §2 · p. 2
  • The decoder receives a set S of activated detectors, also called detection events, as input.Source: §2 · p. 2
  • The graph G has all error subsets as vertices, with edges adding one error subject to predicate P.Source: §2 · p. 2
  • Restricting the predicate can reduce graph degree and improve implementation efficiency, while precedence pruning preserves exactness.Source: §2 · p. 2
  • The empty error set is the START node, while EXIT contains error sets whose activated detectors equal the input syndrome.Source: §2 · p. 2
  • A path exists from F to F′ exactly when F′ contains F, and all such paths have the same total edge cost.Source: §2 · pp. 2–3

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.Source: §3 · p. 3

Pruning the graph

  • Canonicalizing error-addition order removes redundant paths, while additional pruning can make G a tree and simplify traversal.Source: §3 · p. 3

A*

  • A* prioritizes nodes using an admissible heuristic that strictly lower-bounds the remaining distance to EXIT, preserving exactness.Source: §3 · p. 4

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.Source: §3 · p. 5
  • A priority-queue limit prevents unbounded runtime and memory use, with exceeded limits producing a heralded low-confidence outcome treated as a logical error.Source: §3 · p. 5

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.Source: §4 · p. 5
  • Tesseract and integer-program decoding achieve logical error rates one to two orders of magnitude lower than uncorrelated BP+OSD on non-topological codes.Source: §4 · p. 5
  • 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.Source: §4 · p. 6
  • 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.Source: §4 · pp. 6–7
  • 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.Source: Figure 3 · p. 7

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.Source: Figure 4 · p. 8
  • All compared decoders are exact in this benchmark, so each returns the most likely error.Tesseract’s beam cutoffs were disabled for the comparison.Source: Figure 4 · p. 8
  • In practice, judicious beam cutoffs can make Tesseract and DTD significantly faster without compromising much accuracy.Source: Figure 4 · p. 8

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.

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

Beam settings

Protocol settings

Timing caveat

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.

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.

Related papers

Loading 2503.10988v2…