Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Australasian Computer Science Week Multiconference (ACSW)

Solving the Hamiltonian Cycle Problem using a Quantum Computer

Anuradha Mahasinghe, Richard Hua, Michael J. Dinneen, Rajni Goyal

Published Jan 14, 2019• 23 citations
Publisher

Abstract

We review existing quantum computational methods for solving the Hamiltonian cycle problem in different computational frameworks such as quantum circuits, quantum walks and adiabatic quantum computation. Then we present a QUBO (quadratic unconstrained binary optimization) formulation, which is suitable for the adiabatic quantum computation for a D-Wave architecture. Further, we derive a physical Hamiltonian from the QUBO formulation and discuss its adequateness in the adiabatic framework. Finally, we discuss the complexity of running the Hamiltonian cycle QUBO on a D-Wave quantum computer, and compare it with existing quantum computational methods.

DOI
10.1145/3290688.3290703

Related papers

On the QUBO formulation of the Hamiltonian cycle problem

Amélia Durbec, Amina El Yaagoubi, Samuel Deleplanque

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)'.

Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Dec 11, 2025•0 citations

Algorithmic QUBO formulations for k -SAT and hamiltonian cycles

Jonas Nüßlein, Thomas Gabor, Claudia Linnhoff–Popien +1 more

Quadratic Unconstrained Binary Optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO formulations for k-SAT and Hamiltonian Cycles that scale significantly better than existing approaches. For k-SAT we reduce the growth of the QUBO matrix from O(k) to O(log(k)). For Hamiltonian Cycles the matrix no longer grows quadratically in the number of nodes, as currently, but linearly in the number of edges and logarithmically in the number of nodes.

arXiv:2204.13539•Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•18 citations

Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer

Kai Liu, Michael J. Dinneen

We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.

IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)•Dec 1, 2019•6 citations

Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing

Hendrik Künnemann, Frank Phillipson

The problem of finding the maximum weighted cycle in a directed graph maps to optimization problems in NP, implying that approaches in classical computing are inefficient. Here, Quantum computing might be a promising alternative. Many current approaches on the quantum computer are based on a Quadratic Unconstrained Binary Optimization (QUBO) problem formulation. This paper develops four different QUBO approaches to this problem. The first two take the starting vertex and the number of vertices used in the cycle as given, while the latter two loosen the second assumption of knowing the size of the cycle. A QUBO formulation is derived for each approach. Further, the number of binary variables required to encode the maximum weighted cycle problem with one or both assumptions for the respective approach is made explicit. The problem is motivated by finding the maximum weighted debt cycle in a debt graph. This paper compares classical computing versus currently avaiable (hybrid) quantum computing approaches for various debt graphs. For the classical part, it investigated the Depth-First-Search (DFS) method and Simulated Annealing. For the (hybrid) quantum approaches, we utilized direct embedding on the quantum annealer and two types of quantum hybrid solvers. Simulated Annealing and the usage of the hybrid CQM (Constrained Quadratic Model) machine functioned promising. The DFS method, direct QPU, and hybrid BQM (Binary Quadratic Model), on the other hand, performed less, due to memory issues, surpassing the limit of decision variables, and finding the right penalty values, respectively.

Mathematics•Jun 16, 2023•1 citation

A QUBO Formulation for Qubit Allocation

Bryan Dury, Olivia Di Matteo

To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.

arXiv:2009.00140•Aug 31, 2020•10 citations

Quantum solution for solving the Bin Packing problem

Samuel Deleplanque, Amélia Durbec, Amina El Yaagoubi

Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.

International Conference on Control, Decision and Information Technologies (CoDIT)•Jul 1, 2024•1 citation
We review existing quantum computational methods for solving the Hamiltonian cycle problem in different computational frameworks such as quantum circuits, quantum walks and adiabatic quantum computation. Then we present a QUBO (quadratic unconstrained binary optimization) formulation, which is suitable for the adiabatic quantum computation for a D-Wave architecture. Further, we derive a physical Hamiltonian from the QUBO formulation and discuss its adequateness in the adiabatic framework. Finally, we discuss the complexity of running the Hamiltonian cycle QUBO on a D-Wave quantum computer, and compare it with existing quantum computational methods.
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)'.
Quadratic Unconstrained Binary Optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO formulations for k-SAT and Hamiltonian Cycles that scale significantly better than existing approaches. For k-SAT we reduce the growth of the QUBO matrix from O(k) to O(log(k)). For Hamiltonian Cycles the matrix no longer grows quadratically in the number of nodes, as currently, but linearly in the number of edges and logarithmically in the number of nodes.
We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.
The problem of finding the maximum weighted cycle in a directed graph maps to optimization problems in NP, implying that approaches in classical computing are inefficient. Here, Quantum computing might be a promising alternative. Many current approaches on the quantum computer are based on a Quadratic Unconstrained Binary Optimization (QUBO) problem formulation. This paper develops four different QUBO approaches to this problem. The first two take the starting vertex and the number of vertices used in the cycle as given, while the latter two loosen the second assumption of knowing the size of the cycle. A QUBO formulation is derived for each approach. Further, the number of binary variables required to encode the maximum weighted cycle problem with one or both assumptions for the respective approach is made explicit. The problem is motivated by finding the maximum weighted debt cycle in a debt graph. This paper compares classical computing versus currently avaiable (hybrid) quantum computing approaches for various debt graphs. For the classical part, it investigated the Depth-First-Search (DFS) method and Simulated Annealing. For the (hybrid) quantum approaches, we utilized direct embedding on the quantum annealer and two types of quantum hybrid solvers. Simulated Annealing and the usage of the hybrid CQM (Constrained Quadratic Model) machine functioned promising. The DFS method, direct QPU, and hybrid BQM (Binary Quadratic Model), on the other hand, performed less, due to memory issues, surpassing the limit of decision variables, and finding the right penalty values, respectively.
To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.