Fusion Blossom: Fast MWPM Decoders for QEC

Yue Wu, Lin Zhong

TL;DR

This paper introduces Fusion Blossom, a novel parallel algorithm for decoding quantum error correction codes. It significantly speeds up the Minimum-Weight Perfect Matching (MWPM) decoding process, making it practical for real-time quantum hardware by achieving a throughput of one million measurement rounds per second.

What Problem Does This Paper Address?

Quantum error correction (QEC) is crucial for building fault-tolerant quantum computers. A key component of QEC is the decoder, which interprets measurement results (syndromes) to identify and correct errors. Existing decoders, particularly those based on the Minimum-Weight Perfect Matching (MWPM) algorithm, are too slow for the high measurement rates of current quantum hardware (e.g., 1 million measurements per second). This speed bottleneck leads to an ever-growing backlog of uncorrected measurements, preventing the realization of quantum computation's full potential. The paper aims to bridge this gap by developing a fast, scalable, and online MWPM decoder.

Methods

The core innovation lies in two main areas:

  • Parity Blossom: A fast, sequential MWPM decoder that works directly on the "decoding graph" rather than the more complex "syndrome graph." This approach leverages the structure of QEC codes to achieve near-linear time complexity. It uses a novel geometric interpretation and "pseudo-covers" to efficiently detect obstacles during the decoding process.
  • Fusion Blossom: A parallel MWPM decoder that recursively divides the decoding problem into smaller sub-problems, solves them in parallel using Parity Blossom, and then fuses their solutions. This "divide and conquer" strategy, structured as a fusion tree, allows for significant speedups and can be adapted for different trade-offs between decoding time and latency.

Datasets

Not discussed in the paper. The evaluation uses simulated data based on a circuit-level noise model with a physical error rate of 0.1% applied to a rotated surface code.

Key Insights and Ideas

  • Decoding Graph vs. Syndrome Graph: Working directly on the decoding graph, inspired by Union-Find decoders, is significantly more efficient for MWPM in QEC than constructing the full syndrome graph, especially at low error rates.
  • Geometric Interpretation of Blossom Algorithm: The paper provides a novel geometric interpretation of the blossom algorithm, linking dual variables to "covers" on the decoding graph. This insight is crucial for developing efficient obstacle detection mechanisms.
  • Pseudo-Covers for Efficiency: The introduction of "pseudo-covers" offers a more memory-efficient way to track information needed for obstacle detection compared to full "covers," especially when dealing with zero-weight edges.
  • Recursive Parallelization for Scalability: Fusion Blossom's recursive, tree-based parallelization strategy effectively breaks down large decoding problems into manageable chunks, enabling scalability to large code distances and high measurement volumes.
  • Batch vs. Stream Decoding Trade-offs: The paper highlights how different fusion tree structures (balanced, linear, mixed) allow for optimizing either overall throughput (batch decoding) or minimizing latency for real-time applications (stream decoding).

Key Results

  • Throughput: Fusion Blossom achieves a throughput of one million measurement rounds per second for a rotated surface code with a code distance of 33 and a physical error rate of 0.1%, using 64 CPU cores.
  • Latency: In stream decoding mode, Fusion Blossom achieves a constant average latency of 0.7 ms for a code distance of 21, regardless of the number of measurement rounds.
  • Scalability: The decoder scales well with code distance, with Parity Blossom showing near-linear scaling with the number of qubits. Fusion Blossom demonstrates significant speedups with increasing numbers of parallel threads.
  • Comparison to Baselines: Fusion Blossom outperforms traditional MWPM decoders (like Blossom V) and other fast decoders (like Sparse Blossom) in terms of throughput and latency, especially at high measurement volumes and large code distances.

Limitations and Future Work

  • Optimizations: The authors acknowledge that their implementation of Parity Blossom does not include all optimizations found in Sparse Blossom or Blossom V, suggesting potential for further speed improvements.
  • Hardware Implementation: While the paper focuses on software implementation, future work could explore hardware acceleration for even greater performance gains.
  • Error Model Complexity: The current work assumes a simplified circuit-level noise model. Extending the decoder to handle more complex noise models could be a future direction.
  • Trade-offs: The paper discusses trade-offs between decoding time and latency, and future work could involve more dynamic scheduling strategies to optimize these based on real-time system conditions.

Summary updated

BibTeX
@inproceedings{wu2023fusion,
  author = {Yue Wu and Lin Zhong},
  title = {{Fusion Blossom: Fast MWPM Decoders for QEC}},
  booktitle = {QCE},
  year = {2023},
  doi = {10.1109/qce57702.2023.00107},
}
Figure