Quantum and Quantum-Inspired Algorithms for Combinatorial Optimization Problems

Combinatorial optimization problems are considered a promising application area for quantum computing, with the class of Quadratic Unconstraint Binary Optimization (QUBO) problems playing a central role. Solving such problems is a key application goal of projects like Rymax (Sengstock) and the Digital Annealer by D-Wave. Projects P9 (Mnich) and P10 (Mottet) also target combinatorial optimization problems. Furthermore, QUBO solutions can provide good initializations in machine learning (P3a, Mathey). While there is strong heuristic motivation for quantum computing to provide runtime advantages for QUBO problems compared to conventional computing, the existence of such advantages – especially regarding applications – remains largely unclear at a rigorous theoretical level.
This project aims to expand the theoretical understanding of such quantum advantages while analyzing the runtime of quantum and classical algorithms for practically relevant problems. The best classical solution methods are inspired by quantum computing itself. They have been increasingly developed by companies such as Fujitsu, Hitachi, NTT, and Toshiba since 2019 and have recently been successfully deployed in industry. However, these computational methods are comparatively underexplored on a theoretical level, and their runtimes are poorly understood. Therefore, this project will investigate the properties of a QUBO problem that determine the runtime for its solution. This information will be used to decide which computational model (conventional HPCs, quantum-inspired computing, or quantum computing) is best suited for solving application-relevant QUBO problems and what runtimes can be expected for each.