Repository: Qiskit/qiskit (python)

Issue:
GateDirection pass goes outside allowed basis gates
### Environment

- **Qiskit Terra version**: 0.25
- **Python version**: 3.9
- **Operating system**: MacOS


### What is happening?

Trying to run a clifford simulation on a fake backend with ECR basis gates leads to transpilation errors with unsupported basis gates

### How can we reproduce the issue?

```python
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
from qiskit.providers.fake_provider import FakeSherbrooke, FakeWashington

# Stabilizer simulator for FakeSherbrooke
clifford_basis_gates = ['ecr', 'sx', 'x', 'id', 'z', 's', 'sdg']
backend = AerSimulator.from_backend(
    FakeSherbrooke(),
    method="stabilizer",
    basis_gates=clifford_basis_gates, 
)

# Circuit
qc = QuantumCircuit(2)
qc.h(0)
qc.cx(0, 1)

# Transpile
transpile(qc, backend)
```
Raises
```
TranspilerError: "Unable to translate the operations in the circuit: ['ry', 'h', 'sdg', 'sx', 's', 'ecr', 'x'] to the backend's (or manually specified) target basis: ['break_loop', 'quantum_channel', 's', 'save_expval_var', 'for_loop', 'roerror', 'continue_loop', 'save_probabilities', 'z', 'qerror_loc', 'reset', 'save_clifford', 'snapshot', 'if_else', 'id', 'save_probabilities_dict', 'ecr', 'save_state', 'save_amplitudes_sq', 'sdg', 'save_stabilizer', 'delay', 'while_loop', 'save_expval', 'set_stabilizer', 'sx', 'measure', 'barrier', 'x']. This likely means the target basis is not universal or there are additional equivalence rules needed in the EquivalenceLibrary being used. For more details on this error see: https://qiskit.org/documentation/stubs/qiskit.transpiler.passes.BasisTranslator.html#translation_errors"
```

### What should happen?

Running with a manually specified basis gates works (though the output is not at all optimized in terms of number of 1Q gates):

```python
transpile(qc, basis_gates=["ecr", "x", "sx", "id", "z", "s", "sdg"])
```
```
global phase: 3π/2
     ┌───┐┌────┐┌───┐ ┌─────┐     ┌──────┐┌───┐
q_0: ┤ S ├┤ √X ├┤ S ├─┤ Sdg ├─────┤0     ├┤ X ├
     ├───┤├───┬┘├───┴┐└┬───┬┘┌───┐│  Ecr │└───┘
q_1: ┤ S ├┤ S ├─┤ √X ├─┤ S ├─┤ S ├┤1     ├─────
     └───┘└───┘ └────┘ └───┘ └───┘└──────┘     
```


### Any suggestions?

Running transpilation with a callback looks like the issues is due to the `GateDirection` pass which inserts non-Clifford gates outside the allowed basis gates into the circuit and causes the rest of the transpilation to fail. 

```python
def callback(**kwargs):
    print(f"{type(kwargs['pass_']).__name__} output gates: {kwargs['dag'].count_ops()}")

transpile(qc, backend, callback=callback).draw()
```

```
ContainsInstruction, gates: {'h': 1, 'cx': 1}
UnitarySynthesis, gates: {'h': 1, 'cx': 1}
HighLevelSynthesis, gates: {'h': 1, 'cx': 1}
Unroll3qOrMore, gates: {'h': 1, 'cx': 1}
SetLayout, gates: {'h': 1, 'cx': 1}
TrivialLayout, gates: {'h': 1, 'cx': 1}
CheckMap, gates: {'h': 1, 'cx': 1}
FullAncillaAllocation, gates: {'h': 1, 'cx': 1}
EnlargeWithAncilla, gates: {'h': 1, 'cx': 1}
ApplyLayout, gates: {'h': 1, 'cx': 1}
CheckMap, gates: {'h': 1, 'cx': 1}
UnitarySynthesis, gates: {'h': 1, 'cx': 1}
HighLevelSynthesis, gates: {'h': 1, 'cx': 1}
UnrollCustomDefinitions, gates: {'h': 1, 'cx': 1}
BasisTranslator, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'ecr': 1, 'x': 1}
CheckGateDirection, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'ecr': 1, 'x': 1}
GateDirection, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}   # NON BASIS RY INSERTED HERE
RemoveResetInZeroState, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
Depth, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
FixedPoint, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
Size, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
FixedPoint, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
Optimize1qGatesDecomposition, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
CXCancellation, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
GatesInBasis, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
UnitarySynthesis, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
HighLevelSynthesis, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
UnrollCustomDefinitions, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
# raises exception here
```


This pass should only insert gates supported by the backend, and be updated to work with Clifford basis backends to enable simulation testing

Pull request description:
Use only discrete-basis translations in `GateDirection`
### Summary

