EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

ILP-Based QUBO Encodings of the Traveling Salesman Problem: Derivation and Benchmarking on Quantum Annealing Hardware

Katarzyna Nałęcz-Charkiewicz

International Journal of Electronics and Telecommunications · 29.10.2026 · 72 (4) · 1-9

DOI: 10.24425/ijet.2026.6343 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Electronics and Telecommunications, online erschienen am 29.10.2026. Verfasst von Katarzyna Nałęcz-Charkiewicz. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Traveling Salesman Problem (TSP) has been one of the most intensively studied problems in theoretical computer science for decades. Being NP-hard, it is unlikely to be solved in polynomial time; hence, despite numerous classical exact and approximate methods, quantum-inspired approaches are also explored. In this study, we analyze several formulations of the TSP suitable for quantum annealing, focusing not only on qubit requirements but also on practical performance, i.e., how frequently feasible and optimal solutions are obtained. We consider both complete and non-complete graphs, reflecting common real-world scenarios. One of the analyzed formulations corresponds to a previously established Quadratic Unconstrained Binary Optimization (QUBO) model, while the others originate from classical Integer Linear Programming (ILP) formulations. We provide a unified, step-by-step translation of selected compact ILP TSP formulations into QUBO models. We analytically show that for non-complete graphs these encodings are asymptotically smaller than the commonly used baseline formulation. We benchmark the formulations using simulated and quantum annealing to evaluate their feasibility and optimality rates. The results are discussed in the context of current quantum annealing hardware limitations, including QPU size and embedding overhead.

Zitieren

APA

Nałęcz-Charkiewicz, K. (2026). ILP-Based QUBO Encodings of the Traveling Salesman Problem: Derivation and Benchmarking on Quantum Annealing Hardware. International Journal of Electronics and Telecommunications, 72(4), 1-9. https://doi.org/10.24425/ijet.2026.6343

Vancouver

Nałęcz-Charkiewicz K. ILP-Based QUBO Encodings of the Traveling Salesman Problem: Derivation and Benchmarking on Quantum Annealing Hardware. International Journal of Electronics and Telecommunications. 2026;72(4):1-9. doi:10.24425/ijet.2026.6343

BibTeX
@article{NaczCharkiewicz2026,
  author = {Nałęcz-Charkiewicz, Katarzyna},
  title = {ILP-Based QUBO Encodings of the Traveling Salesman Problem: Derivation and Benchmarking on Quantum Annealing Hardware},
  journal = {International Journal of Electronics and Telecommunications},
  year = {2026},
  volume = {72},
  number = {4},
  pages = {1--9},
  doi = {10.24425/ijet.2026.6343}
}
Kostenlos starten →