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.


Plot of the optimal quantum annealing time T* versus the number of spins involved in the construction of HSCP.Here we fit the logarithm of median T* with a straight line. The size M of our Ising systems ranges from 3 to 19. From the fitting function we observe that the annealing time scales as roughly O(20.31M). 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

f3: Plot of the optimal quantum annealing time T* versus the number of spins involved in the construction of HSCP.Here we fit the logarithm of median T* with a straight line. The size M of our Ising systems ranges from 3 to 19. From the fitting function we observe that the annealing time scales as roughly O(20.31M). We also provide on the bottom plot the number of instances for each M.

Mentions: To obtain the final state where T is some positive integer, we use the ode45 subroutine of MATLAB under default settings to numerically integrate Schrödinger equation to obtain from , and then use as an initial state to obtain in the same fashion, and so on. We define the success probability p as a function of the total annealing time T as where Π is a projector onto the subspace spanned by states with s being a solution of the original SCP instance. Using binary search we determine the minimum time T* to achieve for each instance of SCP. Figure 3 shows the distribution of T* for SCP instances that lead to Ising Hamiltonians HSCP of the same sizes, as well as how the median annealing time scales as a function of number of spins M. Results show that for instances with M up to 19, the median annealing time scales roughly as O(20.31M).


Solving Set Cover with Pairs Problem using Quantum Annealing
Plot of the optimal quantum annealing time T* versus the number of spins involved in the construction of HSCP.Here we fit the logarithm of median T* with a straight line. The size M of our Ising systems ranges from 3 to 19. From the fitting function we observe that the annealing time scales as roughly O(20.31M). 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

f3: Plot of the optimal quantum annealing time T* versus the number of spins involved in the construction of HSCP.Here we fit the logarithm of median T* with a straight line. The size M of our Ising systems ranges from 3 to 19. From the fitting function we observe that the annealing time scales as roughly O(20.31M). We also provide on the bottom plot the number of instances for each M.
Mentions: To obtain the final state where T is some positive integer, we use the ode45 subroutine of MATLAB under default settings to numerically integrate Schrödinger equation to obtain from , and then use as an initial state to obtain in the same fashion, and so on. We define the success probability p as a function of the total annealing time T as where Π is a projector onto the subspace spanned by states with s being a solution of the original SCP instance. Using binary search we determine the minimum time T* to achieve for each instance of SCP. Figure 3 shows the distribution of T* for SCP instances that lead to Ising Hamiltonians HSCP of the same sizes, as well as how the median annealing time scales as a function of number of spins M. Results show that for instances with M up to 19, the median annealing time scales roughly as O(20.31M).

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.