Repository: Qiskit/qiskit-terra (python)

Issue:
`SabreSwap` can throw away classically conditioned gates and all successors
### Environment

- **Qiskit Terra version**: main @ 7726d4704
- **Python version**: any
- **Operating system**: any


### What is happening?

The `SabreSwap` transpiler pass can sometimes remove classically conditioned gates from the circuit, and all their successors, whether or not the successors have classical conditions.

This is (I believe) the cause of the current failures in the randomised test suite (from https://github.com/Qiskit/qiskit-terra/issues/2645#issuecomment-1111747082 to https://github.com/Qiskit/qiskit-terra/issues/2645#issuecomment-1121930469).

### How can we reproduce the issue?

```python
In [1]: from qiskit import QuantumCircuit
   ...: from qiskit.transpiler import PassManager, CouplingMap
   ...: from qiskit.transpiler.passes import SabreSwap, TrivialLayout
   ...:
   ...: qc = QuantumCircuit(2, 1)
   ...: qc.z(0)
   ...: qc.z(0).c_if(qc.cregs[0], 0)
   ...: print(qc.draw())
   ...: print()
   ...: cm = CouplingMap([(0, 1), (1, 0)])
   ...: print(PassManager([TrivialLayout(cm), SabreSwap(cm)]).run(qc).draw())
     ┌───┐ ┌───┐
q_0: ┤ Z ├─┤ Z ├─
     └───┘ └─╥─┘
q_1: ────────╫───
          ┌──╨──┐
c: 1/═════╡ 0x0 ╞
          └─────┘

         ┌───┐
q_0 -> 0 ┤ Z ├
         └───┘
q_1 -> 1 ─────
              
    c: 1/═════           
```

### What should happen?

The transpiled circuit should not have lost the second classically controlled gate.

### Any suggestions?

Conditions currently aren't being accounted for in the "expected number of predecessors" calculation that determines whether a gate is eligible to be added to the circuit.  The current `_is_resolved` check, since #7952, is:
```python
self.applied_predecessors[node] == len(node.qargs) + len(node.cargs)
```
but conditions are not part of the `cargs`.  Since the condition is _equality_ to the known value, if the relevant node is not in the original front layer, its `applied_predecessors` (which correctly account for conditions) can be increased beyond the count of its qargs and cargs, so the condition never triggers.

(#7952 didn't cause this issue, it just didn't completely address the issue of all classical arguments.)

The fix is to account for all possible predecessors in `SabreSwap._is_resolved`.

Pull request:
Fix SabreSwap with classically conditioned gates
### Summary

The calculation of the expected number of predecessors for a gate to
be considered "resolved" in `SabreSwap` was not accounting for wires
stemming from classical conditions.  The tracking of the _actual_ number
of predecessor requirements satisfied did correctly account for this, so
in certain circumstances the actual count could jump from "too low" to
"too high" without passing through "just right", and the gate would
never get added to the circuit.

<!--
⚠️ 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 #8040.

Patch:
diff --git a/qiskit/transpiler/passes/routing/sabre_swap.py b/qiskit/transpiler/passes/routing/sabre_swap.py
index c6555b069..1a1530508 100644
--- a/qiskit/transpiler/passes/routing/sabre_swap.py
+++ b/qiskit/transpiler/passes/routing/sabre_swap.py
@@ -139,7 +139,7 @@ class SabreSwap(TransformationPass):
         self.heuristic = heuristic
         self.seed = seed
         self.fake_run = fake_run
-        self.applied_predecessors = None
+        self.required_predecessors = None
         self.qubits_decay = None
         self._bit_indices = None
         self.dist_matrix = None
@@ -188,12 +188,9 @@ class SabreSwap(TransformationPass):
         self.qubits_decay = dict.fromkeys(dag.qubits, 1)
 
         # Start algorithm from the front layer and iterate until all gates done.
+        self.required_predecessors = self._build_required_predecessors(dag)
         num_search_steps = 0
         front_layer = dag.front_layer()
-        self.applied_predecessors = defaultdict(int)
-        for _, input_node in dag.input_map.items():
-            for successor in self._successors(input_node, dag):
-                self.applied_predecessors[successor] += 1
 
         while front_layer:
             execute_gate_list = []
@@ -228,7 +225,7 @@ class SabreSwap(TransformationPass):
                 for node in execute_gate_list:
                     self._apply_gate(mapped_dag, node, current_layout, canonical_register)
                     for successor in self._successors(node, dag):
-                        self.applied_predecessors[successor] += 1
+                        self.required_predecessors[successor] -= 1
                         if self._is_resolved(successor):
                             front_layer.append(successor)
 
@@ -314,6 +311,15 @@ class SabreSwap(TransformationPass):
         """
         self.qubits_decay = {k: 1 for k in self.qubits_decay.keys()}
 
+    def _build_required_predecessors(self, dag):
+        out = defaultdict(int)
+        # We don't need to count in- or out-wires: outs can never be predecessors, and all input
+        # wires are automatically satisfied at the start.
+        for node in dag.op_nodes():
+            for successor in self._successors(node, dag):
+                out[successor] += 1
+        return out
+
     def _successors(self, node, dag):
         """Return an iterable of the successors along each wire from the given node.
 
@@ -326,22 +332,22 @@ class SabreSwap(TransformationPass):
 
     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) + len(node.cargs)
+        return self.required_predecessors[node] == 0
 
     def _obtain_extended_set(self, dag, front_layer):
         """Populate extended_set by looking ahead a fixed number of gates.
         For each existing element add a successor until reaching limit.
         """
         extended_set = []
-        incremented = []
+        decremented = []
         tmp_front_layer = front_layer
         done = False
         while tmp_front_layer and not done:
             new_tmp_front_layer = []
             for node in tmp_front_layer:
                 for successor in self._successors(node, dag):
-                    incremented.append(successor)
-                    self.applied_predecessors[successor] += 1
+                    decremented.append(successor)
+                    self.required_predecessors[successor] -= 1
                     if self._is_resolved(successor):
                         new_tmp_front_layer.append(successor)
                         if len(successor.qargs) == 2:
@@ -350,8 +356,8 @@ class SabreSwap(TransformationPass):
                     done = True
                     break
             tmp_front_layer = new_tmp_front_layer
-        for node in incremented:
-            self.applied_predecessors[node] -= 1
+        for node in decremented:
+            self.required_predecessors[node] += 1
         return extended_set
 
     def _obtain_swaps(self, front_layer, current_layout):
diff --git a/releasenotes/notes/sabreswap-fix-condition-593f36e855f9064c.yaml b/releasenotes/notes/sabreswap-fix-condition-593f36e855f9064c.yaml
new file mode 100644
index 000000000..376014ce4
--- /dev/null
+++ b/releasenotes/notes/sabreswap-fix-condition-593f36e855f9064c.yaml
@@ -0,0 +1,8 @@
+---
+fixes:
+  - |
+    The :class:`.SabreSwap` transpiler pass, used in :func:`.transpile` when
+    ``routing_method="sabre"`` is set, will no longer sporadically drop
+    classically conditioned gates and their successors from circuits during the
+    routing phase of transpilation.  See
+    `#8040 <https://github.com/Qiskit/qiskit-terra/issues/8040>`__.


Test patch:
diff --git a/test/python/transpiler/test_sabre_swap.py b/test/python/transpiler/test_sabre_swap.py
index f7a9e96cf..89e43b914 100644
--- a/test/python/transpiler/test_sabre_swap.py
+++ b/test/python/transpiler/test_sabre_swap.py
@@ -17,9 +17,9 @@ import unittest
 import ddt
 
 from qiskit.circuit.library import CCXGate, HGate, Measure, SwapGate
-from qiskit.transpiler.passes import SabreSwap
+from qiskit.transpiler.passes import SabreSwap, TrivialLayout
 from qiskit.transpiler import CouplingMap, PassManager
-from qiskit import QuantumRegister, QuantumCircuit
+from qiskit import ClassicalRegister, QuantumRegister, QuantumCircuit
 from qiskit.test import QiskitTestCase
 from qiskit.utils import optionals
 
@@ -237,6 +237,31 @@ class TestSabreSwap(QiskitTestCase):
         out_results = sim.run(routed, shots=4096).result().get_counts()
         self.assertEqual(set(in_results), set(out_results))
 
+    def test_classical_condition(self):
+        """Test that :class:`.SabreSwap` correctly accounts for classical conditions in its
+        reckoning on whether a node is resolved or not.  If it is not handled correctly, the second
+        gate might not appear in the output.
+
+        Regression test of gh-8040."""
+        with self.subTest("1 bit in register"):
+            qc = QuantumCircuit(2, 1)
+            qc.z(0)
+            qc.z(0).c_if(qc.cregs[0], 0)
+            cm = CouplingMap([(0, 1), (1, 0)])
+            expected = PassManager([TrivialLayout(cm)]).run(qc)
+            actual = PassManager([TrivialLayout(cm), SabreSwap(cm)]).run(qc)
+            self.assertEqual(expected, actual)
+        with self.subTest("multiple registers"):
+            cregs = [ClassicalRegister(3), ClassicalRegister(4)]
+            qc = QuantumCircuit(QuantumRegister(2, name="q"), *cregs)
+            qc.z(0)
+            qc.z(0).c_if(cregs[0], 0)
+            qc.z(0).c_if(cregs[1], 0)
+            cm = CouplingMap([(0, 1), (1, 0)])
+            expected = PassManager([TrivialLayout(cm)]).run(qc)
+            actual = PassManager([TrivialLayout(cm), SabreSwap(cm)]).run(qc)
+            self.assertEqual(expected, actual)
+
 
 if __name__ == "__main__":
     unittest.main()