This makes it a little more likely that it'll be possible to use the transpiler when targetting a discrete basis, such as a Clifford simulator.  We still in general do not offer full support for discrete-basis translation, and certainly not for optimal discrete-basis transpilation, but this is a relatively easy change that makes us marginally more reliable with them.

<!--
⚠️ 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 #10785.

I'm vaguely concerned about a potential performance regression here by us making the basis translator and resynthesis routines do more work for real-world backends, but I couldn't immediately think what benchmarks, if any, we have to run about that.

*edit*: I'm not 100% convinced that this PR is something we should do, but it's a proof of principle.

Patch:
diff --git a/qiskit/transpiler/passes/__init__.py b/qiskit/transpiler/passes/__init__.py
index c298e9999..b07d2b3dc 100644
--- a/qiskit/transpiler/passes/__init__.py
+++ b/qiskit/transpiler/passes/__init__.py
@@ -34,6 +34,7 @@ Layout Selection (Placement)
    Layout2qDistance
    EnlargeWithAncilla
    FullAncillaAllocation
+   SabrePreLayout
 
 Routing
 =======
@@ -193,6 +194,7 @@ from .layout import ApplyLayout
 from .layout import Layout2qDistance
 from .layout import EnlargeWithAncilla
 from .layout import FullAncillaAllocation
+from .layout import SabrePreLayout
 
 # routing
 from .routing import BasicSwap
diff --git a/qiskit/transpiler/passes/layout/__init__.py b/qiskit/transpiler/passes/layout/__init__.py
index 736ea3add..9b0fdc079 100644
--- a/qiskit/transpiler/passes/layout/__init__.py
+++ b/qiskit/transpiler/passes/layout/__init__.py
@@ -24,3 +24,4 @@ from .apply_layout import ApplyLayout
 from .layout_2q_distance import Layout2qDistance
 from .enlarge_with_ancilla import EnlargeWithAncilla
 from .full_ancilla_allocation import FullAncillaAllocation
