Parallel Implementation and Scalability Analysis of Algorithms Solving QUBO Problems in HPC Systems

Over time, tremendous efforts have been devoted to developing algorithms for solving complex optimization problems. These problems require finding the best possible solutions in a large search space, which is computationally challenging. For many such problems, no algorithm is currently known to solve them in polynomial time. Despite progress, existing methods often struggle with scalability or fail to find good solutions quickly. In this work, we use high-performance computing techniques to implement Simulated Annealing and Scatter Search for solving QUBO optimization problems. These algorithms achieve significant speedups and efficiently explore the large search space. We also study quantum annealing as a promising quantum algorithm on quantum machines (QPUs). We benchmark our solvers against the NP-hard MaxCut problem and analyze the results collected using the Leonardo supercomputer. As a final milestone, we introduce AlmoQUBO, a high-performance library for solving QUBO problems that can be represented as graphs.