Built on

J. Edmonds and E. L. Johnson, “Matching, Euler tours and the Chinese postman,” Mathematical programming , 1973
1973
Earlier work this paper cites.
S. Micali and V. V. Vazirani, “An O ⁡ ( | V | | E | CLOSE O(\sqrt{|V|}|E| ) algoithm for finding maximum matching in general graphs,” in 21st Annual Symposium on Foundations of Computer Science (sfcs 1980) . IEEE, 1980
1980
Earlier work this paper cites.
W. Cook and A. Rohe, “Computing minimum-weight perfect matchings,” INFORMS journal on computing , 1999
1999
Earlier work this paper cites.
D. B. West et al. , Introduction to graph theory . Prentice hall Upper Saddle River, 2001, vol. 2, p. 149
2001
Earlier work this paper cites.
V. Kolmogorov, “Blossom V: a new implementation of a minimum cost perfect matching algorithm,” Mathematical Programming Computation , 2009
2009
Earlier work this paper cites.
B. Dezső, A. Jüttner, and P. Kovács, “LEMON–an open source C++ graph template library,” Electronic Notes in Theoretical Computer Science , 2011
2011
Earlier work this paper cites.
A. J. Landahl, J. T. Anderson, and P. R. Rice, “Fault-tolerant quantum computing with color codes,” arXiv preprint arXiv:1108.5738 , 2011
Original
2011
Earlier work this paper cites.
A. G. Fowler, A. C. Whiteside, and L. C. Hollenberg, “Towards practical classical processing for the surface code: Timing analysis,” Physical Review A , 2012
2012
Earlier work this paper cites.
A. G. Fowler, A. C. Whiteside, A. L. McInnes, and A. Rabbani, “Topological code autotune,” Physical Review X , 2012
2012
Earlier work this paper cites.
V. V. Vazirani, “A simplification of the MV matching algorithm and its proof,” arXiv preprint arXiv:1210.4594 , 2012
Original
2012
Earlier work this paper cites.
A. G. Fowler, “Minimum weight perfect matching of fault-tolerant topological quantum error correction in average o ⁡ ( 1 ) o(1) parallel time,” arXiv preprint arXiv:1307.1740 , 2013
Original
2013
Earlier work this paper cites.

Similar

B. M. Terhal, “Quantum error correction for quantum memories,” Reviews of Modern Physics , 2015
2015
Cited alongside, same era.
N. Delfosse and G. Zémor, “Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel,” Physical Review Research , vol. 2, no. 3, p. 033042, 2020
2020
Cited alongside, same era.
A. Holmes, M. R. Jokar, G. Pasandi, Y. Ding, M. Pedram, and F. T. Chong, “NISQ+: Boosting quantum computing power by approximating quantum error correction,” in 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA) . IEEE, 2020
2020
Cited alongside, same era.
S. Huang, M. Newman, and K. R. Brown, “Fault-tolerant weighted union-find decoding on the toric code,” Physical Review A , 2020
2020
Cited alongside, same era.
N. Delfosse and N. H. Nickerson, “Almost-linear time decoding algorithm for topological codes,” Quantum , 2021

Then

Y. Wu, N. Liyanage, and L. Zhong, “An interpretation of union-find decoder on weighted graphs,” arXiv preprint arXiv:2211.03288 , 2022
Original
2022
Later among the works it cites.
Y. Wu, S. Kolkowitz, S. Puri, and J. D. Thompson, “Erasure conversion for fault-tolerant quantum computing in alkaline earth rydberg atom arrays,” Nature communications , 2022
2022
Later among the works it cites.
J. D. Teoh, P. Winkel, H. K. Babla, B. J. Chapman, J. Claes, S. J. de Graaf, J. W. Garmon, W. D. Kalfus, Y. Lu, A. Maiti et al. , “Dual-rail encoding with superconducting cavities,” arXiv preprint arXiv:2212.12077 , 2022
Original
2022
Later among the works it cites.
E. C. Peterson and P. J. Karalekas, “A distributed blossom algorithm for minimum-weight perfect matching,” arXiv preprint arXiv:2210.14277 , 2022
Original
2022
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2023