+from .sabre_pre_layout import SabrePreLayout
diff --git a/qiskit/transpiler/passes/layout/sabre_pre_layout.py b/qiskit/transpiler/passes/layout/sabre_pre_layout.py
new file mode 100644
index 000000000..55748fef4
--- /dev/null
+++ b/qiskit/transpiler/passes/layout/sabre_pre_layout.py
@@ -0,0 +1,217 @@
+# This code is part of Qiskit.
+#
+# (C) Copyright IBM 2023.
+#
+# This code is licensed under the Apache License, Version 2.0. You may
+# obtain a copy of this license in the LICENSE.txt file in the root directory
+# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
+#
+# Any modifications or derivative works of this code must retain this
+# copyright notice, and modified files need to carry a notice indicating
+# that they have been altered from the originals.
+
+"""Creating Sabre starting layouts."""
+
+import itertools
+
+from qiskit.transpiler import CouplingMap, Target, AnalysisPass, TranspilerError
+from qiskit.transpiler.passes.layout.vf2_layout import VF2Layout
+from qiskit._accelerate.error_map import ErrorMap
+
+
+class SabrePreLayout(AnalysisPass):
+    """Choose a starting layout to use for additional Sabre layout trials.
+
+    Property Set Values Written
+    ---------------------------
+
+    ``sabre_starting_layouts`` (``list[Layout]``)
+        An optional list of :class:`~.Layout` objects to use for additional Sabre layout trials.
+
+    """
+
+    def __init__(
+        self,
+        coupling_map,
+        max_distance=2,
+        error_rate=0.1,
+        max_trials_vf2=100,
+        call_limit_vf2=None,
+        improve_layout=True,
+    ):
+        """SabrePreLayout initializer.
+
+        The pass works by augmenting the coupling map with more and more "extra" edges
+        until VF2 succeeds to find a perfect graph isomorphism. More precisely, the
+        augmented coupling map contains edges between nodes that are within a given
+        distance ``d`` in the original coupling map, and the value of ``d`` is increased
+        until an isomorphism is found.
+
+        Intuitively, a better layout involves fewer extra edges. The pass also optionally
+        minimizes the number of extra edges involved in the layout until a local minimum
+        is found. This involves removing extra edges and running VF2 to see if an
+        isomorphism still exists.
+
+        Args:
+            coupling_map (Union[CouplingMap, Target]): directed graph representing the
+                original coupling map or a target modelling the backend (including its
+                connectivity).
+            max_distance (int): the maximum distance to consider for augmented coupling maps.
+            error_rate (float): the error rate to assign to the "extra" edges. A non-zero
+                error rate prioritizes VF2 to choose original edges over extra edges.
+            max_trials_vf2 (int): specifies the maximum number of VF2 trials. A larger number
+                allows VF2 to explore more layouts, eventually choosing the one with the smallest
+                error rate.
+            call_limit_vf2 (int): limits each call to VF2 by bounding the number of VF2 state visits.
+            improve_layout (bool): whether to improve the layout by minimizing the number of
+                extra edges involved. This might be time-consuming as this requires additional
+                VF2 calls.
+
+        Raises:
+            TranspilerError: At runtime, if neither ``coupling_map`` or ``target`` are provided.
+        """
+
+        self.max_distance = max_distance
+        self.error_rate = error_rate
+        self.max_trials_vf2 = max_trials_vf2
+        self.call_limit_vf2 = call_limit_vf2
+        self.improve_layout = improve_layout
+
+        if isinstance(coupling_map, Target):
+            self.target = coupling_map
+            self.coupling_map = self.target.build_coupling_map()
+        else:
+            self.target = None
+            self.coupling_map = coupling_map
+
+        super().__init__()
+
+    def run(self, dag):
+        """Run the SabrePreLayout pass on `dag`.
+
+        The discovered starting layout is written to the property set
+        value ``sabre_starting_layouts``.
+
+        Args:
+            dag (DAGCircuit): DAG to create starting layout for.
+        """
+
+        if self.coupling_map is None:
+            raise TranspilerError(
+                "SabrePreLayout requires coupling_map to be used with either"
+                "CouplingMap or a Target."
+            )
+
+        starting_layout = None
+        cur_distance = 1
+        while cur_distance <= self.max_distance:
+            augmented_map, augmented_error_map = self._add_extra_edges(cur_distance)
+            pass_ = VF2Layout(
+                augmented_map,
+                seed=0,
+                max_trials=self.max_trials_vf2,
+                call_limit=self.call_limit_vf2,
+            )
+            pass_.property_set["vf2_avg_error_map"] = augmented_error_map
+            pass_.run(dag)
+
+            if "layout" in pass_.property_set:
+                starting_layout = pass_.property_set["layout"]
+                break
+
+            cur_distance += 1
+
+        if cur_distance > 1 and starting_layout is not None:
+            # optionally improve starting layout
+            if self.improve_layout:
+                starting_layout = self._minimize_extra_edges(dag, starting_layout)
+            # write discovered layout into the property set
+            if "sabre_starting_layouts" not in self.property_set:
+                self.property_set["sabre_starting_layouts"] = [starting_layout]
+            else:
+                self.property_set["sabre_starting_layouts"].append(starting_layout)
+
+    def _add_extra_edges(self, distance):
+        """Augments the coupling map with extra edges that connect nodes ``distance``
+        apart in the original graph. The extra edges are assigned errors allowing VF2
+        to prioritize real edges over extra edges.
+        """
+        nq = len(self.coupling_map.graph)
+        augmented_coupling_map = CouplingMap()
+        augmented_coupling_map.graph = self.coupling_map.graph.copy()
+        augmented_error_map = ErrorMap(nq)
+
+        for (x, y) in itertools.combinations(self.coupling_map.graph.node_indices(), 2):
+            d = self.coupling_map.distance(x, y)
+            if 1 < d <= distance:
+                error_rate = 1 - ((1 - self.error_rate) ** d)
+                augmented_coupling_map.add_edge(x, y)
+                augmented_error_map.add_error((x, y), error_rate)
+                augmented_coupling_map.add_edge(y, x)
+                augmented_error_map.add_error((y, x), error_rate)
+
+        return augmented_coupling_map, augmented_error_map
+
+    def _get_extra_edges_used(self, dag, layout):
+        """Returns the set of extra edges involved in the layout."""
+        extra_edges_used = set()
+        virtual_bits = layout.get_virtual_bits()
+        for node in dag.two_qubit_ops():
+            p0 = virtual_bits[node.qargs[0]]
+            p1 = virtual_bits[node.qargs[1]]
+            if self.coupling_map.distance(p0, p1) > 1:
+                extra_edge = (p0, p1) if p0 < p1 else (p1, p0)
+                extra_edges_used.add(extra_edge)
+        return extra_edges_used
+
+    def _find_layout(self, dag, edges):
+        """Checks if there is a layout for a given set of edges."""
+        cm = CouplingMap(edges)
+        pass_ = VF2Layout(cm, seed=0, max_trials=1, call_limit=self.call_limit_vf2)
+        pass_.run(dag)
+        return pass_.property_set.get("layout", None)
+
+    def _minimize_extra_edges(self, dag, starting_layout):
+        """Minimizes the set of extra edges involved in the layout. This iteratively
+        removes extra edges from the coupling map and uses VF2 to check if a layout
+        still exists. This is reasonably efficiently as it only looks for a local
+        minimum.
+        """
+        # compute the set of edges in the original coupling map
+        real_edges = []
+        for (x, y) in itertools.combinations(self.coupling_map.graph.node_indices(), 2):
+            d = self.coupling_map.distance(x, y)
+            if d == 1:
+                real_edges.append((x, y))
+
+        best_layout = starting_layout
+
+        # keeps the set of "necessary" extra edges: without a necessary edge
+        # a layout no longer exists
+        extra_edges_necessary = []
+
+        extra_edges_unprocessed_set = self._get_extra_edges_used(dag, starting_layout)
+
+        while extra_edges_unprocessed_set:
+            # choose some unprocessed edge
+            edge_chosen = next(iter(extra_edges_unprocessed_set))
+            extra_edges_unprocessed_set.remove(edge_chosen)
+
+            # check if a layout still exists without this edge
+            layout = self._find_layout(
+                dag, real_edges + extra_edges_necessary + list(extra_edges_unprocessed_set)
+            )
+
+            if layout is None:
+                # without this edge the layout either does not exist or is too hard to find
+                extra_edges_necessary.append(edge_chosen)
+
+            else:
+                # this edge is not necessary, furthermore we can trim the set of edges to examine based
+                # in the edges involved in the layout.
+                extra_edges_unprocessed_set = self._get_extra_edges_used(dag, layout).difference(
+                    set(extra_edges_necessary)
+                )
+                best_layout = layout
+
+        return best_layout
diff --git a/qiskit/transpiler/passes/scheduling/dynamical_decoupling.py b/qiskit/transpiler/passes/scheduling/dynamical_decoupling.py
index bc606a0f7..87bbdbff9 100644
--- a/qiskit/transpiler/passes/scheduling/dynamical_decoupling.py
+++ b/qiskit/transpiler/passes/scheduling/dynamical_decoupling.py
@@ -53,6 +53,20 @@ class DynamicalDecoupling(TransformationPass):
         from qiskit.transpiler import PassManager, InstructionDurations
         from qiskit.transpiler.passes import ALAPSchedule, DynamicalDecoupling
         from qiskit.visualization import timeline_drawer
