A fast minimumweight perfect matching solver for quantum error correction
Project description
Fusion Blossom
A fast MinimumWeight Perfect Matching (MWPM) solver for Quantum Error Correction (QEC)
Please see our tutorial for a quick explanation and some Python demos.
Key Features
 Correctness: This is an exact MWPM solver, verified against the Blossom V library with millions of randomized test cases .
 Linear Complexity: The decoding time is roughly $O(N)$ given small physical error rate, proportional to the number of syndrome vertices $N$.
 Parallelism: A single MWPM decoding problem can be partitioned and solved in parallel, then fused together to find an exact global MWPM solution.
 Simple Interface: The graph problem is abstracted and easytouse for QEC applications.
Benchmark Highlights
 In phenomenological noise model with $p$ = 0.005, code distance $d$ = 21, planar code with $d(d1)$ = 420 $Z$ stabilizers, 100000 measurement rounds
 singlethread: 2.4us per syndrome or 29us per measurement round
 64threads: 58ns per syndrome or 0.7us per measurement round
Background and Key Ideas
MWPM decoders are widely known for its high accuracy [1] and several optimizations that further improves its accuracy [2]. However, there weren't many publications that improve the speed of the MWPM decoder over the past 10 years. Fowler implemented an $O(N)$ asymptotic complexity MWPM decoder in [3] and proposed an $O(1)$ complexity parallel MWPM decoder in [4], but none of these are publicly available to our best knowledge. Higgott implemented a fast but approximate MWPM decoder (namely "local matching") with roughly $O(N)$ complexity in [5]. With recent experiments of successful QEC on real hardware, it's time for a fast and accurate MWPM decoder to become available to the community.
Our idea comes from our study on the UnionFind (UF) decoder [6]. UF decoder is a fast decoder with $O(N)$ worstcase time complexity, at the cost of being less accurate compared to the MWPM decoder. Inspired by the Fowler's diagram [3], we found a relationship between the UF decoder [7]. This nice animation (press space to trigger animation) could help people see the analogy between UF and MWPM decoders. With this interpretation, we're able to combind the strength of UF and MWPM decoders together.
 From the UF decoder, we learnt to use a sparse decoding graph representation for fast speed
 From the MWPM decoder, we learnt to find an exact minimumweight perfect matching for high accuracy
