A Hybrid Classical-Quantum Annealing Algorithm for the TSP
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917479342669824 |
|---|---|
| author | Hu, Siwei Lopata, Victor Sinno, Salvatore Thuravakkath, Shruthi Zuliani, Paolo |
| author_facet | Hu, Siwei Lopata, Victor Sinno, Salvatore Thuravakkath, Shruthi Zuliani, Paolo |
| contents | Hybrid quantum-classical algorithms can help mitigating the physical limitations of current quantum devices, particularly the low qubit count and the reduced topological connectivity. In this paper, we propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP). Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance, producing a sub-TSP of a size suitable to be efficiently solved by a quantum device. The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09616 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Hybrid Classical-Quantum Annealing Algorithm for the TSP Hu, Siwei Lopata, Victor Sinno, Salvatore Thuravakkath, Shruthi Zuliani, Paolo Quantum Physics Emerging Technologies Hybrid quantum-classical algorithms can help mitigating the physical limitations of current quantum devices, particularly the low qubit count and the reduced topological connectivity. In this paper, we propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP). Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance, producing a sub-TSP of a size suitable to be efficiently solved by a quantum device. The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer. |
| title | A Hybrid Classical-Quantum Annealing Algorithm for the TSP |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2605.09616 |