Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing
The problem of finding the maximum weighted cycle in a directed graph map to solve optimization problems is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">NP</mi></se...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-06-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/12/2741 |
| _version_ | 1797593658129645568 |
|---|---|
| author | Hendrik Künnemann Frank Phillipson |
| author_facet | Hendrik Künnemann Frank Phillipson |
| author_sort | Hendrik Künnemann |
| collection | DOAJ |
| description | The problem of finding the maximum weighted cycle in a directed graph map to solve optimization problems is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">NP</mi></semantics></math></inline-formula>-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. |
| first_indexed | 2024-03-11T02:11:26Z |
| format | Article |
| id | doaj.art-826598cfb9434815af7066928abd2248 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T02:11:26Z |
| publishDate | 2023-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-826598cfb9434815af7066928abd22482023-11-18T11:29:08ZengMDPI AGMathematics2227-73902023-06-011112274110.3390/math11122741Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum AnnealingHendrik Künnemann0Frank Phillipson1School of Business and Economic, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The NetherlandsSchool of Business and Economic, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The NetherlandsThe problem of finding the maximum weighted cycle in a directed graph map to solve optimization problems is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">NP</mi></semantics></math></inline-formula>-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.https://www.mdpi.com/2227-7390/11/12/2741QUBOgraph theorymaximum weighted cycledebt graphs |
| spellingShingle | Hendrik Künnemann Frank Phillipson Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing Mathematics QUBO graph theory maximum weighted cycle debt graphs |
| title | Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing |
| title_full | Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing |
| title_fullStr | Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing |
| title_full_unstemmed | Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing |
| title_short | Finding Debt Cycles: QUBO Formulations for the Maximum Weighted Cycle Problem Solved Using Quantum Annealing |
| title_sort | finding debt cycles qubo formulations for the maximum weighted cycle problem solved using quantum annealing |
| topic | QUBO graph theory maximum weighted cycle debt graphs |
| url | https://www.mdpi.com/2227-7390/11/12/2741 |
| work_keys_str_mv | AT hendrikkunnemann findingdebtcyclesquboformulationsforthemaximumweightedcycleproblemsolvedusingquantumannealing AT frankphillipson findingdebtcyclesquboformulationsforthemaximumweightedcycleproblemsolvedusingquantumannealing |