Demo
We highly suggest you watch through several demos here to get a sense of how the algorithm works. All our demos are captured from real algorithm execution. In fact, we're showing you the visualized debugger tool we wrote for fusion blossom. The demo is a 3D website and you can control the view point as you like.
For more details of why it finds an exact MWPM, please read our paper [coming soon 💪].
Click the demo image below to view the corresponding demo
Serial Execution
Parallel Execution (Shown in Serial For Better Visual)
Usage
Our code is written in Rust programming language for speed and memory safety, but it's hardly a easy language to learn. To make the decoder more accessible, we bind the library to Python and user can simply install the library using pip3 install fusionblossom
.
We have several Python demos at the tutorial website . Also there is a simple example for decoder, and you can run it by cloning the project and run python3 scripts/demo.py
.
For parallel solver, it needs user to provide a partition strategy. Please wait for our paper for a thorough description of how partition works.
Evaluation
We use Intel(R) Xeon(R) Platinum 8375C CPU for evaluation, with 64 physical cores and 128 threads. Note that Apple m1max CPU has roughly 2x singlecore decoding speed, but it has limited number of cores so we do not use data from m1max. By default, we test phenomenological noise model with $p$ = 0.005, code distance $d$ = 21, planar code with $d(d1)$ = 420 $Z$ stabilizers, 100000 measurement rounds.
First of all, the number of partitions will effect the speed. Intuitively, the more partitions there are, the more overhead because fusing two partitions consumes more computation than solving them as a whole. But in practice, memory access is not always at the same speed. If cache cannot hold the data, then solving big partition may consume even more time than solving small ones. We test on a singlethread decoder, and try different partition numbers. At partition number = 2000, we get roughly the minimum decoding time of 2.4us per syndrome. This corresponds to each partition hosting 50 measurement rounds (decoding blocks of 49 * 21 * 20).
Given the optimal partition number of a single thread, we keep the partition number the same and try increasing the number of threads. Note that the partition number may not be optimal for large number of threads, but even in this case, we reach 41x speed up given 64 physical cores. The decoding time is pushed to 58ns per sydnrome or 0.7us per measurement round. This can catch up with the 1us measurement round of a superconducting circuit. Interestingly, we found that hyperthreading won't help much in this case, perhaps because this decoder is memorybounded, meaning memory throughput is the bottleneck. Although the number of syndrome is only a small portion, they are randomly distributed so every time a new syndrome is given, the memory is almost always cold and incur large cache miss panelty.
In order to understand the bottleneck of parallel execution, we wrote a visualization tool to display the execution windows of base partitions and fusion operations on multiple threads. Blue blocks is the base partition and green blocks is the fusion operation. Fusion operation only scales with the size of the fusion boundary and the depth of active partitions, irrelevant to the base partition's size. We'll study different partition and fusion strategies in our paper. Below shows the parallel execution on 64 threads. Blue blocks are base partitions, each is a 49 * 21 * 20 decoding graph block. Green blocks are fusion blocks, each is a 1 * 21 * 20 decoding graph block sandwiched by two neighbor base partitions. You can click the image which jumps to this interactive visualization tool.
Interface
Sparse Decoding Graph and Integer Weights
The weights in QEC decoding graph are computed by taking the log of error probability, e.g. $w_e = \log{(1p)/p}$ or roughly $w_e = \log{p}$, we can safely use integers to save weights by e.g. multiplying the weights by 1e6 and truncate to nearest integer. In this way, the truncation error $\Delta w_e = 1$ of integer weights corresponds to relative error $\Delta p /{p}=10^{6}$ which is small enough. Suppose physical error rate $p$ is in the range of a positive f64
variable (2.2e308 to 1), the maximum weight is 7e7,which is well below the maximum value of a u32
variable (4.3e9). Since weights only sum up in our algorithm (no multiplication), u32
is large enough and accurate enough. By default we use usize
which is platform dependent (usually 64 bits), but you can
We use integer also for ease of migrating to FPGA implementation. In order to fit more vertices into a single FPGA, it's necessary to reduce the resource usage for each vertex. Integers are much cheaper than floatingpoint numbers, and also it allows flexible tradeoff between resource usage and accuracy, e.g. if all weights are equal, we can simply use a 2 bit integer.
Note that other libraries of MWPM solver like Blossom V also default to integer weights as well. Although one can change the macro to use floatingpoint weights, it's not recommended because "the code may even get stuck due to rounding errors".
Installation
Here is an example installation on Ubuntu20.04.
# install rust compiler and package manager
curl proto '=https' tlsv1.2 sSf https://sh.rustup.rs  sh
# install build dependencies
sudo apt install buildessential
Tests
In order to test the correctness of our MWPM solver, we need a groundtruth MWPM solver. Blossom V is widelyused in existing MWPM decoders, but according to the license we cannot embed it in this library. To run the test cases with ground truth comparison or enable the functions like blossom_v_mwpm
, you need to download this library at this website to a folder named blossomV
at the root directory of this git repo.
wget c https://pub.ist.ac.at/~vnk/software/blossom5v2.05.src.tar.gz O   tar xz
cp r blossom5v2.05.src/* blossomV/
rm r blossom5v2.05.src
Visualize
To start a server, run the following
cd visualize
npm install # to download packages
# you can choose to render locally or to view it in a browser interactively
# interactive: open url using a browser (Chrome recommended)
node index.js <url> <width> <height> # local render
# for example you can run the following command to get url
cd ..
cargo test visualize_paper_weighted_union_find_decoder  nocapture
TODOs
 support erasures in parallel solver
Acknowledgements
This project is funded by NSF MRI: Development of PARAGON: Control Instrument for Post NISQ Quantum Computing
References
[1] Fowler, Austin G., et al. "Topological code autotune." Physical Review X 2.4 (2012): 041003.
[2] Criger, Ben, and Imran Ashraf. "Multipath summation for decoding 2D topological codes." Quantum 2 (2018): 102.
[3] Fowler, Austin G., Adam C. Whiteside, and Lloyd CL Hollenberg. "Towards practical classical processing for the surface code: timing analysis." Physical Review A 86.4 (2012): 042313.
[4] Fowler, Austin G. "Minimum weight perfect matching of faulttolerant topological quantum error correction in average $ O (1) $ parallel time." arXiv preprint arXiv:1307.1740 (2013).
[5] Higgott, Oscar. "PyMatching: A Python package for decoding quantum codes with minimumweight perfect matching." ACM Transactions on Quantum Computing 3.3 (2022): 116.
[6] Delfosse, Nicolas, and Naomi H. Nickerson. "Almostlinear time decoding algorithm for topological codes." Quantum 5 (2021): 595.
[7] Wu, Yue. APS 2022 March Meeting Talk "Interpretation of UnionFind Decoder on Weighted Graphs and Application to XZZX Surface Code". Slides: https://us.wuyue98.cn/aps2022, Video: https://youtu.be/BbhqUHKPdQk
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for fusion_blossom0.1.4cp37abi3win_amd64.whl
Algorithm  Hash digest  

SHA256  c43f05a425f177063b4bca9d0fd40a9c94c5fb652212dbe88727b5f9aa81d7c6 

MD5  a906186e067f02c2d86d4e4a4de1575f 

BLAKE2b256  6f3fac51d6276c96764c0f51f475e725149b4a7202681c2946bf8d22bcbe6034 
Hashes for fusion_blossom0.1.4cp37abi3win32.whl
Algorithm  Hash digest  

SHA256  9ef118bac7f0066cf794b16ebdbeb2d6ad5fdcd6b7429dbaf23a880e34b323b1 

MD5  f32938712455b2d99d2c69cf4fffd5e3 

BLAKE2b256  4b51341d149e26883884e752da919436174e8ad7a03ae2fac816160204bb9a0b 
Hashes for fusion_blossom0.1.4cp37abi3musllinux_1_1_x86_64.whl
Algorithm  Hash digest  

SHA256  3173d37ae1b0f339150bdfe4cf233aa6f69fbf9f4da155e96a508a27fea05cc3 

MD5  fa1cc952fecf75e1a706b024b3a3c254 

BLAKE2b256  2c9074b6d59896f9df32b41bc63cdd61660e021eafe7b71fdd8da5421524cca5 
Hashes for fusion_blossom0.1.4cp37abi3manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm  Hash digest  

SHA256  2ba6ca3e3334e3a40904c52209588d0ed8513bb6d736a7edb4986c540ab733d3 

MD5  0b93b6cb24f346c468878527c9a5e1da 

BLAKE2b256  aebaa190a455a1fa9756adc11890f6de80b1f704e2464b3df21cb2368e0aecd4 
Hashes for fusion_blossom0.1.4cp37abi3macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl
Algorithm  Hash digest  

SHA256  1d331c1a3fb25a6df29a1ff99a2338c6bd97cb8f35e325f3ed2ba39ff33f0cfc 

MD5  cd156335ed2fca7639d9463b1fa45185 

BLAKE2b256  664eaff55839a97288c6fedfe5e6dc358e0679bae8b5dc2873c6f4cbc3f8dee8 