csookim
commented
1 month ago SABRE + CircuitMap Optimization
Previous Implementation
- The mapping scheme could be clearer.
- Using
list.index()in logical-to-physical and circuit-to-physical mapping slowed down the routing. - Frequently using the function that finds a gate's target qubits by block number was inefficient.
New Implementation
The code has been updated in three key areas:
1. Qubit Mapping
- SABRE operates using
connectivity,initial_layout, andcircuit. initial_layoutis a dictionary where"q{physical_qubit_number}": {logical_qubit_number}pairs define the initial mapping.physical_qubit_numbercorresponds to the node number inconnectivity.- The
initial_layoutandconnectivitycan have arbitraryphysical_qubit_numbers, when using restricted connectivity.
1-1. Layout Relabel
- To simplify routing,
initial_layoutandconnectivityare relabeled before routing begins. physical_qubit_numberis reassigned to a range from0tolen(connectivity.nodes) - 1.- For example, the layout
{"q4":1, "q6":2, "q3":0}might be relabeled to{"q0":1, "q1":2, "q2":0}. - This relabeling map is saved, and the final layout is reverted to the original labeling when routing is complete.
- All operations in
Sabreare performed using the updatedphysical_qubit_number.
1-2 Physical-Logical Mapping
- Due to the layout labeling, there are two sets of numbers ranging from
0tolen(connectivity.nodes()) - 1ininitial_layout. - Physical to logical mapping (
p2l) and logical to physical mapping (l2p) are implemented using two arrays:self._p2landself._l2p. - For example, with a mapping of
{"q0":1, "q1":2, "q2":0},self._p2lwould be[1, 2, 0]andself._l2pwould be[2, 0, 1]. - Routing is performed using these p2l and l2p conversions.
2. Temporary CircuitMap
- Creating a
CircuitMapincludes unnecessary operations such as block decomposition, circuit object creation, and gate copying, which are not needed for calculating the cost of a candidate swap. - Enable temporary
CircuitMapusing aself._temporaryflag. - For temporary
CircuitMapinstances used only to calculate swap costs, return immediately frominitafter initializingself._l2pandself._p2l. - In these temporary
CircuitMapinstances, skip gate additions or removals in theupdate()method.
3. Blocks in the front_layer
- SABRE calculates the cost of a swap by summing the distances of successive gates.
- To calculate the distance of a successive gate, the target qubit numbers of the gate need to be given.
- Previously, only gate (block) numbers were stored in the
front_layer. - To find the target qubits, the code had to iterate through the list of gates using
search_by_index(block), which increased runtime. - The new approach stores both the gate number and the target qubits when creating
self._dag.
- For example,
self._dag = [(0, {'qubits': (0, 9), 'layer': 0}), (1, {'qubits': (5, 9), 'layer': 1}), (2, {'qubits': (2, 8), 'layer': 0})]- The function
_get_dag_layer(n, qubits=True)returns a list of target qubits for the gates in layern. - This allows retrieval of target qubits in $O(1)$ time.
4. Additional Improvements
- Use shallow copy when copying integer lists.
Evaluation
- Test: 100 random 50-CZ gates on 20 qubits.
- Line connectivity
- Qibo SABRE is 6x faster than before.
- The reason for the reduction in the number of SWAP gates is unknown.
Mean Std
Qiskit Sabre Time 0.0439 0.0075
Qibo Sabre Time 0.0625 0.0179
Qibo Sabre Old Time 0.4252 0.106
Qiskit Sabre Swaps 189.97 21.7295
Qibo Sabre Swaps 196.54 21.8712
Qibo Sabre Old Swaps 279.96 35.739
codecov[bot]
BrunoLiegiBastonLiegi
Simone-Bordoni
To improve Sabre's performance, several implementations have been updated. I’ve added comments to the code and each comment number corresponds to the explanation numbers provided below. Please let me know if any clarifications are needed. Below is the code explanation.
Checklist:
After the code review:
_swap_candidates(), _check_execution(), _shortest_path_routing()(removeget_physical_qubits(block_num)).ShortestPaths.