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.


Example of converting an SCP instance to Ising Hamiltonian.(a) The SCP instance. Here  and . The solution is the set . The circles represent the covering set elements S and the squares are the ground elements U. (b) The interaction of Ising instance HSCP converted from the SCP instance in (a). Every node corresponds to a qubit. The si’s are the output bits that correspond to the covering set elements S. The others are auxiliary variables. Every edge represents an interaction term between the corresponding spins. Here we do not show the 1-local terms in our construction of HSCP (for example the terms in Htarg for enforcing the minimization of the target function). The bold dashed black line exemplifies the edges between the  nodes and the si nodes, which come from the constraints  and  for each pair  that covers ck. Each of the inequality constraints is enforced by a H≤ term in (6). The bold triangle exemplifies the H∨ constraints in (6) that are used to enforce the logical relationship between the  variables and the auxiliary variables as shown in (7). The areas marked by ,  etc outline the structure of the Ising Hamiltonian that is relevant in the discussion of hardware embedding.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f2: Example of converting an SCP instance to Ising Hamiltonian.(a) The SCP instance. Here and . The solution is the set . The circles represent the covering set elements S and the squares are the ground elements U. (b) The interaction of Ising instance HSCP converted from the SCP instance in (a). Every node corresponds to a qubit. The si’s are the output bits that correspond to the covering set elements S. The others are auxiliary variables. Every edge represents an interaction term between the corresponding spins. Here we do not show the 1-local terms in our construction of HSCP (for example the terms in Htarg for enforcing the minimization of the target function). The bold dashed black line exemplifies the edges between the nodes and the si nodes, which come from the constraints and for each pair that covers ck. Each of the inequality constraints is enforced by a H≤ term in (6). The bold triangle exemplifies the H∨ constraints in (6) that are used to enforce the logical relationship between the variables and the auxiliary variables as shown in (7). The areas marked by , etc outline the structure of the Ising Hamiltonian that is relevant in the discussion of hardware embedding.

Mentions: Consider the SCP instance shown in Fig. 2a. With the mapping presented in Theorem 1, we arrive at an Ising instance ISING (h, J) where α = 1/4 in (10) and h, J are presented in Supplementary Material Details of the example SCP instance. The ground state subspace of the Hamiltonian in (2) with hi and Jij coefficients defined above, restricted to the si elements is spanned by . This corresponds to A = {f1, f4}, the solution to the SCP instance. Figure 2b illustrates the interaction graph of the spins in the Ising Hamiltonian that corresponds to the SCP instance.


Solving Set Cover with Pairs Problem using Quantum Annealing
Example of converting an SCP instance to Ising Hamiltonian.(a) The SCP instance. Here  and . The solution is the set . The circles represent the covering set elements S and the squares are the ground elements U. (b) The interaction of Ising instance HSCP converted from the SCP instance in (a). Every node corresponds to a qubit. The si’s are the output bits that correspond to the covering set elements S. The others are auxiliary variables. Every edge represents an interaction term between the corresponding spins. Here we do not show the 1-local terms in our construction of HSCP (for example the terms in Htarg for enforcing the minimization of the target function). The bold dashed black line exemplifies the edges between the  nodes and the si nodes, which come from the constraints  and  for each pair  that covers ck. Each of the inequality constraints is enforced by a H≤ term in (6). The bold triangle exemplifies the H∨ constraints in (6) that are used to enforce the logical relationship between the  variables and the auxiliary variables as shown in (7). The areas marked by ,  etc outline the structure of the Ising Hamiltonian that is relevant in the discussion of hardware embedding.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f2: Example of converting an SCP instance to Ising Hamiltonian.(a) The SCP instance. Here and . The solution is the set . The circles represent the covering set elements S and the squares are the ground elements U. (b) The interaction of Ising instance HSCP converted from the SCP instance in (a). Every node corresponds to a qubit. The si’s are the output bits that correspond to the covering set elements S. The others are auxiliary variables. Every edge represents an interaction term between the corresponding spins. Here we do not show the 1-local terms in our construction of HSCP (for example the terms in Htarg for enforcing the minimization of the target function). The bold dashed black line exemplifies the edges between the nodes and the si nodes, which come from the constraints and for each pair that covers ck. Each of the inequality constraints is enforced by a H≤ term in (6). The bold triangle exemplifies the H∨ constraints in (6) that are used to enforce the logical relationship between the variables and the auxiliary variables as shown in (7). The areas marked by , etc outline the structure of the Ising Hamiltonian that is relevant in the discussion of hardware embedding.
Mentions: Consider the SCP instance shown in Fig. 2a. With the mapping presented in Theorem 1, we arrive at an Ising instance ISING (h, J) where α = 1/4 in (10) and h, J are presented in Supplementary Material Details of the example SCP instance. The ground state subspace of the Hamiltonian in (2) with hi and Jij coefficients defined above, restricted to the si elements is spanned by . This corresponds to A = {f1, f4}, the solution to the SCP instance. Figure 2b illustrates the interaction graph of the spins in the Ising Hamiltonian that corresponds to the SCP instance.

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.