Skip to content

A search-based decoder for quantum error correction (QEC)

License

Notifications You must be signed in to change notification settings

quantumlib/tesseract-decoder

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

20 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Tesseract Decoder

A Search-Based Decoder for Quantum Error Correction.

Licensed under the Apache 2.0 open-source license C++

InstallationUsageHelpCitationContact

Tesseract is a Most Likely Error decoder designed for Low Density Parity Check (LDPC) quantum error-correcting codes. It applies pruning heuristics and manifold orientation techniques during a search over the error subsets to identify the most likely error configuration consistent with the observed syndrome. Tesseract archives significant speed improvements over traditional integer programming-based decoders while maintaining comparable accuracy at moderate physical error rates.

We tested the Tesseract decoder for:

  • Surface codes
  • Color codes
  • Bivariate-bicycle codes
  • Transversal CNOT protocols for surface codes

Features

  • A* search: deploys A* search while running a Dijkstra algorithm with early stop for high performance.
  • Stim and DEM Support: processes Stim circuit files and Detector Error Model (DEM) files with arbitrary error models.
  • Parallel Decoding: uses multithreading to accelerate the decoding process, making it suitable for large-scale simulations.
  • Efficient Beam Search: implements a beam search algorithm to minimize decoding cost and enhance efficiency.
  • Sampling and Shot Range Processing: supports sampling shots from circuits and processing specific ranges of shots for flexible experiment setups.
  • Detailed Statistics: provides comprehensive statistics output, including shot counts, error counts, and processing times.
  • Heuristics: includes flexible heuristic options: --beam, --det-penalty, --beam-climbing, --no-revisit-dets, --at-most-two-errors-per-detector and --pqlimit to improve performance while maintaining a low logical error rate. To learn more about these options, use ./bazel-bin/tesseract/tesseract --help

Installation

Tesseract relies on the following external libraries:

  • argparse: For command-line argument parsing.
  • nlohmann/json: For JSON handling (used for statistics output).
  • Stim: For quantum circuit simulation and error model handling.

Build Instructions

Tesseract uses Bazel as its build system. To build the decoder:

bazel build tesseract:all

Usage

The file tesseract_main.cc provides the main entry point for Tesseract Decoder. It can decode error events from Stim circuits, DEM files, and pre-existing detection event files.

Basic Usage:

./tesseract --circuit CIRCUIT_FILE.stim --sample-num-shots N --print-stats

Example with Advanced Options:

./tesseract \
        --pqlimit 1000000 \
        --at-most-two-errors-per-detector \
        --det-order-seed 232852747 \
        --circuit circuit_file.stim \
        --sample-seed 232856747 \
        --sample-num-shots 10000 \
        --threads 32 \
        --print-stats \
        --beam 23 \
        --num-det-orders 1 \
        --shot-range-begin 582 \
        --shot-range-end 583

Example Usage

Sampling Shots from a Circuit:

./tesseract --circuit surface_code.stim --sample-num-shots 1000 --out predictions.01 --out-format 01

Using a Detection Event File:

./tesseract --in events.01 --in-format 01 --dem surface_code.dem --out decoded.txt

Using a Detection Event File and Observable Flips:

./tesseract --in events.01 --in-format 01 --obs_in obs.01 --obs-in-format 01 --dem surface_code.dem --out decoded.txt

Tesseract supports reading and writing from all of Stim's standard output formats.

Performance Optimization

Here are some tips for improving performance:

  • Parallelism over shots: increase --threads to leverage multicore processors for faster decoding.
  • Beam Search: use --beam to control the trade-off between accuracy and speed. Smaller beam sizes result in faster decoding but potentially lower accuracy.
  • Beam Climbing: enable --beam-climbing for enhanced cost-based decoding.
  • At most two errors per detector: enable --at-most-two-errors-per-detector to improve performance.
  • Priority Queue limit: use --pqlimit to limit the size of the priority queue.

Output Formats

  • Observable flips output: predictions of logical errors.
  • DEM usage frequency output: if --dem-out is specified, outputs estimated error frequencies.
  • Statistics output: includes number of shots, errors, low confidence shots, and processing time.

Help

We are committed to providing a friendly, safe, and welcoming environment for all. Please read and respect our Code of Conduct.

Citation

When publishing articles or otherwise writing about Tesseract Decoder, please cite the following:

@misc{beni2025tesseractdecoder,
    title={Tesseract: A Search-Based Decoder for Quantum Error Correction},
    author = {Aghababaie Beni, Laleh and Higgott, Oscar and Shutty, Noah},
    year={2025},
    eprint={2503.10988},
    archivePrefix={arXiv},
    primaryClass={quant-ph},
    doi = {10.48550/arXiv.2503.10988},
    url={https://arxiv.org/abs/2503.10988},
}

Contact

For any questions or concerns not addressed here, please email [email protected].

Disclaimer

Tesseract Decoder is not an officially supported Google product. This project is not eligible for the Google Open Source Software Vulnerability Rewards Program.

Copyright 2025 Google LLC.