  In this paper, we tackle the problem of measuring similarity among graphs
that represent real objects with noisy data. To account for noise, we relax the
definition of similarity using the maximum weighted co-$k$-plex relaxation
method, which allows dissimilarities among graphs up to a predetermined level.
We then formulate the problem as a novel quadratic unconstrained binary
optimization problem that can be solved by a quantum annealer. The context of
our study is molecular similarity where the presence of noise might be due to
regular errors in measuring molecular features. We develop a similarity measure
and use it to predict the mutagenicity of a molecule. Our results indicate that
the relaxed similarity measure, designed to accommodate the regular errors,
yields a higher prediction accuracy than the measure that ignores the noise.
