  The Closest String Problem is an NP-complete problem which appears more
commonly in bioinformatics and coding theory. Less surprisingly, classical
approaches have been pursued with two prominent algorithms being the genetic
algorithm and simulated annealing. Latest improvements to quantum computing
devices with a specialization in optimization tasks such as DWave systems,
suggest that an attempt to embed the problem in a model accepted by such
systems is worthwhile. In this work, two QUBO formulations have been proposed,
with one being a slight modification over the other. Subsequently, an
evaluation based on a few simple test cases had been carried out on both
formulations. In this regard, the D-Wave annealers have been used, while
providing guidelines for optimality on certain platform-specific concerns. For
evaluation purposes, a metric termed Occurrence Ratio (OR) has been defined.
With minimal hyperparameter tuning, the expected solutions were obtained for
every test case and the optimality was guaranteed. To address practical and
implementation issues, an inherent decomposition strategy based on the
possibility of having substrings has been elucidated to accommodate the
restricted qubit count. Conclusively, the need for further investigation on
tuning the hyperparameters is emphasized.
