Implements the LineInititialMapper strategy #5831
Conversation
…q' namespace; made both classes not serializable
…al_mapping_setup syncing
…al_mapping_setup syncing
…al_mapping_setup syncing
…for directed graph value equality remaining
…_initial_mapper syncing
|
|
||
| @value.value_equality | ||
| class LineInitialMapper(routing.AbstractInitialMapper): | ||
| """Places logical qubits in the circuit onto physical qubits on the device.""" |
There was a problem hiding this comment.
Add a brief description to class docstring as well, highlighting high level details like an overview of strategy, expected complexity etc.
|
@tanujkhattar A few notes:
|
IIUC, the indeterminism is in graph construction in the tests then? Anyways, sorting once in the constructor to get rid of sorting in each bfs_successors and get_next_physical_qubit sounds good to me. |
| # Greedily map to highest degree neighbor that that is available | ||
| sorted_neighbors = sorted( | ||
| self.device_graph.neighbors(current_physical), | ||
| key=lambda x: self.device_graph.degree(x), |
There was a problem hiding this comment.
Should we be sorting based on "unused degree", i.e. x > y if x has more unmapped neighbors than y?
There was a problem hiding this comment.
I'll keep note of this change and try it during benchmarking!
| return neighbor | ||
| # If cannot map onto one long line of physical qubits, then break down into multiple | ||
| # small lines by finding nearest available qubit to the physical center | ||
| return self._closest_unmapped_qubit(self.center) |
There was a problem hiding this comment.
Should we find a closest unmapped qubit to current_physical instead? If the outer loop of logical qubits is iterating over a connected line, then this would ensure that we find the closest node to the previous neighbour in line (i.e. current_physical), instead of forgetting about the line position and restarting from center?
There was a problem hiding this comment.
I'll keep note of this change and try it during benchmarking!
…reltigani/Cirq into routing-line_initial_mapper syncing with master
cirq-core/cirq/transformers/routing/line_initial_mapper_test.py
Outdated
Show resolved
Hide resolved
…reltigani/Cirq into routing-line_initial_mapper syncing
tanujkhattar
added
the
automerge
CirqBot
added
the
front_of_queue_automerge
CirqBot
removed
automerge
This PR implements the main initial mapping strategy highlighted in http://tinyurl.com/cirq-qubit-routing
This PR implements the main initial mapping strategy highlighted in http://tinyurl.com/cirq-qubit-routing
This PR implements the main initial mapping strategy highlighted in http://tinyurl.com/cirq-qubit-routing