Search

US-12619903-B2 - Fast minimum-weight perfect matching (MWPM) decoder for quantum error correction

US12619903B2US 12619903 B2US12619903 B2US 12619903B2US-12619903-B2

Abstract

Provided herein are methods of solving minimum-weight perfect matching (MWPM) for quantum error correction. The methods include i) partitioning an algorithm into a dual module and a primal module; ii) computing a maximum update length in the dual module; iii) gathering a return value in the dual module, the return value including a growth event or a conflict event; iv) resolving a conflict in the primal module when the return value is the conflict event; and v) setting a growth state in the dual module for each of one or more nodes when the return value is the growth event.

Inventors

  • Yue Wu
  • Lin Zhong
  • Namitha Godawatte Liyanage

Assignees

  • YALE UNIVERSITY

Dates

Publication Date
20260505
Application Date
20240209

Claims (20)

  1. 1 . A method of solving minimum-weight perfect matching (MWPM) for quantum error correction, the method comprising: i) partitioning an algorithm into a dual module and a primal module; ii) computing a maximum update length in the dual module; iii) gathering a return value in the dual module, the return value including: a growth value; or a conflict value; iv) resolving a conflict event in the primal module when the return value is the conflict value; and v) setting a growth state for a node in the dual module when the return value is the growth value.
  2. 2 . The method of claim 1 , further comprising repeating steps ii through v until the step of computing the maximum update length returns an empty value.
  3. 3 . The method of claim 1 , wherein the algorithm works on the dual module and the primal module simultaneously.
  4. 4 . The method of claim 1 , further comprising growing all variables in the dual module in parallel.
  5. 5 . The method of claim 4 , wherein the growing includes a multiple-tree growth strategy.
  6. 6 . The method of claim 1 , wherein the algorithm includes the blossom algorithm.
  7. 7 . The method of claim 1 , wherein the dual module and the primal module are abstracted from implementation.
  8. 8 . The method of claim 1 , wherein the step of computing the maximum update length comprises a time complexity of O ( 1 ).
  9. 9 . The method of claim 1 , wherein the step of setting the growth state comprises a time complexity of O ( 1 ) for each of the one or more nodes.
  10. 10 . The method of claim 1 , wherein the return value includes the conflict value when one or more conflict events is detected in at least one edge of the node.
  11. 11 . The method of claim 10 , wherein the one or more conflict event includes a positive growing length of any of the at least one edges nodes leading to unsafe exploratory region overlapping.
  12. 12 . The method of claim 10 , wherein the conflict value includes at least two conflict events.
  13. 13 . The method of claim 12 , wherein the at least two conflict events are gathered in parallel.
  14. 14 . The method of claim 13 , wherein the at least two conflicts are gathered into a single conflict.
  15. 15 . The method of claim 14 , wherein the gathering into the single conflict includes a tree structure gathering.
  16. 16 . The method of claim 1 , wherein: the gathering step includes a time complexity of O (log (N)); and N is the number of edges of the node.
  17. 17 . The method of claim 16 , wherein the gathering step is completed in a single clock cycle.
  18. 18 . The method of claim 16 , wherein the method includes a constant clock cycle with O (log (N)) clock cycles.
  19. 19 . The method of claim 1 , wherein the growth state for the node includes grow, stay, or shrink.
  20. 20 . The method of claim 1 , further comprising, in the dual module, at least one of adding a syndrome event to one of the one or more nodes, forming a blossom node, removing a blossom node, or setting at least one edge to 0 weight when an erasure event is detected.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS The present application claims priority under 35 U.S.C. § 119(c) to U.S. Provisional Patent Application No. 63/444,632, filed Feb. 10, 2023, which application is incorporated herein by reference in its entirety. STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT This invention was made with government support under DE-SC0019406 awarded by the Department of Energy. The government has certain rights in the invention. BACKGROUND OF THE DISCLOSURE Minimum weight perfect matching (MWPM) decoders are widely known for their high accuracy. Although there have been several optimizations that further improved the accuracy of MWPM decoders, there have not been many improvements to the speed of the MWPM decoder over the past 10 years. An O(N) asymptotic complexity MWPM decoder was implemented in (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.), and an O(1) complexity parallel MWPM decoder was proposed in (Fowler, Austin G. “Minimum weight perfect matching of fault-tolerant topological quantum error correction in average O(1) parallel time.” arXiv preprint arXiv: 1307.1740 (2013).). Additionally, a fast but approximate MWPM decoder (namely “local matching”) with roughly O(N) complexity was implemented in (Higgott, Oscar. “PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching.” ACM Transactions on Quantum Computing 3.3 (2022): 1-16.). However, as high throughput and low latency are both important to realize a fault-tolerant quantum computer, there remains a need in the art for methods that improve on existing decoders by providing increased throughput and decreased latency. The present invention addresses this need. SUMMARY OF THE DISCLOSURE In one aspect a method of solving minimum-weight perfect matching (MWPM) for quantum error correction includes i) partitioning an algorithm into a dual module and a primal module; ii) computing a maximum update length in the dual module; iii) gathering a return value in the dual module, the return value including a growth value or a conflict value; iv) resolving a conflict event in the primal module when the return value is the conflict value; and v) setting a growth state for the node in the dual module when the return value is the growth value. In some embodiments, the growth state for the node includes grow, stay, or shrink. In some embodiments, the method further includes repeating steps ii through v until the step of computing the maximum update length returns an empty value. In some embodiments, the algorithm works on the dual module and the primal module simultaneously. In some embodiments, the method further includes growing all variables in the dual module in parallel. In some embodiments, the growing includes a multiple-tree growth strategy. In some embodiments, the algorithm includes the blossom algorithm. In some embodiments, the method further includes, in the dual module, at least one of adding a syndrome event to one of the one or more nodes, forming a blossom node, removing a blossom node, or setting at least one edge to 0 weight when an erasure event is detected. In some embodiments, the dual module and the primal module are abstracted from implementation. In some embodiments, the step of computing the maximum update length comprises a time complexity of O(1). In some embodiments, the step of setting the growth state comprises a time complexity of O(1) for each of the one or more nodes. In some embodiments, the gathering step includes a time complexity of O(log(N)), where N is the number of edges of the node. In some embodiments, the gathering step is completed in a single clock cycle. In some embodiments, the method includes a constant clock cycle with O(log(N)) clock cycles. In some embodiments, the return value includes the conflict value when one or more conflict events is detected in at least one edge of the node. In some embodiments, the one or more conflict event includes a positive growing length of any of the at least one edges nodes leading to unsafe exploratory region overlapping. In some embodiments, the conflict value includes at least two conflict events. In some embodiments, the at least two conflict events are gathered in parallel. In some embodiments, the at least two conflicts are gathered into a single conflict. In some embodiments, the gathering into the single conflict includes a tree structure gathering. BRIEF DESCRIPTION OF THE DRAWINGS For a fuller understanding of the nature and desired objects of the present invention, reference is made to the following detailed description taken in conjunction with the accompanying figures wherein like reference characters denote corresponding parts throughout the several views. FIG. 1 is an image showing a schematic of a decoding method. FIG. 2 is an image showing an example of a con