QUBO Formulations for Arithmetic Progression Graph Labeling Problems
Cristian S. Calude, Michael J. Dinneen and Yitong Liu
The Arithmetic Progression Graph Labeling is an NP-complete problem with various applications, including optimizing scheduling problems. This paper presents Quadratic Unconstrained Boolean Optimization solutions for the version of the problem with fixed vertex labels and the original problem. We use and compare standard (D-Wave Advantage and Advantage 2 Prototype) quantum annealers and hybrid (D-Wave Leap Hybrid Solver Service) methods to solve these problems with D-Wave quantum machines. Our experiments suggest that the hybrid methods outperform the standard ones.
Keywords: Adiabatic quantum computing, QUBO, arithmetic progression graphs