Skip to content

Support control flow in Python components of SabreLayout #9421

@jakelishman

Description

@jakelishman

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:

  1. choose a random initial layout
  2. keep copies of the circuit, and the circuit with its operations reversed
  3. run the routing pass to reach a final layout
  4. 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.
  5. repeat steps 3 and 4 several times, then use the resultant initial layout as the solution.

Our implementation of SabreLayout has two paths:

  1. a pure-Python implementation that gets a routing pass injected during SabreLayout instance construction, then manually manages calling it with an internal PassManager. This can handle any routing pass.
  2. 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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions