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

Improve efficiency of VF2 family of layout pass scoring with disjoint circuits #9834

Closed
Tracked by #9898
mtreinish opened this issue Mar 21, 2023 · 1 comment
Closed
Tracked by #9898
Assignees
Milestone

Comments

@mtreinish
Copy link
Member

What should we add?

Right now when there are multiple connected components in the circuit when we're running heuristic scoring for VF2Layout or VF2PostLayout we end up spending a great deal of time evaluating different potential layouts. This is because the number of combinations of layouts is quite high when there are multiple connected components in the circuit as there is a lot of freedom of placement and we evaluating each potential combination of valid placement for each connected component. This is a similar problem to #9026 (and fixed in #9148) but that was for the case of single qubit components in the circuit (this is causing poor performance in #9802).

To address this we should investigate expanding the approach taken in #9148 to larger connected components instead of just single qubit connected components. This would basically involve sorting each circuit connected component by number of operations and placing the connected components with the most operations first (maybe weighting towards more 2q ops than single qubit) and then iterate over each connected component and place them on the lowest error subgraphs in sequence. We likely will miss some potential layouts in this approach, but those lost possibilities shouldn't be significant.

For the implementation this might be a bit more involved, because rustworkx.vf2_mapping() doesn't support providing partial input mappings and I'm not sure the best mechanism to handle to go about doing this.

@mtreinish
Copy link
Member Author

I'm going to close this as fixed by #10054 since that is setting limits on the number of layouts evaluated which effectively time boxes the passes to prevent this issue from occurring. There is a follow up investigation and work we need to do to ensure that with our truncated search that we try and ensure we're still getting the highest quality output from the passes. @kevinhartman has been looking at a way to do this by presorting the input graphs to vf2_mapping in order of error rates. I'll open a follow up issue to track this work as part of 0.25.0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants