PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching

• URL: http://arxiv.org/abs/2105.13082v2
• Date: Mon, 12 Jul 2021 20:20:56 GMT
• Title: PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching
• Authors: Oscar Higgott
• Abstract summary: PyMatching is a package for decoding quantum error-correcting codes with the minimum-weight perfect matching (MWPM) algorithm. PyMatching supports the use of weighted edges, hook errors, boundaries and measurement errors, enabling fast decoding and simulation of fault-tolerant quantum computing.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces PyMatching, a fast open-source Python package for decoding quantum error-correcting codes with the minimum-weight perfect matching (MWPM) algorithm. PyMatching includes the standard MWPM decoder as well as a variant, which we call local matching, that restricts each syndrome defect to be matched to another defect within a local neighbourhood. The decoding performance of local matching is almost identical to that of the standard MWPM decoder in practice, while reducing the computational complexity approximately quadratically. We benchmark the performance of PyMatching, showing that local matching is several orders of magnitude faster than implementations of the full MWPM algorithm using NetworkX or Blossom V for problem sizes typically considered in error correction simulations. PyMatching and its dependencies are open-source, and it can be used to decode any quantum code for which syndrome defects come in pairs using a simple Python interface. PyMatching supports the use of weighted edges, hook errors, boundaries and measurement errors, enabling fast decoding and simulation of fault-tolerant quantum computing.

Related papers

• Improved accuracy for decoding surface codes with matching synthesis [0.40182506671515367]
  We present a method, called matching synthesis, for decoding quantum codes that produces an enhanced assignment of errors from an ensemble of decoders. Matching synthesis takes the solutions of an ensemble of approximate solvers for the minimum-weight hypergraph matching problem. We show that matching synthesis has favorable scaling properties where accuracy begins to saturate with an ensemble size of 60.
  arXiv  Detail & Related papers  (2024-08-22T05:34:36Z)
• Let the Code LLM Edit Itself When You Edit the Code [50.46536185784169]
  underlinetextbfPositional textbfIntegrity textbfEncoding (PIE) PIE reduces computational overhead by over 85% compared to the standard full recomputation approach. Results demonstrate that PIE reduces computational overhead by over 85% compared to the standard full recomputation approach.
  arXiv  Detail & Related papers  (2024-07-03T14:34:03Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• Hardness results for decoding the surface code with Pauli noise [0.0]
  We show that quantum maximum likelihood decoding (QMLD) and degenerate quantum maximum likelihood decoding (DQMLD) for the surface code are NP-hard and #P-hard, respectively. We transform a formula into a qubit-dependent Pauli noise model and set of syndromes that encode the satisfiability properties of the formula.
  arXiv  Detail & Related papers  (2023-09-19T05:29:01Z)
• QDistRnd: A GAP package for computing the distance of quantum error-correcting codes [0.029541734875307393]
  GAP package QDistRnd implements a probabilistic algorithm for finding the minimum distance of a quantum low-density parity-check code linear over a finite field GF(q)
  arXiv  Detail & Related papers  (2023-08-29T09:17:57Z)
• Sparse Blossom: correcting a million errors per core second with minimum-weight matching [0.0]
  We introduce a fast implementation of the minimum-weight perfect matching (MWPM) decoder. Our algorithm, which we call sparse blossom, is a variant of the blossom algorithm which directly solves the decoding problem relevant to quantum error correction.
  arXiv  Detail & Related papers  (2023-03-28T12:42:54Z)
• Scalable Quantum Error Correction for Surface Codes using FPGA [67.74017895815125]
  A fault-tolerant quantum computer must decode and correct errors faster than they appear. We report a distributed version of the Union-Find decoder that exploits parallel computing resources for further speedup. The implementation employs a scalable architecture called Helios that organizes parallel computing resources into a hybrid tree-grid structure.
  arXiv  Detail & Related papers  (2023-01-20T04:23:00Z)
• Pipelined correlated minimum weight perfect matching of the surface code [56.01788646782563]
  We describe a pipeline approach to decoding the surface code using minimum weight perfect matching. An independent no-communication parallelizable processing stage reweights the graph according to likely correlations. A later general stage finishes the matching. We validate the new algorithm on the fully fault-tolerant toric, unrotated, and rotated surface codes.
  arXiv  Detail & Related papers  (2022-05-19T19:58:02Z)
• pygrank: A Python Package for Graph Node Ranking [13.492381728793612]
  We introduce pygrank, an open source Python package to define, run and evaluate node ranking algorithms. We provide object-oriented and extensively unit-tested algorithm components, such as graph filters, post-processors, measures, benchmarks and online tuning.
  arXiv  Detail & Related papers  (2021-10-18T13:13:21Z)
• OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
  Mixed precision quantization takes advantage of hardware's multiple bit-width arithmetic operations to unleash the full potential of network quantization. We propose to optimize a proxy metric, the concept of networkity, which is highly correlated with the loss of the integer programming. This approach reduces the search time and required data amount by orders of magnitude, with little compromise on quantization accuracy.
  arXiv  Detail & Related papers  (2021-09-16T10:59:33Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.