Divide-et-impera Heuristic-based Randomized Search for the Qubit Routing Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911274518970368 |
|---|---|
| author | Baioletti, Marco Fagiolo, Fabrizio Oddi, Angelo Rasconi, Riccardo |
| author_facet | Baioletti, Marco Fagiolo, Fabrizio Oddi, Angelo Rasconi, Riccardo |
| contents | This paper introduces the DIRSH algorithm for the Qubit Routing Problem (QRP), using a heuristic-guided randomized divide-and-conquer strategy. The method splits the circuit into chunks and optimizes each one with a stochastic selection of gates and swaps. It balances global search, via restarts and adaptive tuning of bandit parameters with depth-sensitive local pruning. Tested on RevLib benchmarks mapped to the 20-qubit IBMQ Tokyo topology, DIRSH outperformed three LightSABRE variants across different time budgets, achieving shorter depths and fewer swaps. These results confirm that combining chunk-based decomposition with bandit-driven heuristics is effective for routing quantum circuits on NISQ devices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14644 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Divide-et-impera Heuristic-based Randomized Search for the Qubit Routing Problem Baioletti, Marco Fagiolo, Fabrizio Oddi, Angelo Rasconi, Riccardo Quantum Physics Emerging Technologies This paper introduces the DIRSH algorithm for the Qubit Routing Problem (QRP), using a heuristic-guided randomized divide-and-conquer strategy. The method splits the circuit into chunks and optimizes each one with a stochastic selection of gates and swaps. It balances global search, via restarts and adaptive tuning of bandit parameters with depth-sensitive local pruning. Tested on RevLib benchmarks mapped to the 20-qubit IBMQ Tokyo topology, DIRSH outperformed three LightSABRE variants across different time budgets, achieving shorter depths and fewer swaps. These results confirm that combining chunk-based decomposition with bandit-driven heuristics is effective for routing quantum circuits on NISQ devices. |
| title | Divide-et-impera Heuristic-based Randomized Search for the Qubit Routing Problem |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2511.14644 |