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

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