Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support control flow in Python components of SabreLayout #9421

Closed
Tracked by #9417 ...
jakelishman opened this issue Jan 23, 2023 · 0 comments · Fixed by #10366
Closed
Tracked by #9417 ...

Support control flow in Python components of SabreLayout #9421

jakelishman opened this issue Jan 23, 2023 · 0 comments · Fixed by #10366
Labels
mod: transpiler Issues and PRs related to Transpiler type: feature request New feature or request
Milestone

Comments

@jakelishman
Copy link
Member

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.

@jakelishman jakelishman added the type: feature request New feature or request label Jan 23, 2023
@jakelishman jakelishman added this to the 0.24.0 milestone Jan 23, 2023
@jakelishman jakelishman added the mod: transpiler Issues and PRs related to Transpiler label Jan 23, 2023
@jakelishman jakelishman changed the title Support control-flow in Python components of SabreLayout Support control flow in Python components of SabreLayout Jan 23, 2023
@jakelishman jakelishman modified the milestones: 0.24.0, 0.25.0 Apr 3, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
mod: transpiler Issues and PRs related to Transpiler type: feature request New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant