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

Mathematics

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

Hendrik Künnemann, Frank Phillipson

Published Jun 16, 2023• 1 citation
Publisher

Abstract

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.

DOI
10.3390/math11122741

Related papers

QUBO Formulation of the Shortest Path Algorithm and its Evaluation on a Quantum Annealer

Renáta Rusnáková, Martin Chovanec, Maroš Harahus +1 more

This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.

IEEE World Symposium on Applied Machine Intelligence and Informatics (SAMI)•Jan 23, 2025•0 citations

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

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•7 citations

Solving the Max-Flow Problem on a Quantum Annealing Computer

Thomas Krauss, Joey McCollum, Chapman Pendery +2 more

This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph $\sum _i{c_i}$. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to $\mathcal {O}(|E| \log C_{\max })$, where $|E|$ and $C_{\max }$ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using $|V|$ qubits, where $|V|$ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.

IEEE Transactions on Quantum Engineering•Jan 1, 2020•30 citations

Formulations for Quantum Annealed Project Scheduling

U Kanade

Resource constrained project scheduling and related allocation tasks can be expressed as Quadratic Unconstrained Binary Optimization (QUBO) models and submitted to quantum annealers. This paper develops the QUBO formulation in detail: choice of binary variables, linear and quadratic objective terms, conversion of precedence and resource constraints into penalty functions, and calibration of penalty weights. The resulting Hamiltonian is embedded onto quantum hardware, annealed, and post-processed. Hybrid classical–quantum workflows that wrap the QUBO solver inside Monte Carlo risk analysis or a digital twin are examined. Supporting process flowcharts and energy-landscape figures illustrate every stage. The treatment remains grounded in construction and logistics applications while remaining transferable to other combinatorial domains such as ULD configuration. Keywords: QUBO formulation; quantum annealing; Ising model; penalty methods; resource-constrained project scheduling; hybrid quantum-classical; minor embedding; Monte Carlo; digital twin.

International Journal of Creative and Open Research in Engineering and Management•Aug 22, 2026•0 citations

QUBO formulations for parallel machine scheduling

Frank Phillipson, Yoseph Y. Hutten

This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.

Computers & Operations Research•Sep 11, 2026•0 citations
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.
This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.
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)'.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph ∑ici\sum _i{c_i}∑i​ci​. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to O(∣E∣log⁡Cmax⁡)\mathcal {O}(|E| \log C_{\max })O(∣E∣logCmax​), where ∣E∣|E|∣E∣ and Cmax⁡C_{\max }Cmax​ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using ∣V∣|V|∣V∣ qubits, where ∣V∣|V|∣V∣ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.
Resource constrained project scheduling and related allocation tasks can be expressed as Quadratic Unconstrained Binary Optimization (QUBO) models and submitted to quantum annealers. This paper develops the QUBO formulation in detail: choice of binary variables, linear and quadratic objective terms, conversion of precedence and resource constraints into penalty functions, and calibration of penalty weights. The resulting Hamiltonian is embedded onto quantum hardware, annealed, and post-processed. Hybrid classical–quantum workflows that wrap the QUBO solver inside Monte Carlo risk analysis or a digital twin are examined. Supporting process flowcharts and energy-landscape figures illustrate every stage. The treatment remains grounded in construction and logistics applications while remaining transferable to other combinatorial domains such as ULD configuration. Keywords: QUBO formulation; quantum annealing; Ising model; penalty methods; resource-constrained project scheduling; hybrid quantum-classical; minor embedding; Monte Carlo; digital twin.
This paper investigates several Quadratic Unconstrained Binary optimisation (QUBO) formulations for the parallel machine scheduling problem P m | | C max with the goal of assessing their suitability for quantum annealing and related heuristic optimisation methods. Three QUBO models are constructed, ranging from formulations derived from classical integer and one-hot encodings to a more compact load-balancing based representation. Extensive computational experiments using Simulated Annealing (SA) and Quantum Annealing (QA) reveal substantial differences in scalability and solution quality among the formulations. The alternative load-balanced model consistently yields near-optimal makespans, typically within 1%–3% of the theoretical lower bound, highlighting its stability and effectiveness compared to the more penalty sensitive formulations, whose performance deteriorates for larger instances. Sensitivity analyses further reveal that the appropriate selection of penalty weights and problem-specific parameter tuning significantly influences both solution accuracy and computational effort in QUBO formulations. While current quantum hardware limitations restrict experimentation to small problem sizes, the findings illustrate how compact QUBO designs can better exploit quantum optimisation frameworks. The insights gained in this study provide practical modelling guidelines for future quantum scheduling research and lay the groundwork for extending QUBO-based approaches to more complex scheduling environments. • Three QUBO formulations are compared for identical parallel machine scheduling. • A compact load-balancing QUBO avoids auxiliary variables. • Load balancing yields makespans on average within 1–3%. • Both simulated and quantum annealing produce near-optimal schedules. • Penalty selection and encoding strongly affect scalability and solution quality.