Papers › Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems
Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems
Chandeepa Dissanayake
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections