Fix Looping Behavior in Qibo SABRE

[csookim]

This PR addresses the issue #1396.

Checklist:

• [x] Reviewers confirm new code works as expected.
• [x] Tests are passing.
• [x] Coverage does not decrease.
• [x] Documentation is updated.

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 99.99%. Comparing base (c598c67) to head (eafec2a). Report is 38 commits behind head on master.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #1398 +/- ## ======================================= Coverage 99.99% 99.99% ======================================= Files 78 78 Lines 11191 11217 +26 ======================================= + Hits 11190 11216 +26 Misses 1 1 ``` | [Flag](https://app.codecov.io/gh/qiboteam/qibo/pull/1398/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=qiboteam) | Coverage Δ | | |---|---|---| | [unittests](https://app.codecov.io/gh/qiboteam/qibo/pull/1398/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=qiboteam) | `99.99% <100.00%> (+<0.01%)` | :arrow_up: | Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=qiboteam#carryforward-flags-in-the-pull-request-comment) to find out more.

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[alecandido]

Is this ready for review? Or still work in progress?

[csookim]

Is this ready for review? Or still work in progress?

Ready for review. Thanks.

[alecandido]

Ready for review. Thanks.

Then, let's appoint some reviewers during the Qibo meeting ;)

Unless you or @marekgluza have already someone to propose.

[Simone-Bordoni]

I will take care of the review. I have tried to fix this issue for many month without success. I made the algorithm using the paper https://arxiv.org/pdf/1809.02573 and I didn't manage to find this correction made by qiskit (https://github.com/Qiskit/qiskit/blob/e5ee1a8d97753ccca09b0c15be7b7ab0c1c84b90/crates/accelerate/src/sabre/route.rs#L559). Thank you for finding this out!

[Simone-Bordoni]

The implemented solution uses the shortest path routing strategy to address the prolem. This is the same euristic strategy employed in the shortest_paths router. In this router all the possible shortest paths are considered and between them the one that also matches the connectivity of the maximum amount of other gates is chosen. Integrating the shortest_paths router in the SABRE may improve its performance (in terms of added_swaps) with a small time performance reduction. I think we may have a meet to discuss this possibility in a future PR.

[Simone-Bordoni]

Can you also add a test checking that the method "_route_to_nearest_gate()" alone is correctly working? I also suggest changing the name of the method to "_shortest_path_routing()"

[csookim]

@Simone-Bordoni @BrunoLiegiBastonLiegi Thanks for the review. Will this be merged at the qibo meeting, or can I merge it myself?

[BrunoLiegiBastonLiegi]

I don't think we need to wait, but just to be sure we can ask @scarrazza.

[Simone-Bordoni]

@Simone-Bordoni @BrunoLiegiBastonLiegi Thanks for the review. Will this be merged at the qibo meeting, or can I merge it myself?

Please wait until tomorrow. I would like to have a Quick Look after the changes.