Repository: Qiskit/qiskit-terra (python)

Issue:
SabreLayout does not terminate in some cases
### Environment

Qiskit version: master
Python version: 3.8.8
OS: Mac OS 12.2

### What is happening?

SabreSwap gets stuck in some specific cases and does not make forward progress.



### How can we reproduce the issue?

here's an example that runs indefinitely for me. Note that even though I run SabreLayout, internally it is calling SabreSwap and that's where it gets stuck.

```py
from qiskit.circuit.library import QuantumVolume
from qiskit.transpiler import PassManager, CouplingMap
from qiskit.transpiler.passes import SabreLayout

n = 30
coupling_map = CouplingMap.from_line(n)
basis_gates=['cx', 'u']
qv = QuantumVolume(n, seed=983).decompose()
pm = PassManager(SabreLayout(coupling_map, seed=1))
pm.run(qv)
```

### What should happen?

map the circuit and terminate

### Any suggestions?

I think the SabreSwap algorithm has a way to score different swap options and to make forward progress, so not sure what's going on.

Pull request description:
Fix potential infinite loop in SabreSwap
### Summary

This adds a "release valve" mechanism to `SabreSwap`, so that it will
always eventually make forwards progress and terminate the run.  Before
this commit, it was possible for certain pathological circuits
(see `looping_circuit` in `test/python/transpiler/test_sabre_swap.py`
for an example) to get stuck in a stable local minimum of the
'lookahead' or 'decay' heuristics (no matter the weightings).

The release mechanism is done with very small per-loop overhead for the
vastly more common good paths; we simply count how many iterations we
have been through since we made progress, and the minimum weight in the
coupling map to be overcome to make progress again.  Once the
number of iterations without progress exceeds some value, we backtrack
(inefficiently, because this is the bad path) to the last time we made
progress, and forcibly insert swaps to bring the nearest gate together.
We then continue like normal.

There are also a few minor optimisations in this commit that prevent
recalculating sets that we already know; `extended_set` is fixed by
knowledge of the `front_layer` if the DAG isn't (meaningfully) changed,
so there's no need to recalculate it on each loop.

<!--
⚠️ 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 #7707.

This commit also knocks off some of the low-hanging fruit in the efficiency of the `SabreSwap` implementation, since I had to touch it anyway; we don't recalculate the `extended_set` on each iteration if no progress on the first layer has been made, because it shouldn't have changed.  We just store it and move on.  This is good for a 25-30% speedup in `SabreSwap` for 20 qubits at a depth of 1024, and it passes some savings on to a general `transpile(optimization_level=3)`, which is most notable for QV circuits.

Patch:
diff --git a/qiskit/transpiler/passes/routing/sabre_swap.py b/qiskit/transpiler/passes/routing/sabre_swap.py
index 5e44b29e5..c6555b069 100644
--- a/qiskit/transpiler/passes/routing/sabre_swap.py
+++ b/qiskit/transpiler/passes/routing/sabre_swap.py
@@ -15,7 +15,9 @@
 import logging
 from collections import defaultdict
 from copy import copy, deepcopy
+
 import numpy as np
+import retworkx
 
 from qiskit.circuit.library.standard_gates import SwapGate
 from qiskit.transpiler.basepasses import TransformationPass
@@ -64,7 +66,13 @@ class SabreSwap(TransformationPass):
     `arXiv:1809.02573 <https://arxiv.org/pdf/1809.02573.pdf>`_
     """
 
-    def __init__(self, coupling_map, heuristic="basic", seed=None, fake_run=False):
+    def __init__(
+        self,
+        coupling_map,
+        heuristic="basic",
+        seed=None,
+        fake_run=False,
+    ):
         r"""SabreSwap initializer.
 
         Args:
@@ -153,6 +161,14 @@ class SabreSwap(TransformationPass):
         if len(dag.qubits) > self.coupling_map.size():
             raise TranspilerError("More virtual qubits exist than physical.")
 