Fusion Blossom: Fast MWPM Decoders for QEC

Wu, Yue, Zhong, Lin

Understand

The Minimum-Weight Perfect Matching (MWPM) decoder is widely used in Quantum Error Correction (QEC) decoding.

Despite its high accuracy, existing implementations of the MWPM decoder cannot catch up with quantum hardware, e.g., 1 million measurements per second for superconducting qubits.
They suffer from a backlog of measurements that grows exponentially and as a result, cannot realize the power of quantum computation.
We design and implement a fast MWPM decoder, called Parity Blossom, which reaches a time complexity almost proportional to the number of defect measurements.

Built on

J. Edmonds and E. L. Johnson, “Matching, Euler tours and the Chinese postman,” Mathematical programming , 1973
1973
Earlier work this paper cites.
S. Micali and V. V. Vazirani, “An O ⁡ ( | V | | E | CLOSE O(\sqrt{|V|}|E| ) algoithm for finding maximum matching in general graphs,” in 21st Annual Symposium on Foundations of Computer Science (sfcs 1980) . IEEE, 1980
1980
Earlier work this paper cites.
W. Cook and A. Rohe, “Computing minimum-weight perfect matchings,” INFORMS journal on computing , 1999
1999
Earlier work this paper cites.
D. B. West et al. , Introduction to graph theory . Prentice hall Upper Saddle River, 2001, vol. 2, p. 149
2001
Earlier work this paper cites.
V. Kolmogorov, “Blossom V: a new implementation of a minimum cost perfect matching algorithm,” Mathematical Programming Computation , 2009
2009
Earlier work this paper cites.
B. Dezső, A. Jüttner, and P. Kovács, “LEMON–an open source C++ graph template library,” Electronic Notes in Theoretical Computer Science , 2011
2011
Earlier work this paper cites.
A. J. Landahl, J. T. Anderson, and P. R. Rice, “Fault-tolerant quantum computing with color codes,” arXiv preprint arXiv:1108.5738 , 2011
Original
2011
Earlier work this paper cites.
A. G. Fowler, A. C. Whiteside, and L. C. Hollenberg, “Towards practical classical processing for the surface code: Timing analysis,” Physical Review A , 2012
2012
Earlier work this paper cites.
A. G. Fowler, A. C. Whiteside, A. L. McInnes, and A. Rabbani, “Topological code autotune,” Physical Review X , 2012
2012
Earlier work this paper cites.
V. V. Vazirani, “A simplification of the MV matching algorithm and its proof,” arXiv preprint arXiv:1210.4594 , 2012
Original
2012
Earlier work this paper cites.
A. G. Fowler, “Minimum weight perfect matching of fault-tolerant topological quantum error correction in average o ⁡ ( 1 ) o(1) parallel time,” arXiv preprint arXiv:1307.1740 , 2013
Original
2013
Earlier work this paper cites.

Similar

B. M. Terhal, “Quantum error correction for quantum memories,” Reviews of Modern Physics , 2015
2015
Cited alongside, same era.
N. Delfosse and G. Zémor, “Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel,” Physical Review Research , vol. 2, no. 3, p. 033042, 2020
2020
Cited alongside, same era.
A. Holmes, M. R. Jokar, G. Pasandi, Y. Ding, M. Pedram, and F. T. Chong, “NISQ+: Boosting quantum computing power by approximating quantum error correction,” in 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA) . IEEE, 2020
2020
Cited alongside, same era.
S. Huang, M. Newman, and K. R. Brown, “Fault-tolerant weighted union-find decoding on the toric code,” Physical Review A , 2020
2020
Cited alongside, same era.
N. Delfosse and N. H. Nickerson, “Almost-linear time decoding algorithm for topological codes,” Quantum , 2021

Then

