Limits...
Solving Set Cover with Pairs Problem using Quantum Annealing

View Article: PubMed Central - PubMed

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.

No MeSH data available.


An example of embedding L10 onto F(5, 2, 4).Each color in the left diagram represents a node u in L10 and the nodes of the same color in the right diagram shows μ10(u).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC5037405&req=5

f6: An example of embedding L10 onto F(5, 2, 4).Each color in the left diagram represents a node u in L10 and the nodes of the same color in the right diagram shows μ10(u).

Mentions: In Fig. 6 we show an example of L10. For any , let rk be the number of pairs that cover k. Then . Hence in order to show that we could embed any onto a Chimera graph, it suffices to show that we can embed any Ln onto a Chimera graph. We show this in the following Lemma for c = 4.


Solving Set Cover with Pairs Problem using Quantum Annealing
An example of embedding L10 onto F(5, 2, 4).Each color in the left diagram represents a node u in L10 and the nodes of the same color in the right diagram shows μ10(u).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC5037405&req=5

f6: An example of embedding L10 onto F(5, 2, 4).Each color in the left diagram represents a node u in L10 and the nodes of the same color in the right diagram shows μ10(u).
Mentions: In Fig. 6 we show an example of L10. For any , let rk be the number of pairs that cover k. Then . Hence in order to show that we could embed any onto a Chimera graph, it suffices to show that we can embed any Ln onto a Chimera graph. We show this in the following Lemma for c = 4.

View Article: PubMed Central - PubMed

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.

No MeSH data available.