Incompatibility with pymatching

[quantumjim]

Steps to reproduce the problem

Run tests.

What is the current behavior?

Multiple tests involving PyMatching are failing.

======================================================================
ERROR: test_d3_10 (heavy_hex_codes.test_heavy_hex_decoder.TestHHCDecoder)
Check 3, zx, x, pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 323, in test_d3_10
    self.correct_all_1(c, circ, dec, self.model, 0, True)
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 71, in correct_all_1
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_d3_2 (heavy_hex_codes.test_heavy_hex_decoder.TestHHCDecoder)
Check 3, zx, z, pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 149, in test_d3_2
    self.correct_all_1(c, circ, dec, self.model)
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 71, in correct_all_1
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_d3_5 (heavy_hex_codes.test_heavy_hex_decoder.TestHHCDecoder)
Check 1, zxzxzx, z, pymatching, logical=xyzxyz.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 235, in test_d3_5
    self.correct_all_1(c, circ, dec, self.model)
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 71, in correct_all_1
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_d3_7 (heavy_hex_codes.test_heavy_hex_decoder.TestHHCDecoder)
Check 3, zx, z, pymatching, -1 eigenstate.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 280, in test_d3_7
    self.correct_all_1(c, circ, dec, self.model, 0, False, "propagator")
  File "/Users/jwo/Desktop/qiskit-qec/tests/heavy_hex_codes/test_heavy_hex_decoder.py", line 71, in correct_all_1
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_correct_single_errors_pymatching (matching.test_circuitmatcher.TestCircuitMatcher)
Test the case with single faults using pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_circuitmatcher.py", line 215, in test_correct_single_errors_pymatching
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_correct_single_errors_pymatching_uniform (matching.test_circuitmatcher.TestCircuitMatcher)
Test the case with single faults using pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_circuitmatcher.py", line 241, in test_correct_single_errors_pymatching_uniform
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_error_pairs_propagator_pymatching (matching.test_circuitmatcher.TestCircuitMatcher)
Test the case with two faults using error propagator and pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_circuitmatcher.py", line 324, in test_error_pairs_propagator_pymatching
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_error_pairs_propagator_pymatching_uniform (matching.test_circuitmatcher.TestCircuitMatcher)
Test the case with two faults using error propagator and pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_circuitmatcher.py", line 352, in test_error_pairs_propagator_pymatching_uniform
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_match (matching.test_pymatchingmatcher.TestPyMatchingMatcher)
Test matching example.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_pymatchingmatcher.py", line 39, in test_match
    qubit_errors, measurement_errors = self.m.find_errors(graph, idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_correct_single_errors_pymatching (matching.test_repetitionmatcher.TestRepetitionCircuitMatcher)
Test the case with two faults using pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_repetitionmatcher.py", line 92, in test_correct_single_errors_pymatching
    self.test_correct_single_errors(method="pymatching")
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_repetitionmatcher.py", line 86, in test_correct_single_errors
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

======================================================================
ERROR: test_error_pairs_pymatching (matching.test_repetitionmatcher.TestRepetitionCircuitMatcher)
Test the case with two faults on a d=5 code using pymatching.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_repetitionmatcher.py", line 112, in test_error_pairs_pymatching
    self.test_error_pairs(dec_method="pymatching", fe_method="stabilizer")
  File "/Users/jwo/Desktop/qiskit-qec/tests/matching/test_repetitionmatcher.py", line 105, in test_error_pairs
    corrected_outcomes = dec.process(outcome)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/circuit_matching_decoder.py", line 563, in process
    qubit_errors, _ = self.matcher.find_errors(self.graph, self.idxmap, highlighted)
  File "/Users/jwo/Desktop/qiskit-qec/qiskit_qec/decoders/pymatching_matcher.py", line 57, in find_errors
    correction = self.pymatching.decode(syndrome)
  File "/Users/jwo/Desktop/qiskit-qec/.tox/py39/lib/python3.9/site-packages/pymatching/matching.py", line 320, in decode
    correction, weight = self._matching_graph.decode(detection_events)
ValueError: No perfect matching could be found. This likely means that the syndrome has odd parity in the support of a connected component without a boundary.

----------------------------------------------------------------------

[mtreinish]

There was a major version release for pymatching yesterday: https://github.com/oscarhiggott/PyMatching/releases/tag/v2.0.0 you'll probably need to update the usage for the new version, or in the short term pin the version < 2.0 until you update the usage.

[oscarhiggott]

I've now fixed this issue in pymatching in this PR and made a new patch release (v2.0.1) that includes the fix.

The issue was that I wasn't handling the case that the user adds a detection event on the boundary node in v2.0.0. There's never any need to add detection events to boundary nodes, as the boundary is handled automatically by the decoder. But now these boundary node detection events are ignored, as they were in v0.7.

I also just opened PR #280 which fixes a couple of minor remaining issues caused by the upgrade to v2.0.1. See the PR for details. PR #280 is intended to replace #278.

[quantumjim]

Thanks @oscarhiggott!