Document Type
Article
Language
eng
Format of Original
15 p.
Publication Date
2016
Publisher
Nature Publishing Group (Macmillan Publishers Limited)
Source Publication
Scientific Reports
Source ISSN
2045-2322
Original Item ID
DOI: 10.1038/srep33957
Abstract
Here we consider using quantum annealing to solve Set Cover with Pairs (SCP), an NP-hard combinatorial optimization problem that plays an important role in networking, computational biology, and biochemistry. We show an explicit construction of Ising Hamiltonians whose ground states encode the solution of SCP instances. We numerically simulate the time-dependent Schrödinger equation in order to test the performance of quantum annealing for random instances and compare with that of simulated annealing. We also discuss explicit embedding strategies for realizing our Hamiltonian construction on the D-wave type restricted Ising Hamiltonian based on Chimera graphs. Our embedding on the Chimera graph preserves the structure of the original SCP instance and in particular, the embedding for general complete bipartite graphs and logical disjunctions may be of broader use than that the specific problem we deal with.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Cao, Yudong; Jiang, Shuxian; Perouli, Debbie; and Kais, Sabre, "Solving Set Cover with Pairs Problem using Quantum Annealing" (2016). Mathematics, Statistics and Computer Science Faculty Research and Publications. 482.
https://epublications.marquette.edu/mscs_fac/482
Comments
Published version. Scientific Reports, Vol. 6 (2016). DOI. © 2016 The Author(s). Used with permission.