Does the structure of the QUBO problem affect the effectiveness of quantum annealing? An empirical perspective

In recent years there has been a significant interest in exploring the potential of Quantum Annealers (QA) as heuristic solvers of Quadratic Unconstrained Binary Optimization (QUBO) problems. Some problems are more difficult to solve on QA and understanding why is not straightforward, because an analytical study of the underlying physical system is intractable for large QUBO problems. This work consists in an empirical analysis of the features making a QUBO problem difficult to solve on QA, based on clusters of QUBO instances identified with Hierarchical Clustering. The analysis reveals correlations between specific values of the features and the ability of QA to solve effectively the instances. These initial results open new research opportunities to inform the development of new AI methods supporting quantum computation (e.g., for minor embedding or error mitigation) that are better tailored to the characteristics of the problem, as well as to develop better QUBO formulations for known problems in order to improve the quality of the solutions found by QA.