  Quantum annealing is a promising technique which leverages quantum mechanics
to solve hard optimization problems. Considerable progress has been made in the
development of a physical quantum annealer, motivating the study of methods to
enhance the efficiency of such a solver. In this work, we present a quantum
annealing approach to measure similarity among molecular structures.
Implementing real-world problems on a quantum annealer is challenging due to
hardware limitations such as sparse connectivity, intrinsic control error, and
limited precision. In order to overcome the limited connectivity, a problem
must be reformulated using minor-embedding techniques. Using a real data set,
we investigate the performance of a quantum annealer in solving the molecular
similarity problem. We provide experimental evidence that common practices for
embedding can be replaced by new alternatives which mitigate some of the
hardware limitations and enhance its performance. Common practices for
embedding include minimizing either the number of qubits or the chain length,
and determining the strength of ferromagnetic couplers empirically. We show
that current criteria for selecting an embedding do not improve the hardware's
performance for the molecular similarity problem. Furthermore, we use a
theoretical approach to determine the strength of ferromagnetic couplers. Such
an approach removes the computational burden of the current empirical
approaches, and also results in hardware solutions that can benefit from simple
local classical improvement. Although our results are limited to the problems
considered here, they can be generalized to guide future benchmarking studies.
