  The field of Quantum Computing has gathered significant popularity in recent
years and a large number of papers have studied its effectiveness in tackling
many tasks. We focus in particular on Quantum Annealing (QA), a meta-heuristic
solver for Quadratic Unconstrained Binary Optimization (QUBO) problems. It is
known that the effectiveness of QA is dependent on the task itself, as is the
case for classical solvers, but there is not yet a clear understanding of which
are the characteristics of a problem that makes it difficult to solve with QA.
In this work, we propose a new methodology to study the effectiveness of QA
based on meta-learning models. To do so, we first build a dataset composed of
more than five thousand instances of ten different optimization problems. We
define a set of more than a hundred features to describe their characteristics,
and solve them with both QA and three classical solvers. We publish this
dataset online for future research. Then, we train multiple meta-models to
predict whether QA would solve that instance effectively and use them to probe
which are the features with the strongest impact on the effectiveness of QA.
Our results indicate that it is possible to accurately predict the
effectiveness of QA, validating our methodology. Furthermore, we observe that
the distribution of the problem coefficients representing the bias and coupling
terms is very informative to identify the probability of finding good
solutions, while the density of these coefficients alone is not enough. The
methodology we propose allows to open new research directions to further our
understanding of the effectiveness of QA, by probing specific dimensions or by
developing new QUBO formulations that are better suited for the particular
nature of QA. Furthermore, the proposed methodology is flexible and can be
extended or used to study other quantum or classical solvers.