Y. Wu, N. Liyanage, and L. Zhong, “An interpretation of union-find decoder on weighted graphs,” arXiv preprint arXiv:2211.03288 , 2022
Original
2022
Later among the works it cites.
Y. Wu, S. Kolkowitz, S. Puri, and J. D. Thompson, “Erasure conversion for fault-tolerant quantum computing in alkaline earth rydberg atom arrays,” Nature communications , 2022
2022
Later among the works it cites.
J. D. Teoh, P. Winkel, H. K. Babla, B. J. Chapman, J. Claes, S. J. de Graaf, J. W. Garmon, W. D. Kalfus, Y. Lu, A. Maiti et al. , “Dual-rail encoding with superconducting cavities,” arXiv preprint arXiv:2212.12077 , 2022
Original
2022
Later among the works it cites.
E. C. Peterson and P. J. Karalekas, “A distributed blossom algorithm for minimum-weight perfect matching,” arXiv preprint arXiv:2210.14277 , 2022
Original
2022
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2021

Cited alongside, same era.

S.-s. Lee, Y. Yu, Y. Tang, A. Khandelwal, L. Zhong, and A. Bhattacharjee, “MIND: In-network memory management for disaggregated data centers,” in Proc. ACM SIGOPS Symposium on Operating Systems Principles , 2021

2021

Cited alongside, same era.

Y. Ueno, M. Kondo, M. Tanaka, Y. Suzuki, and Y. Tabuchi, “QECOOL: On-line quantum error correction with a superconducting decoder for surface code,” in 2021 58th ACM/IEEE Design Automation Conference (DAC) . IEEE, 2021

2021

Cited alongside, same era.

P. Das, C. A. Pattison, S. Manne, D. M. Carmean, K. M. Svore, M. Qureshi, and N. Delfosse, “AFS: Accurate, fast, and scalable error-decoding for fault-tolerant quantum computers,” in 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA) . IEEE, 2022

2022

Cited alongside, same era.

L. Skoric, D. E. Browne, K. M. Barnes, N. I. Gillespie, and E. T. Campbell, “Parallel window decoding enables scalable fault tolerant quantum computation,” arXiv preprint arXiv:2209.08552 , 2022

Original

2022

Cited alongside, same era.

X. Tan, F. Zhang, R. Chao, Y. Shi, and J. Chen, “Scalable surface code decoders with parallelization in time,” arXiv preprint arXiv:2209.09219 , 2022

Original

2022

Cited alongside, same era.

“Fusion Blossom: a fast minimum-weight perfect matching (MWPM) solver for quantum error correction (QEC).” [Online]. Available: https://github.com/yale-paragon/fusion-blossom

Cited in the paper.

“Python binding of Fusion Blossom library.” [Online]. Available: https://pypi.org/project/fusion-blossom

Cited in the paper.

——, “QULATIS: A quantum error correction methodology toward lattice surgery,” in 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA) . IEEE, 2022

2022

Later among the works it cites.

O. Higgott and C. Gidney, “Sparse Blossom: correcting a million errors per core second with minimum-weight matching,” arXiv preprint arXiv:2303.15933 , 2023

Original

2023

Closest in time.

N. Liyanage, Y. Wu, A. Deters, and L. Zhong, “Scalable quantum error correction for surface codes using fpga,” arXiv preprint arXiv:2301.08419 , 2023

Original

2023

Closest in time.

“Suppressing quantum errors by scaling a surface code logical qubit,” Nature , 2023

2023

Closest in time.

H. Bombín, C. Dawson, Y.-H. Liu, N. Nickerson, F. Pastawski, and S. Roberts, “Modular decoding: parallelizable real-time decoding for quantum computers,” arXiv preprint arXiv:2303.04846 , 2023

Original

2023

Closest in time.

G. S. Ravi, J. Baker, A. Fayyazi, S. Lin, A. Javadi-Abhari, M. Pedram, and F. Chong, “Better than worst-case decoding for quantum error correction,” Bulletin of the American Physical Society , 2023

2023

Closest in time.