Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

Quantum Physics [Submitted on 22 Apr 2026] Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero The Traveling Salesman Problem is a classical NP-hard combinatorial optimization problem that has been extensively studied in operations research. A major challenge in Traveling Salesman Problem formulations is the large number of subtour elimination constraints required to ensure a valid tour. To address this issue, we adopt an iterative approach grounded in well-established operations research techniques, in which subtour elimination constraints are generated dynamically. In addition, we integrate a preprocessing phase to reduce the number of candidate arcs. In this work, we investigate both classical and quantum optimization approaches for solving the problem using the proposed framework. In particular, for quantum optimization we analyze quantum annealing techniques within the D-Wave framework, considering both direct quantum execution on the QPU and hybrid quantum classical solvers. Computational experiments show that the proposed strategies significantly reduce the model size and lead to positive improvements in computational performance across classical, direct quantum, and hybrid optimization approaches. Subjects: Quantum Physics (quant-ph) Cite as: arXiv:2604.20321 [quant-ph]   (or arXiv:2604.20321v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.20321 Focus to learn more Submission history From: Alessia Ciacco [view email] [v1] Wed, 22 Apr 2026 08:20:17 UTC (510 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)