Manara - Qatar Research Repository
Browse

Solving Set Cover with Pairs Problem using Quantum Annealing

journal contribution
submitted on 2024-09-26, 07:20 and posted on 2024-09-26, 07:20 authored by Yudong Cao, Shuxian Jiang, Debbie Perouli, Sabre Kais

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.

Other Information

Published in: Scientific Reports
License: https://creativecommons.org/licenses/by/4.0
See article on publisher's website: https://dx.doi.org/10.1038/srep33957

Funding

Open Access funding provided by the Qatar National Library.

History

Language

  • English

Publisher

Springer Nature

Publication Year

  • 2016

License statement

This Item is licensed under the Creative Commons Attribution 4.0 International License.

Institution affiliated with

  • Hamad Bin Khalifa University
  • Qatar Environment and Energy Research Institute - HBKU

Usage metrics

    Qatar Environment and Energy Research Institute - HBKU

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC