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.


Related in: MedlinePlus

The Chimera graph that represents the qubit connectivity of D-Wave hardware.(a) Example of a 3 × 3 grid of K4,4 cells, denoted as F(3, 3, 4). (b) Labelling of nodes within a particular cell on the a-th row and b-th column. Here we use the cell on the 2nd row and 3rd column as an example.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f1: The Chimera graph that represents the qubit connectivity of D-Wave hardware.(a) Example of a 3 × 3 grid of K4,4 cells, denoted as F(3, 3, 4). (b) Labelling of nodes within a particular cell on the a-th row and b-th column. Here we use the cell on the 2nd row and 3rd column as an example.

Mentions: Here we specifically consider the embedding our construction into a particular type of hardware graphs used by D-Wave devices4465 called the Chimera graphs. The basic components of this graph are 8-spin unit cells6 whose interactions form a K4,4. The K4,4 unit cells are tiled together and the 4 nodes on the left half of K4,4 are connected to their counterparts in the cells above and below. The 4 nodes on the right half of K4,4 are connected to their counterparts in the cells left and right. Furthermore, we define F(p, q, c) as a Chimera graph formed by an p × q grid of Kc,c cells. Figure 1a shows F(3, 4) as an example. Note that any Km,n with m, n ≤ c can be trivially embedded in F(p, q, c) with any p, q ≥ 1 via subgraph embedding. However, it is not clear a priori how to embed Km,n with m > c or n > c onto a Chimera graph, other than using the general embedding of an (m + n)-node complete graph and consider Km,n as a subgraph. This costs O((m + n)2) qubits in general and one may lose the intuitive structure of a bipartite graph in the embedding. One of the building blocks of our embedding for our Ising Hamiltonian construction (Section Embedding on quantum hardware) is an alternative embedding strategy for mapping any Km,n onto as a graph minor. Our embedding costs O(mn) qubits and preserves the structure of the bipartite graph.


Solving Set Cover with Pairs Problem using Quantum Annealing
The Chimera graph that represents the qubit connectivity of D-Wave hardware.(a) Example of a 3 × 3 grid of K4,4 cells, denoted as F(3, 3, 4). (b) Labelling of nodes within a particular cell on the a-th row and b-th column. Here we use the cell on the 2nd row and 3rd column as an example.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f1: The Chimera graph that represents the qubit connectivity of D-Wave hardware.(a) Example of a 3 × 3 grid of K4,4 cells, denoted as F(3, 3, 4). (b) Labelling of nodes within a particular cell on the a-th row and b-th column. Here we use the cell on the 2nd row and 3rd column as an example.
Mentions: Here we specifically consider the embedding our construction into a particular type of hardware graphs used by D-Wave devices4465 called the Chimera graphs. The basic components of this graph are 8-spin unit cells6 whose interactions form a K4,4. The K4,4 unit cells are tiled together and the 4 nodes on the left half of K4,4 are connected to their counterparts in the cells above and below. The 4 nodes on the right half of K4,4 are connected to their counterparts in the cells left and right. Furthermore, we define F(p, q, c) as a Chimera graph formed by an p × q grid of Kc,c cells. Figure 1a shows F(3, 4) as an example. Note that any Km,n with m, n ≤ c can be trivially embedded in F(p, q, c) with any p, q ≥ 1 via subgraph embedding. However, it is not clear a priori how to embed Km,n with m > c or n > c onto a Chimera graph, other than using the general embedding of an (m + n)-node complete graph and consider Km,n as a subgraph. This costs O((m + n)2) qubits in general and one may lose the intuitive structure of a bipartite graph in the embedding. One of the building blocks of our embedding for our Ising Hamiltonian construction (Section Embedding on quantum hardware) is an alternative embedding strategy for mapping any Km,n onto as a graph minor. Our embedding costs O(mn) qubits and preserves the structure of the bipartite graph.

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.


Related in: MedlinePlus