+
+        # Because the legacy passes do not propagate the scheduling information correctly, it is
+        # necessary to run a no-op "re-schedule" before the output circuits can be drawn.
+        def draw(circuit):
+            from qiskit import transpile
+
+            scheduled = transpile(
+                circuit,
+                optimization_level=0,
+                instruction_durations=InstructionDurations(),
+                scheduling_method="alap",
+            )
+            return timeline_drawer(scheduled)
+
         circ = QuantumCircuit(4)
         circ.h(0)
         circ.cx(0, 1)
@@ -69,7 +83,7 @@ class DynamicalDecoupling(TransformationPass):
         pm = PassManager([ALAPSchedule(durations),
                           DynamicalDecoupling(durations, dd_sequence)])
         circ_dd = pm.run(circ)
-        timeline_drawer(circ_dd)
+        draw(circ_dd)
 
         # Uhrig sequence on qubit 0
         n = 8
@@ -87,7 +101,7 @@ class DynamicalDecoupling(TransformationPass):
             ]
         )
         circ_dd = pm.run(circ)
-        timeline_drawer(circ_dd)
+        draw(circ_dd)
     """
 
     @deprecate_func(
diff --git a/qiskit/transpiler/passes/utils/gate_direction.py b/qiskit/transpiler/passes/utils/gate_direction.py
index a259106d3..98b471f6f 100644
--- a/qiskit/transpiler/passes/utils/gate_direction.py
+++ b/qiskit/transpiler/passes/utils/gate_direction.py
@@ -21,7 +21,9 @@ from qiskit.converters import dag_to_circuit, circuit_to_dag
 from qiskit.circuit import QuantumRegister, ControlFlowOp
 from qiskit.dagcircuit import DAGCircuit, DAGOpNode
 from qiskit.circuit.library.standard_gates import (
-    RYGate,
+    SGate,
+    SdgGate,
+    SXGate,
     HGate,
     CXGate,
     CZGate,
@@ -49,11 +51,14 @@ class GateDirection(TransformationPass):
         q_1: ┤ X ├      q_1: ┤ H ├──■──┤ H ├
              └───┘           └───┘     └───┘
 
-             ┌──────┐          ┌───────────┐┌──────┐┌───┐
-        q_0: ┤0     ├     q_0: ┤ RY(-pi/2) ├┤1     ├┤ H ├
-             │  ECR │  =       └┬──────────┤│  ECR │├───┤
-        q_1: ┤1     ├     q_1: ─┤ RY(pi/2) ├┤0     ├┤ H ├
-             └──────┘           └──────────┘└──────┘└───┘
+
+                          global phase: 3π/2
+             ┌──────┐           ┌───┐ ┌────┐┌─────┐┌──────┐┌───┐
+        q_0: ┤0     ├     q_0: ─┤ S ├─┤ √X ├┤ Sdg ├┤1     ├┤ H ├
+             │  ECR │  =       ┌┴───┴┐├────┤└┬───┬┘│  Ecr │├───┤
+        q_1: ┤1     ├     q_1: ┤ Sdg ├┤ √X ├─┤ S ├─┤0     ├┤ H ├
+             └──────┘          └─────┘└────┘ └───┘ └──────┘└───┘
+
 
              ┌──────┐          ┌───┐┌──────┐┌───┐
         q_0: ┤0     ├     q_0: ┤ H ├┤1     ├┤ H ├
@@ -90,11 +95,19 @@ class GateDirection(TransformationPass):
         self._cx_dag.apply_operation_back(HGate(), [qr[0]], [])
         self._cx_dag.apply_operation_back(HGate(), [qr[1]], [])
 
+        # This is done in terms of less-efficient S/SX/Sdg gates instead of the more natural
+        # `RY(pi /2)` so we have a chance for basis translation to keep things in a discrete basis
+        # during resynthesis, if that's what's being asked for.
         self._ecr_dag = DAGCircuit()
         qr = QuantumRegister(2)
+        self._ecr_dag.global_phase = -pi / 2
         self._ecr_dag.add_qreg(qr)
-        self._ecr_dag.apply_operation_back(RYGate(-pi / 2), [qr[0]], [])
-        self._ecr_dag.apply_operation_back(RYGate(pi / 2), [qr[1]], [])
+        self._ecr_dag.apply_operation_back(SGate(), [qr[0]], [])
+        self._ecr_dag.apply_operation_back(SXGate(), [qr[0]], [])
+        self._ecr_dag.apply_operation_back(SdgGate(), [qr[0]], [])
+        self._ecr_dag.apply_operation_back(SdgGate(), [qr[1]], [])
+        self._ecr_dag.apply_operation_back(SXGate(), [qr[1]], [])
+        self._ecr_dag.apply_operation_back(SGate(), [qr[1]], [])
         self._ecr_dag.apply_operation_back(ECRGate(), [qr[1], qr[0]], [])
         self._ecr_dag.apply_operation_back(HGate(), [qr[0]], [])
         self._ecr_dag.apply_operation_back(HGate(), [qr[1]], [])
diff --git a/qiskit/visualization/timeline/core.py b/qiskit/visualization/timeline/core.py
index 35841fe16..d98527937 100644
--- a/qiskit/visualization/timeline/core.py
+++ b/qiskit/visualization/timeline/core.py
@@ -159,6 +159,7 @@ class DrawerCanvas:
                 "This circuit should be transpiled with scheduler though it consists of "
                 "instructions with explicit durations.",
                 DeprecationWarning,
+                stacklevel=3,
             )
 
             try:
diff --git a/releasenotes/notes/add-sabre-starting-layout-7e151b7abb8a6c13.yaml b/releasenotes/notes/add-sabre-starting-layout-7e151b7abb8a6c13.yaml
new file mode 100644
index 000000000..98c2467bb
--- /dev/null
+++ b/releasenotes/notes/add-sabre-starting-layout-7e151b7abb8a6c13.yaml
@@ -0,0 +1,37 @@
+---
+features:
+  - |
+    Added a new analysis :class:`.SabrePreLayout` pass that creates a starting
+    layout for :class:`.SabreLayout`, writing the layout into the property set
+    value ``sabre_starting_layouts``.
+
+    The pass works by augmenting the coupling map with more and more "extra" edges
+    until :class:`.VF2Layout` succeeds to find a perfect graph isomorphism.
+    More precisely, the augmented coupling map contains edges between nodes that are
+    within a given distance ``d`` in the original coupling map, and the value of ``d``
+    is increased until an isomorphism is found. The pass also optionally minimizes
+    the number of extra edges involved in the layout until a local minimum is found.
+    This involves removing extra edges and calling :class:`.VF2Layout` to check if
+    an isomorphism still exists.
+
+    Here is an example of calling the :class:`.SabrePreLayout` before :class:`.SabreLayout`::
+
+        import math
+        from qiskit.transpiler import CouplingMap, PassManager
+        from qiskit.circuit.library import EfficientSU2
+        from qiskit.transpiler.passes import SabrePreLayout, SabreLayout
+
+        qc = EfficientSU2(16, entanglement='circular', reps=6, flatten=True)
+        qc.assign_parameters([math.pi / 2] * len(qc.parameters), inplace=True)
+        qc.measure_all()
+
+        coupling_map = CouplingMap.from_heavy_hex(7)
+
+        pm = PassManager(
+            [
+                SabrePreLayout(coupling_map=coupling_map),
+                SabreLayout(coupling_map),
+            ]
+        )
+
+        pm.run(qc)
diff --git a/releasenotes/notes/discrete-basis-gatedirection-bdffad3b47c1c532.yaml b/releasenotes/notes/discrete-basis-gatedirection-bdffad3b47c1c532.yaml
new file mode 100644
index 000000000..c3d4bbe63
--- /dev/null
+++ b/releasenotes/notes/discrete-basis-gatedirection-bdffad3b47c1c532.yaml
@@ -0,0 +1,8 @@
+---
+fixes:
+  - |
+    The :class:`.GateDirection` transpiler pass will now use discrete-basis translations rather than
+    relying on a continuous :class:`.RYGate`, which should help make some discrete-basis-set targets
+    slightly more reliable.  In general, :func:`.transpile` only has partial support for basis sets
+    that do not contain a continuously-parametrised operation, and so it may not always succeed in
+    these situations, and will almost certainly not produce optimal results.
diff --git a/releasenotes/notes/fix-timeline-draw-unscheduled-warning-873f7a24c6b51e2c.yaml b/releasenotes/notes/fix-timeline-draw-unscheduled-warning-873f7a24c6b51e2c.yaml
new file mode 100644
index 000000000..e93e62c96
--- /dev/null
+++ b/releasenotes/notes/fix-timeline-draw-unscheduled-warning-873f7a24c6b51e2c.yaml
@@ -0,0 +1,22 @@
+---
+deprecations:
+  - |
+    Passing a circuit to :func:`qiskit.visualization.timeline_drawer` that does not have scheduled
+    node start-time information is deprecated.  Only circuits that have gone through one of the
+    scheduling analysis passes (for example :class:`.ALAPScheduleAnalysis` or
+    :class:`.ASAPScheduleAnalysis`) can be visualised.  If you have used one of the old-style
+    scheduling passes (for example :class:`.ALAPSchedule` or :class:`.ASAPSchedule`), you can
+    propagate the scheduling information by running::
+
+      from qiskit import transpile
+      from qiskit.transpiler import InstructionDurations
+
+      scheduled = transpile(
+        my_old_style_circuit,
+        optimization_level=0,
+        scheduling_method="alap",
+        instruction_durations=InstructionDurations(),
+      )
+
+    This behaviour was previously intended to be deprecated in Qiskit 0.37, but due to a bug in the
+    warning, it was not displayed to users until now.  The behaviour will be removed in Qiskit 1.0.


Test patch:
diff --git a/test/python/compiler/test_transpiler.py b/test/python/compiler/test_transpiler.py
index f41f0a3dd..9a54bdc7d 100644
--- a/test/python/compiler/test_transpiler.py
+++ b/test/python/compiler/test_transpiler.py
@@ -51,16 +51,20 @@ from qiskit.circuit.delay import Delay
 from qiskit.circuit.library import (
     CXGate,
     CZGate,
+    ECRGate,
     HGate,
     RXGate,
     RYGate,
     RZGate,
+    SGate,
     SXGate,
+    SXdgGate,
+    SdgGate,
     U1Gate,
     U2Gate,
     UGate,
     XGate,
-    SGate,
+    ZGate,
 )
 from qiskit.circuit.measure import Measure
 from qiskit.compiler import transpile
@@ -417,6 +421,28 @@ class TestTranspile(QiskitTestCase):
         circuits = transpile(qc, backend)
         self.assertIsInstance(circuits, QuantumCircuit)
 
+    def test_transpile_bell_discrete_basis(self):
+        """Test that it's possible to transpile a very simple circuit to a discrete stabiliser-like
+        basis.  In general, we do not make any guarantees about the possibility or quality of
+        transpilation in these situations, but this is at least useful as a check that stuff that
+        _could_ be possible remains so."""
+
+        target = Target(num_qubits=2)
+        for one_q in [XGate(), SXGate(), SXdgGate(), SGate(), SdgGate(), ZGate()]:
+            target.add_instruction(one_q, {(0,): None, (1,): None})
+        # This is only in one direction, and not the direction we're going to attempt to lay it out
+        # onto, so we can test the basis translation.
+        target.add_instruction(ECRGate(), {(1, 0): None})
+
+        qc = QuantumCircuit(2)
+        qc.h(0)
+        qc.cx(0, 1)
+
+        # Try with the initial layout in both directions to ensure we're dealing with the basis
+        # having only a single direction.
+        self.assertIsInstance(transpile(qc, target=target, initial_layout=[0, 1]), QuantumCircuit)
+        self.assertIsInstance(transpile(qc, target=target, initial_layout=[1, 0]), QuantumCircuit)
+
     def test_transpile_one(self):
         """Test transpile a single circuit.
 