+        max_iterations_without_progress = 10 * len(dag.qubits)  # Arbitrary.
+        ops_since_progress = []
+        extended_set = None
+
+        # Normally this isn't necessary, but here we want to log some objects that have some
+        # non-trivial cost to create.
+        do_expensive_logging = logger.isEnabledFor(logging.DEBUG)
+
         self.dist_matrix = self.coupling_map.distance_matrix
 
         rng = np.random.default_rng(self.seed)
@@ -169,7 +185,7 @@ class SabreSwap(TransformationPass):
 
         # A decay factor for each qubit used to heuristically penalize recently
         # used qubits (to encourage parallelism).
-        self.qubits_decay = {qubit: 1 for qubit in dag.qubits}
+        self.qubits_decay = dict.fromkeys(dag.qubits, 1)
 
         # Start algorithm from the front layer and iterate until all gates done.
         num_search_steps = 0
@@ -178,10 +194,12 @@ class SabreSwap(TransformationPass):
         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 = []
 
             # Remove as many immediately applicable gates as possible
+            new_front_layer = []
             for node in front_layer:
                 if len(node.qargs) == 2:
                     v0, v1 = node.qargs
@@ -191,13 +209,24 @@ class SabreSwap(TransformationPass):
                         current_layout._v2p[v0], current_layout._v2p[v1]
                     ):
                         execute_gate_list.append(node)
+                    else:
+                        new_front_layer.append(node)
                 else:  # Single-qubit gates as well as barriers are free
                     execute_gate_list.append(node)
+            front_layer = new_front_layer
+
+            if not execute_gate_list and len(ops_since_progress) > max_iterations_without_progress:
+                # Backtrack to the last time we made progress, then greedily insert swaps to route
+                # the gate with the smallest distance between its arguments.  This is a release
+                # valve for the algorithm to avoid infinite loops only, and should generally not
+                # come into play for most circuits.
+                self._undo_operations(ops_since_progress, mapped_dag, current_layout)
+                self._add_greedy_swaps(front_layer, mapped_dag, current_layout, canonical_register)
+                continue
 
             if execute_gate_list:
                 for node in execute_gate_list:
                     self._apply_gate(mapped_dag, node, current_layout, canonical_register)
-                    front_layer.remove(node)
                     for successor in self._successors(node, dag):
                         self.applied_predecessors[successor] += 1
                         if self._is_resolved(successor):
@@ -207,27 +236,33 @@ class SabreSwap(TransformationPass):
                         self._reset_qubits_decay()
 
                 # Diagnostics
-                logger.debug(
-                    "free! %s",
-                    [
-                        (n.name if isinstance(n, DAGOpNode) else None, n.qargs)
-                        for n in execute_gate_list
-                    ],
-                )
-                logger.debug(
-                    "front_layer: %s",
-                    [(n.name if isinstance(n, DAGOpNode) else None, n.qargs) for n in front_layer],
-                )
-
+                if do_expensive_logging:
+                    logger.debug(
+                        "free! %s",
+                        [
+                            (n.name if isinstance(n, DAGOpNode) else None, n.qargs)
+                            for n in execute_gate_list
+                        ],
+                    )
+                    logger.debug(
+                        "front_layer: %s",
+                        [
+                            (n.name if isinstance(n, DAGOpNode) else None, n.qargs)
+                            for n in front_layer
+                        ],
+                    )
+
+                ops_since_progress = []
+                extended_set = None
                 continue
 
             # After all free gates are exhausted, heuristically find
             # the best swap and insert it. When two or more swaps tie
             # for best score, pick one randomly.
