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

Update SwapUpdater to use computed shortest path length instead of Manhattan distance #149

Closed
weinstein opened this issue Feb 19, 2021 · 0 comments · Fixed by #151
Closed
Assignees
Labels

Comments

@weinstein
Copy link
Contributor

The current SwapUpdater implementation (#146) takes a short cut and uses manhattan distance when computing the shortest GridQubit-to-GridQubit distances.

But the manhattan distance is only the same as the shortest path length on the device connectivity graph when there are no unusable qubits (no holes, hanging strips, or disconnected qubits).

We should update the SwapUpdater to precompute shortest path lengths on the device connectivity graph (ex using the Floyd-Warshall algorithm, which we're already using for the initial circuit placement) and use those distances instead of manhattan distance. Otherwise, circuit placement will break in the presence of pruned qubits (see also quantumlib/unitary#51).

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

Successfully merging a pull request may close this issue.

2 participants