diff --git a/test/python/transpiler/test_gate_direction.py b/test/python/transpiler/test_gate_direction.py
index ef23ea53f..172c74e0c 100644
--- a/test/python/transpiler/test_gate_direction.py
+++ b/test/python/transpiler/test_gate_direction.py
@@ -172,12 +172,16 @@ class TestGateDirection(QiskitTestCase):
         #       ├─────────┴┐│  Ecr │├───┤
         # qr_1: ┤ Ry(-π/2) ├┤1     ├┤ H ├
         #       └──────────┘└──────┘└───┘
-        expected = QuantumCircuit(qr)
-        expected.ry(pi / 2, qr[0])
-        expected.ry(-pi / 2, qr[1])
-        expected.ecr(qr[0], qr[1])
-        expected.h(qr[0])
-        expected.h(qr[1])
+        expected = QuantumCircuit(qr, global_phase=-pi / 2)
+        expected.s(1)
+        expected.sx(1)
+        expected.sdg(1)
+        expected.sdg(0)
+        expected.sx(0)
+        expected.s(0)
+        expected.ecr(0, 1)
+        expected.h(0)
+        expected.h(1)
 
         pass_ = GateDirection(coupling)
         after = pass_.run(dag)
@@ -405,8 +409,13 @@ class TestGateDirection(QiskitTestCase):
             expected.h([0, 1])
             expected.cx(0, 1)
             with expected.if_test((circuit.clbits[0], True)) as else_:
