EUVIMEDEUVIMED entdecken
Crossref

On the QUBO formulation of the Hamiltonian cycle problem

Amélia Durbec, Amina El Yaagoubi, Samuel Deleplanque iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

Hamiltonian cycle problemIsingQUBOoptimization

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}
}
Kostenlos starten →