BIP mapping pass #6580
Merged
BIP mapping pass #6580
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Pr mip routing
Improved doc
Improved logical/physical qubit mapping
|
|
Add release note fix typos
Update docstring fix typo
1ucian0
reviewed
Jun 29, 2021
1ucian0
reviewed
Jun 29, 2021
1ucian0
reviewed
Jun 29, 2021
1ucian0
reviewed
Jun 29, 2021
1ucian0
reviewed
Jun 29, 2021
gnannicini
reviewed
Jun 29, 2021
Comment on lines
+214
to
+229
| for t in range(self.depth): | ||
| for (p, q) in self.gates[t]: | ||
| for (i, j) in self._arcs: | ||
| # Apply McCormick to y[t, p, q, i, j] == w[t, p, i] * w[t, q, j] | ||
| mdl.add_constraint( | ||
| y[t, p, q, i, j] >= w[t, p, i] + w[t, q, j] - 1, | ||
| ctname=f"McCormickLB_{p}_{q}_{i}_{j}_at_{t}", | ||
| ) | ||
| mdl.add_constraint( | ||
| y[t, p, q, i, j] <= w[t, p, i], | ||
| ctname=f"McCormickUB1_{p}_{q}_{i}_{j}_at_{t}", | ||
| ) | ||
| mdl.add_constraint( | ||
| y[t, p, q, i, j] <= w[t, q, j], | ||
| ctname=f"McCormickUB2_{p}_{q}_{i}_{j}_at_{t}", | ||
| ) |
There was a problem hiding this comment.
There is a better version of these constraints that is stronger.
Suggested:
for t in range(self.depth-1):
for (p, q) in self.gates[t]:
for (i, j) in self._arcs:
# Stronger version of McCormick: gate (p,q) is implemented at (i, j) iff i moves to i or j, and j moves to i or j
mdl.add_constraint(
y[t, p, q, i, j] >= x[t, p, i, i] + x[t, p, i, j] + x[t, q, j, i] + x[t, q, j, j] - 1,
ctname=f"McCormickLB_{p}_{q}_{i}_{j}_at_{t}",
)
mdl.add_constraint(
y[t, p, q, i, j] <= x[t, p, i, i] + x[t, p, i, j],
ctname=f"McCormickUB1_{p}_{q}_{i}_{j}_at_{t}",
)
mdl.add_constraint(
y[t, p, q, i, j] <= x[t, q, j, i] + x[t, q, j, j],
ctname=f"McCormickUB2_{p}_{q}_{i}_{j}_at_{t}",
)
# For last time step, use regular McCormick
for (p, q) in self.gates[self.depth - 1]:
for (i, j) in self._arcs:
# Apply McCormick to y[self.depth - 1, p, q, i, j] == w[self.depth - 1, p, i] * w[self.depth - 1, q, j]
mdl.add_constraint(
y[self.depth - 1, p, q, i, j] >= w[self.depth - 1, p, i] + w[self.depth - 1, q, j] - 1,
ctname=f"McCormickLB_{p}_{q}_{i}_{j}_at_last",
)
mdl.add_constraint(
y[self.depth - 1, p, q, i, j] <= w[self.depth - 1, p, i],
ctname=f"McCormickUB1_{p}_{q}_{i}_{j}_at_last",
)
mdl.add_constraint(
y[self.depth - 1, p, q, i, j] <= w[self.depth - 1, q, j],
ctname=f"McCormickUB2_{p}_{q}_{i}_{j}_at_last",
)
There was a problem hiding this comment.
I prefer the current constraints for several reasons:
- they are the same as described in arxiv paper cited in the docstring (users would read this code with the paper in hand and would be confused if different-looking constraints show up)
- they are fewer lines and easier to read (suggesting easier to understand)
- there is no difference in performance between the suggested ones and the current ones (at least QV circuits in my env).
There was a problem hiding this comment.
- I can update the paper, and I am planning to do so -- the reason they are not indicated in the paper is oversight, not a deliberate choice.
- True, the current constraints are easier to understand.
- The proposed set of constraints is stronger. It is very well possible that one cannot observe the difference on smaller instances, as you say, but on larger QV circuits solved to optimality, the version that I am proposing is better. From an optimization standpoint, there is no reason to choose the weaker version. For large QV experiments, we need the best model we can get.
There was a problem hiding this comment.
I'd personally like to push the suggested change to a follow-up PR after the revised version of the paper is published in the future. I'd like to ask comments for others on this point.
There was a problem hiding this comment.
If there's a better/stronger version, let's update to it (follow-up PR is fine).
1ucian0
reviewed
Jun 29, 2021
itoko
commented
Jun 30, 2021
ajavadia
reviewed
Jul 1, 2021
Co-authored-by: Ali Javadi-Abhari <ajavadia@users.noreply.github.com>
Co-authored-by: Ali Javadi-Abhari <ajavadia@users.noreply.github.com>
Co-authored-by: Ali Javadi-Abhari <ajavadia@users.noreply.github.com>
Co-authored-by: Ali Javadi-Abhari <ajavadia@users.noreply.github.com>
Co-authored-by: Ali Javadi-Abhari <ajavadia@users.noreply.github.com>
Co-authored-by: Ali Javadi-Abhari <ajavadia@users.noreply.github.com>
1ucian0
approved these changes
Jul 1, 2021
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Summary
Add BIP-based mapping pass, which does layout and routing at once as described in https://arxiv.org/abs/2106.06446.
Closes #6437
Details and comments
BIPMappingpass is added as aroutingpass while it actually doeslayoutandroutingat once (termed "mapping" to stand for "layout and routing"). It employs BIP (binary integer programming) to represent the mapping problem and relies on CPLEX solver to solve the problem, as implemented inBIPMappingModel. This introduces the dependencies to external libraries:docplex(for representing the BIP problem) andcplex(for solving the BIP problem). That implies the paid version ofcplexmay be needed to solve large BIP problems (roughly, mapping of circuits with more than 5 qubits).Optional:
Add "error_rate" and "balanced" objectiveCo-authored-by: Giacomo Nannicini (@gnannicini )