On the QUBO formulation of the Hamiltonian cycle problem
Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · 11.12.2025 · 383 (2310)
DOI: 10.1098/rsta.2024.0559 ↗Kurz gefasst
Fachartikel in der Zeitschrift Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences, online erschienen am 11.12.2025. Verfasst von Amélia Durbec und 2 weiteren Autor:innen. Beteiligte Einrichtung: ICL, Junia, Université Catholique de Lille, LITL , F-59000 Lille, Hauts-de-France, France. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 53 Literaturangaben. Gefördert von: Région Hauts-de-France.
Abstract (Originalsprache)
Combinatorial problems pose significant challenges, especially for large-scale instances. A promising approach to addressing these challenges involves quadratic unconstrained binary optimization (QUBO) models, a key framework in quantum computing. QUBO formulations require tailored approaches owing to their unique characteristics and the hardware constraints of quantum systems. This paper focuses on the QUBO formulations of the Hamiltonian cycle problem (HCP). We analyse three QUBO formulations for the HCP, including two inspired by Lagrangian relaxation techniques, where penalties may result in negative costs for certain solutions but are balanced within the model. A preprocessing methodology is also introduced. To evaluate these models, we employ D-Wave quantum annealers, which feature a fixed qubit topology and impose strict resource constraints. The mapping of QUBOs on to this architecture highlights the importance of efficient model design. Through experimental studies, we analyse the performance of the proposed QUBOs with and without preprocessing. This article is part of the theme issue ‘Quantum theory and topology in models of decision making (Part 2)’.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- ICL, Junia, Université Catholique de Lille, LITL , F-59000 Lille, Hauts-de-France, France.
- CNRS, JUNIA, Centrale Lille, Univ. Polytechnique H-d-F, UMR 8520 - IEMN , 59652 VILLENEUVE D'ASCQ, France.
ORCID-Profile: Samuel Deleplanque
Förderung
- Région Hauts-de-France
Zitieren
APA
Durbec, A., El Yaagoubi, A., & Deleplanque, S. (2025). On the QUBO formulation of the Hamiltonian cycle problem. Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences, 383(2310). https://doi.org/10.1098/rsta.2024.0559
Vancouver
Durbec A, El Yaagoubi A, Deleplanque S. On the QUBO formulation of the Hamiltonian cycle problem. Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences. 2025;383(2310). doi:10.1098/rsta.2024.0559
BibTeX
@article{Durbec2025,
author = {Durbec, Amélia and El Yaagoubi, Amina and Deleplanque, Samuel},
title = {On the QUBO formulation of the Hamiltonian cycle problem},
journal = {Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences},
year = {2025},
volume = {383},
number = {2310},
doi = {10.1098/rsta.2024.0559}
}
EUVIMED