-                expected.ry(pi / 2, 2)
-                expected.ry(-pi / 2, 3)
+                expected.global_phase -= pi / 2
+                expected.sdg(2)
+                expected.sx(2)
+                expected.s(2)
+                expected.s(3)
+                expected.sx(3)
+                expected.sdg(3)
                 expected.ecr(2, 3)
                 expected.h([2, 3])
             with else_:
@@ -442,8 +451,13 @@ class TestGateDirection(QiskitTestCase):
             expected.h([0, 1])
             expected.cx(0, 1)
             with expected.if_test((circuit.clbits[0], True)) as else_:
-                expected.ry(pi / 2, 2)
-                expected.ry(-pi / 2, 3)
+                expected.global_phase -= pi / 2
+                expected.sdg(2)
+                expected.sx(2)
+                expected.s(2)
+                expected.s(3)
+                expected.sx(3)
+                expected.sdg(3)
                 expected.ecr(2, 3)
                 expected.h([2, 3])
             with else_:
diff --git a/test/python/transpiler/test_sabre_layout.py b/test/python/transpiler/test_sabre_layout.py
index 0d0a185c5..abc48f63a 100644
--- a/test/python/transpiler/test_sabre_layout.py
+++ b/test/python/transpiler/test_sabre_layout.py
@@ -14,7 +14,10 @@
 
 import unittest
 
