An example showing the embedding scheme outlined in Lem

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.	© Copyright Policy - open-access Related In: Results - Collection License Show All Figures getmorefigures.php?uid=PMC5037405&req=5 f5: An example showing the embedding scheme outlined in Lemma 1.The nodes and the trees mapped from the nodes are marked with the same colors. Mentions: In Fig. 5 we show an example of embedding K7,10 into F(3, 2, 4). A natural corollary of Lemma 1 is that any bipartite graph between p and q nodes can be minor embedded in . We are then prepared to handle embedding the parts of the interaction graphs of HSCP, which are but bipartite graphs (see Fig. 2b for example).

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 showing the embedding scheme outlined in Lemma 1.The nodes and the trees mapped from the nodes are marked with the same colors.

Related In: Results - Collection

License

Show All Figures

getmorefigures.php?uid=PMC5037405&req=5

f5: An example showing the embedding scheme outlined in Lemma 1.The nodes and the trees mapped from the nodes are marked with the same colors.

Mentions: In Fig. 5 we show an example of embedding K7,10 into F(3, 2, 4). A natural corollary of Lemma 1 is that any bipartite graph between p and q nodes can be minor embedded in . We are then prepared to handle embedding the parts of the interaction graphs of HSCP, which are but bipartite graphs (see Fig. 2b for example).