PyMatching v2.0

[oscarhiggott]

This PR introduces major changes for the version 2.0 release:

Flagship changes:

• The C++ extension has been completely rewritten, and includes a new implementation of the blossom algorithm
• PyMatching v2.0 is now around 100-1000x faster than PyMatching v0.7 for decoding surface codes with circuit-level noise
• The new implementation is also exact. It does not make the "local matching" approximation used in v0.7 and earlier, which resulted in a reduction in accuracy for very large surface code circuits (fixes #29)
• The runtime of the new version is approximately linear in the size of the graph, and can process between 1 and 10 million detection events per second

Features and improvements

• Decoding speeds improved 100-1000x

• pymatching.Matching.load_from_check_matrix is around 30x faster

• Added methods to pymatching.Matching:

  • pymatching.Matching.add_boundary_edge
  • pymatching.Matching.decode_to_matched_dets_array (fixes #34)
  • pymatching.Matching.decode_to_matched_dets_dict
  • pymatching.Matching.has_edge
  • pymatching.Matching.get_edge_data
  • pymatching.Matching.set_min_num_fault_ids

• Added static methods to pymatching.Matching:

  • pymatching.Matching.from_detector_error_model
  • pymatching.Matching.from_check_matrix (static method equivalent to constructing a new pymatching.Matching and then calling pymatching.Matching.load_from_check_matrix)

• merge_strategy argument added to pymatching.Matching.add_edge, pymatching.Matching.add_boundary_edge and pymatching.Matching.load_from_check_matrix (fixes #33). When an attempt is made to add an edge already present in the graph, the following strategies are available:

  • disallow: raises a ValueError if a parallel edge is added
  • independent: edge weights and error probabilities updated treating the parallel edges as independent error mechanisms
  • smallest-weight: The edge with the smallest weight is kept
  • keep-original: The existing edge is kept and the new edge is silently ignored
  • replace: Only the edge being added is kept

• faults_matrix argument added to pymatching.Matching.from_check_matrix. faults_matrix is an array that can be used to set the fault_ids attribute of edges in a graph loaded from a check matrix. For example, faults_matrix can be used to specify the logical observables whose outcome should be predicted by the decoder.

Minor changes to the API

• spacelike_weights renamed to weights in pymatching.Matching.load_from_check_matrix. But spacelike_weights still accepted for backward compatibility.
• H renamed to graph in the constructor for pymatching.Matching. H still accepted for backward compatibility.
• precompute_shortest_paths argument removed from constructor (won't break if supplied)
• Both a virtual boundary node (via pymatching.Matching.add_boundary_edge) and a regular boundary node are supported. These are treated equivalently by the decoder, but are treated differently by pymatching.Matching.edges, pymatching.Matching.to_networkx and pymatching.Matching.to_retworkx

Minor breaking changes to the API

• pymatching.Matching.matching_graph renamed to pymatching.Matching._matching_graph (since this property is only intended to be used internally to access the C++ extension)
• pymatching.Matching.decode arguments after the first argument are now keyword-only, and num_neighbours has been removed as an argument. Users' code won't break or raise a warning if they already used keyword arguments (and num_neighbours is silently ignored when provided). If users provide num_neivhbours or return_weight as a positional argument, a deprecation warning is raised.
• pymatching.Matching.compute_all_pairs_shortest_paths method removed

Bug fixes

• Fixed a bug where timelike error probabilities were set incorrectly if provided as a scalar (fixes #35)