Repository: Qiskit/qiskit-terra (python)

Issue:
`SabreSwap` can reorder operations that depend on the same classical bit
### Environment

- **Qiskit Terra version**: main @ ef997f9
- **Python version**: any
- **Operating system**: any

### What is happening?

`SabreSwap` can re-order measurement operations (and probably classically conditioned gates) that write to the same classical bits.  This affects optimisation level 3 by default, since it uses sabre to route if nothing else is provided.

I am 95% sure this is the cause of the failures we're seeing in the randomised test suite currently.

<details><summary>Expand for logs of recent failed randomised run</summary>
Hypothesis failure at commit 618e0ea8b3daca194c1bde97292e57c15eddd762, in file `test/randomized/test_transpile_equivalence.py`

```text
Falsifying example:
state = QCircuitMachine()
state.qasm()
(v1,) = state.add_creg(n=1)
state.qasm()
v2, v3, v4 = state.add_qreg(n=3)
state.qasm()
state.add_3q_gate(gate=qiskit.circuit.library.standard_gates.x.CCXGate, qargs=[v4, v3, v2])
state.qasm()
state.add_1q1c_gate(carg=v1, gate=qiskit.circuit.measure.Measure, qarg=v3)
state.qasm()
state.add_1q2p_gate(gate=qiskit.circuit.library.standard_gates.u2.U2Gate, params=[0.0, 0.0], qarg=v4)
state.qasm()
state.add_1q1c_gate(carg=v1, gate=qiskit.circuit.measure.Measure, qarg=v4)
state.qasm()
Evaluating circuit at level 3 on fake_ourense:
OPENQASM 2.0;
include "qelib1.inc";
qreg q35069[3];
creg c1656[1];
ccx q35069[2],q35069[1],q35069[0];
measure q35069[1] -> c1656[0];
u2(0,0) q35069[2];
measure q35069[2] -> c1656[0];

state.equivalent_transpile(backend=<FakeOurense('fake_ourense')>, opt_level=3)
state.teardown()

You can reproduce this example by temporarily adding @reproduce_failure('6.43.2', b'AXicY2Bk5GFgYGDkZWBiYARCIBPIYmAE8thAbEYOBkwAkgKSrEBlzAALaABL') as a decorator on your test case
```
</details>

### How can we reproduce the issue?

Given a circuit:
```python
import qiskit

qc = qiskit.QuantumCircuit(3, 1)
qc.ccx(2, 1, 0)
qc.h(0)
qc.measure(0, 0)
qc.measure(1, 0)
```
which has a drawing
```text
     ┌───┐┌───┐┌─┐
q_0: ┤ X ├┤ H ├┤M├───
     └─┬─┘└───┘└╥┘┌─┐
q_1: ──■────────╫─┤M├
       │        ║ └╥┘
q_2: ──■────────╫──╫─
                ║  ║
c: 1/═══════════╩══╩═
                0  0
```
Clearly the output of the circuit should always be 0, because qubit 1 is never altered, and is measured second.

If we transpile it with a special coupling map that essentially only has one valid routing for the default decomposition of ccx, the orders of the measurements get flipped, which Aer confirms:
```python
transpiled = qiskit.transpile(qc, coupling_map=[[(0, 2), (2, 0), (1, 2), (2, 1)]], routing_method="sabre")
backend = qiskit.Aer.get_backend("aer_simulator")
print(backend.run(qc, shots=1024).result().get_counts())
print(backend.run(transpiled, shots=1024).result().get_counts())
```
This produces, for example:
```python
{'0': 1024}
{'1': 503, '0': 521}
```
but the second dictionary should be the same as the first.

