Looping Behavior in Qibo SABRE

[csookim]

There is a bug in the SABRE algorithm, and I modified router.py to fix it. Is it okay to make a PR? My code is in a forked repo. Below is the explanation.

[csookim]

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 path in 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]

Thanks @csookim for this analysis and tests. Let me invite @Simone-Bordoni to have a look and confirm your findings, meanwhile please feel free to open a PR with the suggested fix in this repository.