+import math
+
 from qiskit import QuantumRegister, QuantumCircuit
+from qiskit.circuit.library import EfficientSU2
 from qiskit.transpiler import CouplingMap, AnalysisPass, PassManager
 from qiskit.transpiler.passes import SabreLayout, DenseLayout
 from qiskit.transpiler.exceptions import TranspilerError
@@ -24,6 +27,8 @@ from qiskit.compiler.transpiler import transpile
 from qiskit.providers.fake_provider import FakeAlmaden, FakeAlmadenV2
 from qiskit.providers.fake_provider import FakeKolkata
 from qiskit.providers.fake_provider import FakeMontreal
+from qiskit.transpiler.passes.layout.sabre_pre_layout import SabrePreLayout
+from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
 
 
 class TestSabreLayout(QiskitTestCase):
@@ -389,5 +394,44 @@ class TestDisjointDeviceSabreLayout(QiskitTestCase):
         self.assertEqual([layout[q] for q in qc.qubits], [3, 1, 2, 5, 4, 6, 7, 8])
 
 
+class TestSabrePreLayout(QiskitTestCase):
+    """Tests the SabreLayout pass with starting layout created by SabrePreLayout."""
+
+    def setUp(self):
+        super().setUp()
+        circuit = EfficientSU2(16, entanglement="circular", reps=6, flatten=True)
+        circuit.assign_parameters([math.pi / 2] * len(circuit.parameters), inplace=True)
+        circuit.measure_all()
+        self.circuit = circuit
+        self.coupling_map = CouplingMap.from_heavy_hex(7)
+
+    def test_starting_layout(self):
+        """Test that a starting layout is created and looks as expected."""
+        pm = PassManager(
+            [
+                SabrePreLayout(coupling_map=self.coupling_map),
+                SabreLayout(self.coupling_map, seed=123456, swap_trials=1, layout_trials=1),
+            ]
+        )
+        pm.run(self.circuit)
+        layout = pm.property_set["layout"]
+        self.assertEqual(
+            [layout[q] for q in self.circuit.qubits],
+            [30, 98, 104, 36, 103, 35, 65, 28, 61, 91, 22, 92, 23, 93, 62, 99],
+        )
+
+    def test_integration_with_pass_manager(self):
+        """Tests SabrePreLayoutIntegration with the rest of PassManager pipeline."""
+        backend = FakeAlmadenV2()
+        pm = generate_preset_pass_manager(1, backend, seed_transpiler=0)
+        pm.pre_layout = PassManager([SabrePreLayout(backend.target)])
+        qct = pm.run(self.circuit)
+        qct_initial_layout = qct.layout.initial_layout
+        self.assertEqual(
+            [qct_initial_layout[q] for q in self.circuit.qubits],
+            [1, 6, 5, 10, 11, 12, 16, 17, 18, 13, 14, 9, 8, 3, 2, 0],
+        )
+
+
 if __name__ == "__main__":
     unittest.main()
