-
Notifications
You must be signed in to change notification settings - Fork 2.6k
Description
What should we add?
Part of #9417. Related to #9419.
Details
As an overview, the SabreLayout
algorithm is a relatively small wrapper around some externally defined routing pass. Qiskit generally uses SabreSwap
as this driver by default. The layout-specific part of the algorithm is approximately:
- choose a random initial layout
- keep copies of the circuit, and the circuit with its operations reversed
- run the routing pass to reach a final layout
- run the routing pass on the reversed circuit, using the previous final layout as input. Take the "final" layout from this routing of the reversed circuit to be the new initial layout of the forwards circuit.
- repeat steps 3 and 4 several times, then use the resultant initial layout as the solution.
Our implementation of SabreLayout
has two paths:
- a pure-Python implementation that gets a routing pass injected during
SabreLayout
instance construction, then manually manages calling it with an internalPassManager
. This can handle any routing pass. - a preferred fast-path that immediately drops down to Rust space, and calls our Rust version of the Sabre routing algorithm repeatedly as the driver. This lets us run several tries of the layout pass in parallel, significantly improving the output quality and run time. This method acts as a joint layout+routing pass, since we can just reverse the final routed "reversed" circuit to get the output of the swap mapper without re-running it.
For initial support through SabreLayout
, it is acceptable to only upgrade path 1. Upgrading path 2 implies the more difficult, long-term direction of #9419 is taken, which can be done later once we understand more about how to route dynamic circuits.
Technically, SabreLayout
should already execute on a dynamic circuit if a StochasticSwap
instance is passed in to path 1 as the router. However, this is logically not entirely correct; the "reverse circuit" operation will not recurse into the control-flow operations to reverse them, so the algorithm will likely produce very inefficient layouts, because part of its algorithm is stymied.
For the control-flow and classical operations currently implemented by Qiskit and supported by the other transpiler passes, implementing the reverse operation largely should just be a case of reversing the operations inside each control-flow block. This is assuming that break
and continue
remain unsupported; these might have different properties. Bear in mind that the "reverse" of the circuit doesn't have any real meaning in terms of circuit behaviour, it's just a tool we use as part of the algorithm; anything that logically lets us run the routing pass over the operations in the circuit in reverse topological order is fine.