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.


(a) Plot of annealing time T versus number of sweeps S using the simulated annealing implementation68 on an Ising Hamiltonians of 17 spins constructed from an SCP instance. We use the default settings for all parameters other than S and R. Also we mark the optimal runtime T*. (b) Plot of optimized annealing time T* versus the number of spins involved in the Ising Hamiltonian HSCP corresponding to randomly generated SCP instances according to Algorithm 1. We also provide on the bottom plot the number of instances for each M.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f4: (a) Plot of annealing time T versus number of sweeps S using the simulated annealing implementation68 on an Ising Hamiltonians of 17 spins constructed from an SCP instance. We use the default settings for all parameters other than S and R. Also we mark the optimal runtime T*. (b) Plot of optimized annealing time T* versus the number of spins involved in the Ising Hamiltonian HSCP corresponding to randomly generated SCP instances according to Algorithm 1. We also provide on the bottom plot the number of instances for each M.

Mentions: In general w(S) increases as S increases, leading to a decrease in R. We numerically investigate this with an Ising system of Nā€‰=ā€‰17 spins generated from an SCP instance via the construction in Theorem 1. We plot the annealing time T versus S in Fig. 4a. For each SCP instance with the number of spin M we compute the optimal S* such that is the optimized runtime (Fig. 4a). We further explore how the optimal runtime T* scales as a function of the number of spins M. As shown in Fig. 4b, a linear fit on a semilog plot shows that roughly .


Solving Set Cover with Pairs Problem using Quantum Annealing
(a) Plot of annealing time T versus number of sweeps S using the simulated annealing implementation68 on an Ising Hamiltonians of 17 spins constructed from an SCP instance. We use the default settings for all parameters other than S and R. Also we mark the optimal runtime T*. (b) Plot of optimized annealing time T* versus the number of spins involved in the Ising Hamiltonian HSCP corresponding to randomly generated SCP instances according to Algorithm 1. We also provide on the bottom plot the number of instances for each M.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f4: (a) Plot of annealing time T versus number of sweeps S using the simulated annealing implementation68 on an Ising Hamiltonians of 17 spins constructed from an SCP instance. We use the default settings for all parameters other than S and R. Also we mark the optimal runtime T*. (b) Plot of optimized annealing time T* versus the number of spins involved in the Ising Hamiltonian HSCP corresponding to randomly generated SCP instances according to Algorithm 1. We also provide on the bottom plot the number of instances for each M.
Mentions: In general w(S) increases as S increases, leading to a decrease in R. We numerically investigate this with an Ising system of Nā€‰=ā€‰17 spins generated from an SCP instance via the construction in Theorem 1. We plot the annealing time T versus S in Fig. 4a. For each SCP instance with the number of spin M we compute the optimal S* such that is the optimized runtime (Fig. 4a). We further explore how the optimal runtime T* scales as a function of the number of spins M. As shown in Fig. 4b, a linear fit on a semilog plot shows that roughly .

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.