(It's too long to draw `transpiled` here, but if you do it locally, you can see the measurements are swapped.)

### What should happen?

Sabre should take into account the topological ordering of measurements (and other clbits).  In the above examples, the counts should both be `{'0': 1024}` (which they are for any other routing method).

### Any suggestions?

In both `SabreSwap._successors` and `._is_resolved`, only the quantum bits are accounted for.  My very very rough intuition for what's going on makes it feel like it should account for _all_ successors, not just qubits.

Pull request description:
Make SabreSwap account for clbits in predecessors
### Summary

Previously, SabreSwap only checked that it was valid to add a gate back
to the DAG by ensuring that all its qubit predecessors had already been
added to the DAG.  It did not check for clbit successors.  This meant
that measurements and (potentially, unverified) classically conditioned
gates could be re-ordered out from the correct topological ordering.

The most notable effect of this was that measurements writing to the
same bit could be re-ordered, changing the output of the circuit.

See gh-7950 for more detail.

<!--
⚠️ If you do not respect this template, your pull request will be closed.
⚠️ Your pull request title should be short detailed and understandable for all.
⚠️ Also, please add a release note file using reno if the change needs to be
  documented in the release notes.
⚠️ If your pull request fixes an open issue, please link to the issue.

- [ ] I have added the tests to cover my changes.
- [ ] I have updated the documentation accordingly.
- [ ] I have read the CONTRIBUTING document.
-->



### Details and comments

Fix #7950.  I also believe this to be the cause of the sporadic randomised test failures (see an example in the linked issue).

Ali (@ajavadia) - this might be something you ought to look at, since I don't understand SabreSwap well.


Patch:
diff --git a/qiskit/transpiler/passes/routing/sabre_swap.py b/qiskit/transpiler/passes/routing/sabre_swap.py
index 3690c763f..5e44b29e5 100644
--- a/qiskit/transpiler/passes/routing/sabre_swap.py
+++ b/qiskit/transpiler/passes/routing/sabre_swap.py
@@ -18,7 +18,6 @@ from copy import copy, deepcopy
 import numpy as np
 
 from qiskit.circuit.library.standard_gates import SwapGate
-from qiskit.circuit.quantumregister import Qubit
 from qiskit.transpiler.basepasses import TransformationPass
 from qiskit.transpiler.exceptions import TranspilerError
 from qiskit.transpiler.layout import Layout
@@ -276,15 +275,18 @@ class SabreSwap(TransformationPass):
         self.qubits_decay = {k: 1 for k in self.qubits_decay.keys()}
 
     def _successors(self, node, dag):
-        for _, successor, edge_data in dag.edges(node):
-            if not isinstance(successor, DAGOpNode):
-                continue
-            if isinstance(edge_data, Qubit):
+        """Return an iterable of the successors along each wire from the given node.
+
+        This yields the same successor multiple times if there are parallel wires (e.g. two adjacent
+        operations that have one clbit and qubit in common), which is important in the swapping
+        algorithm for detecting if each wire has been accounted for."""
+        for _, successor, _ in dag.edges(node):
+            if isinstance(successor, DAGOpNode):
                 yield successor
 
     def _is_resolved(self, node):
         """Return True if all of a node's predecessors in dag are applied."""
-        return self.applied_predecessors[node] == len(node.qargs)
+        return self.applied_predecessors[node] == len(node.qargs) + len(node.cargs)
 
     def _obtain_extended_set(self, dag, front_layer):
         """Populate extended_set by looking ahead a fixed number of gates.
diff --git a/releasenotes/notes/fix-sabreswap-clbits-428eb5f3a46063da.yaml b/releasenotes/notes/fix-sabreswap-clbits-428eb5f3a46063da.yaml
new file mode 100644
index 000000000..0401e5a36
--- /dev/null
+++ b/releasenotes/notes/fix-sabreswap-clbits-428eb5f3a46063da.yaml
@@ -0,0 +1,9 @@
+---
+fixes:
+  - |
+    Fixed :class:`.SabreSwap`, and by extension :func:`.transpile` with
+    ``optimization_level=3``, occasionally re-ordering measurements invalidly.
+    Previously, if two measurements wrote to the same classical bit,
+    :class:`.SabreSwap` could (depending on the coupling map) re-order them to
+    produce a non-equivalent circuit.  This behaviour was stochastic, so may
+    not have appeared reliably.


Test patch:
diff --git a/test/python/transpiler/test_sabre_swap.py b/test/python/transpiler/test_sabre_swap.py
index a19f574a3..509225f65 100644
--- a/test/python/transpiler/test_sabre_swap.py
+++ b/test/python/transpiler/test_sabre_swap.py
@@ -13,6 +13,7 @@
 """Test the Sabre Swap pass"""
 
 import unittest
+from qiskit.circuit.library import CCXGate, HGate, Measure
 from qiskit.transpiler.passes import SabreSwap
 from qiskit.transpiler import CouplingMap, PassManager
 from qiskit import QuantumRegister, QuantumCircuit
@@ -95,6 +96,34 @@ class TestSabreSwap(QiskitTestCase):
 
         self.assertEqual(set(cm_edges), set(coupling.get_edges()))
 
+    def test_do_not_reorder_measurements(self):
+        """Test that SabreSwap doesn't reorder measurements to the same classical bit.
+
+        With the particular coupling map used in this test and the 3q ccx gate, the routing would
+        invariably the measurements if the classical successors are not accurately tracked.
+        Regression test of gh-7950."""
+        coupling = CouplingMap([(0, 2), (2, 0), (1, 2), (2, 1)])
+        qc = QuantumCircuit(3, 1)
+        qc.compose(CCXGate().definition, [0, 1, 2], [])  # Unroll CCX to 2q operations.
+        qc.h(0)
+        qc.barrier()
+        qc.measure(0, 0)  # This measure is 50/50 between the Z states.
+        qc.measure(1, 0)  # This measure always overwrites with 0.
+        passmanager = PassManager(SabreSwap(coupling))
+        transpiled = passmanager.run(qc)
+
+        last_h, h_qubits, _ = transpiled.data[-4]
+        self.assertIsInstance(last_h, HGate)
+        first_measure, first_measure_qubits, _ = transpiled.data[-2]
+        second_measure, second_measure_qubits, _ = transpiled.data[-1]
+        self.assertIsInstance(first_measure, Measure)
+        self.assertIsInstance(second_measure, Measure)
+        # Assert that the first measure is on the same qubit that the HGate was applied to, and the
+        # second measurement is on a different qubit (though we don't care which exactly - that
+        # depends a little on the randomisation of the pass).
+        self.assertEqual(h_qubits, first_measure_qubits)
+        self.assertNotEqual(h_qubits, second_measure_qubits)
+
 
 if __name__ == "__main__":
     unittest.main()