diff --git a/test/python/transpiler/test_sabre_pre_layout.py b/test/python/transpiler/test_sabre_pre_layout.py
new file mode 100644
index 000000000..4041cb50b
--- /dev/null
+++ b/test/python/transpiler/test_sabre_pre_layout.py
@@ -0,0 +1,98 @@
+# This code is part of Qiskit.
+#
+# (C) Copyright IBM 2023.
+#
+# This code is licensed under the Apache License, Version 2.0. You may
+# obtain a copy of this license in the LICENSE.txt file in the root directory
+# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
+#
+# Any modifications or derivative works of this code must retain this
+# copyright notice, and modified files need to carry a notice indicating
+# that they have been altered from the originals.
+
+"""Test the SabrePreLayout pass"""
+
+from qiskit.circuit import QuantumCircuit
+from qiskit.transpiler import TranspilerError, CouplingMap, PassManager
+from qiskit.transpiler.passes.layout.sabre_pre_layout import SabrePreLayout
+from qiskit.converters import circuit_to_dag
+from qiskit.test import QiskitTestCase
+
+
+class TestSabrePreLayout(QiskitTestCase):
+    """Tests the SabrePreLayout pass."""
+
+    def test_no_constraints(self):
+        """Test we raise at runtime if no target or coupling graph are provided."""
+        qc = QuantumCircuit(2)
+        empty_pass = SabrePreLayout(coupling_map=None)
+        with self.assertRaises(TranspilerError):
+            empty_pass.run(circuit_to_dag(qc))
+
+    def test_starting_layout_created(self):
+        """Test the case that no perfect layout exists and SabrePreLayout can find a
+        starting layout."""
+        qc = QuantumCircuit(4)
+        qc.cx(0, 1)
+        qc.cx(1, 2)
+        qc.cx(2, 3)
+        qc.cx(3, 0)
+        coupling_map = CouplingMap.from_ring(5)
+        pm = PassManager([SabrePreLayout(coupling_map=coupling_map)])
+        pm.run(qc)
+
+        # SabrePreLayout should discover a single layout.
+        self.assertIn("sabre_starting_layouts", pm.property_set)
+        layouts = pm.property_set["sabre_starting_layouts"]
+        self.assertEqual(len(layouts), 1)
+        layout = layouts[0]
+        self.assertEqual([layout[q] for q in qc.qubits], [2, 1, 0, 4])
+
+    def test_perfect_layout_exists(self):
+        """Test the case that a perfect layout exists."""
+        qc = QuantumCircuit(4)
+        qc.cx(0, 1)
+        qc.cx(1, 2)
+        qc.cx(2, 3)
+        qc.cx(3, 0)
+        coupling_map = CouplingMap.from_ring(4)
+        pm = PassManager([SabrePreLayout(coupling_map=coupling_map)])
+        pm.run(qc)
+
+        # SabrePreLayout should not create starting layouts when a perfect layout exists.
+        self.assertNotIn("sabre_starting_layouts", pm.property_set)
+
+    def test_max_distance(self):
+        """Test the ``max_distance`` option to SabrePreLayout."""
+        qc = QuantumCircuit(6)
+        qc.cx(0, 1)
+        qc.cx(0, 2)
+        qc.cx(0, 3)
+        qc.cx(0, 4)
+        qc.cx(0, 5)
+        coupling_map = CouplingMap.from_ring(6)
+
+        # It is not possible to map a star-graph with 5 leaves into a ring with 6 nodes,
+        # so that all nodes are distance-2 apart.
+        pm = PassManager([SabrePreLayout(coupling_map=coupling_map, max_distance=2)])
+        pm.run(qc)
+        self.assertNotIn("sabre_starting_layouts", pm.property_set)
+
+        # But possible with distance-3.
+        pm = PassManager([SabrePreLayout(coupling_map=coupling_map, max_distance=3)])
+        pm.run(qc)
+        self.assertIn("sabre_starting_layouts", pm.property_set)
+
+    def test_call_limit_vf2(self):
+        """Test the ``call_limit_vf2`` option to SabrePreLayout."""
+        qc = QuantumCircuit(4)
+        qc.cx(0, 1)
+        qc.cx(1, 2)
+        qc.cx(2, 3)
+        qc.cx(3, 0)
+        coupling_map = CouplingMap.from_ring(5)
+        pm = PassManager(
+            [SabrePreLayout(coupling_map=coupling_map, call_limit_vf2=1, max_distance=3)]
+        )
+        pm.run(qc)
+        self.assertNotIn("sabre_starting_layouts", pm.property_set)