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

Hendrik Künnemann and Frank Phillipson ()
Additional contact information
Hendrik Künnemann: School of Business and Economic, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands
Frank Phillipson: School of Business and Economic, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands

Mathematics, 2023, vol. 11, issue 12, 1-18

Abstract: The problem of finding the maximum weighted cycle in a directed graph map to solve optimization problems is NP -hard, implying that approaches in classical computing are inefficient. Here, Quantum computing might be a promising alternative. Many current approaches to 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 available (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, a direct embedding on the quantum annealer and two types of quantum hybrid solvers were utilized. Simulated Annealing and the usage of the hybrid CQM (Constrained Quadratic Model) had promising functionality. 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.

Keywords: QUBO; graph theory; maximum weighted cycle; debt graphs (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/12/2741/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/12/2741/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:12:p:2741-:d:1173036

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().