-            extended_set = self._obtain_extended_set(dag, front_layer)
-            swap_candidates = self._obtain_swaps(front_layer, current_layout)
-            swap_scores = dict.fromkeys(swap_candidates, 0)
-            for swap_qubits in swap_scores:
+            if extended_set is None:
+                extended_set = self._obtain_extended_set(dag, front_layer)
+            swap_scores = {}
+            for swap_qubits in self._obtain_swaps(front_layer, current_layout):
                 trial_layout = current_layout.copy()
                 trial_layout.swap(*swap_qubits)
                 score = self._score_heuristic(
@@ -238,9 +273,14 @@ class SabreSwap(TransformationPass):
             best_swaps = [k for k, v in swap_scores.items() if v == min_score]
             best_swaps.sort(key=lambda x: (self._bit_indices[x[0]], self._bit_indices[x[1]]))
             best_swap = rng.choice(best_swaps)
-            swap_node = DAGOpNode(op=SwapGate(), qargs=best_swap)
-            self._apply_gate(mapped_dag, swap_node, current_layout, canonical_register)
+            swap_node = self._apply_gate(
+                mapped_dag,
+                DAGOpNode(op=SwapGate(), qargs=best_swap),
+                current_layout,
+                canonical_register,
+            )
             current_layout.swap(*best_swap)
+            ops_since_progress.append(swap_node)
 
             num_search_steps += 1
             if num_search_steps % DECAY_RESET_INTERVAL == 0:
@@ -250,23 +290,23 @@ class SabreSwap(TransformationPass):
                 self.qubits_decay[best_swap[1]] += DECAY_RATE
 
             # Diagnostics
-            logger.debug("SWAP Selection...")
-            logger.debug("extended_set: %s", [(n.name, n.qargs) for n in extended_set])
-            logger.debug("swap scores: %s", swap_scores)
-            logger.debug("best swap: %s", best_swap)
-            logger.debug("qubits decay: %s", self.qubits_decay)
+            if do_expensive_logging:
+                logger.debug("SWAP Selection...")
+                logger.debug("extended_set: %s", [(n.name, n.qargs) for n in extended_set])
+                logger.debug("swap scores: %s", swap_scores)
+                logger.debug("best swap: %s", best_swap)
+                logger.debug("qubits decay: %s", self.qubits_decay)
 
         self.property_set["final_layout"] = current_layout
-
         if not self.fake_run:
             return mapped_dag
         return dag
 
     def _apply_gate(self, mapped_dag, node, current_layout, canonical_register):
-        if self.fake_run:
-            return
         new_node = _transform_gate_for_layout(node, current_layout, canonical_register)
-        mapped_dag.apply_operation_back(new_node.op, new_node.qargs, new_node.cargs)
+        if self.fake_run:
+            return new_node
+        return mapped_dag.apply_operation_back(new_node.op, new_node.qargs, new_node.cargs)
 
     def _reset_qubits_decay(self):
         """Reset all qubit decay factors to 1 upon request (to forget about
@@ -332,9 +372,20 @@ class SabreSwap(TransformationPass):
                     virtual_neighbor = current_layout[neighbor]
                     swap = sorted([virtual, virtual_neighbor], key=lambda q: self._bit_indices[q])
                     candidate_swaps.add(tuple(swap))
-
         return candidate_swaps
 
+    def _add_greedy_swaps(self, front_layer, dag, layout, qubits):
+        """Mutate ``dag`` and ``layout`` by applying greedy swaps to ensure that at least one gate
+        can be routed."""
+        layout_map = layout._v2p
+        target_node = min(
+            front_layer,
+            key=lambda node: self.dist_matrix[layout_map[node.qargs[0]], layout_map[node.qargs[1]]],
+        )
+        for pair in _shortest_swap_path(tuple(target_node.qargs), self.coupling_map, layout):
+            self._apply_gate(dag, DAGOpNode(op=SwapGate(), qargs=pair), layout, qubits)
+            layout.swap(*pair)
+
     def _compute_cost(self, layer, layout):
         cost = 0
         layout_map = layout._v2p
@@ -369,13 +420,38 @@ class SabreSwap(TransformationPass):
 
         raise TranspilerError("Heuristic %s not recognized." % heuristic)
 
+    def _undo_operations(self, operations, dag, layout):
+        """Mutate ``dag`` and ``layout`` by undoing the swap gates listed in ``operations``."""
+        if dag is None:
+            for operation in reversed(operations):
+                layout.swap(*operation.qargs)
+        else:
+            for operation in reversed(operations):
+                dag.remove_op_node(operation)
+                p0 = self._bit_indices[operation.qargs[0]]
+                p1 = self._bit_indices[operation.qargs[1]]
+                layout.swap(p0, p1)
+
 
 def _transform_gate_for_layout(op_node, layout, device_qreg):
     """Return node implementing a virtual op on given layout."""
     mapped_op_node = copy(op_node)
+    mapped_op_node.qargs = [device_qreg[layout._v2p[x]] for x in op_node.qargs]
+    return mapped_op_node
 
-    premap_qargs = op_node.qargs
-    mapped_qargs = map(lambda x: device_qreg[layout._v2p[x]], premap_qargs)
-    mapped_op_node.qargs = list(mapped_qargs)
 
-    return mapped_op_node
+def _shortest_swap_path(target_qubits, coupling_map, layout):
+    """Return an iterator that yields the swaps between virtual qubits needed to bring the two
+    virtual qubits in ``target_qubits`` together in the coupling map."""
+    v_start, v_goal = target_qubits
+    start, goal = layout._v2p[v_start], layout._v2p[v_goal]
+    # TODO: remove the list call once using retworkx 0.12, as the return value can be sliced.
+    path = list(retworkx.dijkstra_shortest_paths(coupling_map.graph, start, target=goal)[goal])
+    # Swap both qubits towards the "centre" (as opposed to applying the same swaps to one) to
+    # parallelise and reduce depth.
+    split = len(path) // 2
+    forwards, backwards = path[1:split], reversed(path[split:-1])
+    for swap in forwards:
+        yield v_start, layout._p2v[swap]
+    for swap in backwards:
+        yield v_goal, layout._p2v[swap]
diff --git a/releasenotes/notes/sabreswap-loop-230ef99e61358105.yaml b/releasenotes/notes/sabreswap-loop-230ef99e61358105.yaml
new file mode 100644
index 000000000..f004d411b
--- /dev/null
+++ b/releasenotes/notes/sabreswap-loop-230ef99e61358105.yaml
@@ -0,0 +1,11 @@
+---
+fixes:
+  - |
+    The :class:`.SabreSwap` transpiler pass, and by extension
+    :class:`.SabreLayout` and :func:`.transpile` at ``optimization_level=3``,
+    now has an escape mechanism to guarantee that it can never get stuck in an
+    infinite loop.  Certain inputs previously could, with a great amount of bad
+    luck, get stuck in a stable local minimum of the search space and the pass
+    would never make further progress.  It will now force a series of swaps that
+    allow the routing to continue if it detects it has not made progress
+    recently.  Fixed `#7707 <https://github.com/Qiskit/qiskit-terra/issues/7707>`__.


Test patch:
diff --git a/test/python/transpiler/test_sabre_swap.py b/test/python/transpiler/test_sabre_swap.py
index 509225f65..f7a9e96cf 100644
--- a/test/python/transpiler/test_sabre_swap.py
+++ b/test/python/transpiler/test_sabre_swap.py
@@ -13,13 +13,79 @@
 """Test the Sabre Swap pass"""
 
 import unittest
-from qiskit.circuit.library import CCXGate, HGate, Measure
+
+import ddt
+
+from qiskit.circuit.library import CCXGate, HGate, Measure, SwapGate
 from qiskit.transpiler.passes import SabreSwap
 from qiskit.transpiler import CouplingMap, PassManager
 from qiskit import QuantumRegister, QuantumCircuit
 from qiskit.test import QiskitTestCase
-
-
+from qiskit.utils import optionals
+
+
+def looping_circuit(uphill_swaps=1, additional_local_minimum_gates=0):
+    """A circuit that causes SabreSwap to loop infinitely.
+
+    This looks like (using cz gates to show the symmetry, though we actually output cx for testing
+    purposes):
+
+    .. parsed-literal::
+
+         q_0: ─■────────────────
+               │
+         q_1: ─┼──■─────────────
+               │  │
+         q_2: ─┼──┼──■──────────
+               │  │  │
+         q_3: ─┼──┼──┼──■───────
+               │  │  │  │
+         q_4: ─┼──┼──┼──┼─────■─
+               │  │  │  │     │
+         q_5: ─┼──┼──┼──┼──■──■─
+               │  │  │  │  │
+         q_6: ─┼──┼──┼──┼──┼────
+               │  │  │  │  │
+         q_7: ─┼──┼──┼──┼──■──■─
+               │  │  │  │     │
+         q_8: ─┼──┼──┼──┼─────■─
+               │  │  │  │
+         q_9: ─┼──┼──┼──■───────
+               │  │  │
+        q_10: ─┼──┼──■──────────
+               │  │
+        q_11: ─┼──■─────────────
+               │
+        q_12: ─■────────────────
+
+    where `uphill_swaps` is the number of qubits separating the inner-most gate (representing how
+    many swaps need to be made that all increase the heuristics), and
+    `additional_local_minimum_gates` is how many extra gates to add on the outside (these increase
+    the size of the region of stability).
+    """
+    outers = 4 + additional_local_minimum_gates
+    n_qubits = 2 * outers + 4 + uphill_swaps
+    # This is (most of) the front layer, which is a bunch of outer qubits in the
+    # coupling map.
+    outer_pairs = [(i, n_qubits - i - 1) for i in range(outers)]
+    inner_heuristic_peak = [
+        # This gate is completely "inside" all the others in the front layer in
+        # terms of the coupling map, so it's the only one that we can in theory
+        # make progress towards without making the others worse.
+        (outers + 1, outers + 2 + uphill_swaps),
+        # These are the only two gates in the extended set, and they both get
+        # further apart if you make a swap to bring the above gate closer
+        # together, which is the trick that creates the "heuristic hill".
+        (outers, outers + 1),
+        (outers + 2 + uphill_swaps, outers + 3 + uphill_swaps),
+    ]
+    qc = QuantumCircuit(n_qubits)
+    for pair in outer_pairs + inner_heuristic_peak:
+        qc.cx(*pair)
+    return qc
+
+
+@ddt.ddt
 class TestSabreSwap(QiskitTestCase):
     """Tests the SabreSwap pass."""
 
@@ -124,6 +190,53 @@ class TestSabreSwap(QiskitTestCase):
         self.assertEqual(h_qubits, first_measure_qubits)
         self.assertNotEqual(h_qubits, second_measure_qubits)
 
+    # The 'basic' method can't get stuck in the same way.
+    @ddt.data("lookahead", "decay")
+    def test_no_infinite_loop(self, method):
+        """Test that the 'release value' mechanisms allow SabreSwap to make progress even on
+        circuits that get stuck in a stable local minimum of the lookahead parameters."""
+        qc = looping_circuit(3, 1)
+        qc.measure_all()
+        coupling_map = CouplingMap.from_line(qc.num_qubits)
+        routing_pass = PassManager(SabreSwap(coupling_map, method))
+
+        n_swap_gates = 0
+
+        def leak_number_of_swaps(cls, *args, **kwargs):
+            nonlocal n_swap_gates
+            n_swap_gates += 1
+            if n_swap_gates > 1_000:
+                raise Exception("SabreSwap seems to be stuck in a loop")
+            # pylint: disable=bad-super-call
+            return super(SwapGate, cls).__new__(cls, *args, **kwargs)
+
+        with unittest.mock.patch.object(SwapGate, "__new__", leak_number_of_swaps):
+            routed = routing_pass.run(qc)
+
+        routed_ops = routed.count_ops()
+        del routed_ops["swap"]
+        self.assertEqual(routed_ops, qc.count_ops())
+        couplings = {
+            tuple(routed.find_bit(bit).index for bit in qargs)
+            for _, qargs, _ in routed.data
+            if len(qargs) == 2
+        }
+        # Asserting equality to the empty set gives better errors on failure than asserting that
+        # `couplings <= coupling_map`.
+        self.assertEqual(couplings - set(coupling_map.get_edges()), set())
+
+        # Assert that the same keys are produced by a simulation - this is a test that the inserted
+        # swaps route the qubits correctly.
+        if not optionals.HAS_AER:
+            return
+
+        from qiskit import Aer
+
+        sim = Aer.get_backend("aer_simulator")
+        in_results = sim.run(qc, shots=4096).result().get_counts()
+        out_results = sim.run(routed, shots=4096).result().get_counts()
+        self.assertEqual(set(in_results), set(out_results))
+
 
 if __name__ == "__main__":
     unittest.main()