csookim
commented
3 months ago Looping Behavior in Qibo SABRE
Introduction
When the SABRE router encounters a two-qubit gate that cannot be executed due to hardware constraints, it adds a sequence of SWAPs to make the two-qubit gate executable. SABRE generates candidate SWAPs and selects one based on a defined formula. This process is repeated until the two-qubit gate becomes executable. However, since SABRE is a heuristic algorithm, the process can sometimes get stuck in a loop.
Problem
In some cases, SABRE adds a repeated sequence of similar SWAPs. For example, a 10-qubit circuit with the following connectivity:
qubit_array = [(7, 2), (6, 0), (5, 6), (4, 8), (3, 5), (9, 1)]is routed with 156 SWAPs using the Trivial placer and SABRE router. (After modification, the number of SWAPs is reduced to 17.) This example is illustrated in the notebook.
Solution
To solve this, the number of SWAPs is managed until every routing is made. Notebook
...
self.circuit.update(best_candidate) # SWAP is added
self._added_swaps += 1
..._added_swaps is counted after one SWAP is picked from the candidate SWAPs. If routing is completed (a two-qubit gate becomes executable), _added_swaps is reset to 0.
...
if self._added_swaps > 1.5 * longest_path: # threshold is arbitrary
self.circuit = deepcopy(self._saved_circuit)
self._route_to_nearest_gate()
...If _added_swaps exceeds the threshold, the nearest two-qubit gate is routed manually. The two-qubit gate with the minimum distance between the qubits is selected, and qubit 1 is moved adjacent to qubit 2.
Tests
When routing 30 random CZ circuits with the Random placer and original SABRE router, there are cases where more than 100 SWAPs are added.
After modification, no such cases were found.
Discussion
-
Qiskit also has the same issue and a similar solution. Reference, line 559.
-
Setting the Threshold: The current threshold is set to
1.5 * longest pathin the current connectivity. This value is somewhat arbitrary and might need tuning. -
Routing the Nearest Two-Qubit Gate: Currently, the algorithm routes the nearest two-qubit gate by moving qubit 1 adjacent to qubit 2. This method ensures the selected gate will be routed, but alternative strategies might be considered.
scarrazza
There is a bug in the SABRE algorithm, and I modified
router.pyto fix it. Is it okay to make a PR? My code is in a forked repo. Below is the explanation.