Source code for minorminer.utils.chimera

# Copyright 2018 D-Wave Systems Inc.
#
#    Licensed under the Apache License, Version 2.0 (the "License");
#    you may not use this file except in compliance with the License.
#    You may obtain a copy of the License at
#
#        http://www.apache.org/licenses/LICENSE-2.0
#
#    Unless required by applicable law or agreed to in writing, software
#    distributed under the License is distributed on an "AS IS" BASIS,
#    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#    See the License for the specific language governing permissions and
#    limitations under the License.
#
# ================================================================================================

try:
    import collections.abc as abc
except ImportError:
    import collections as abc

import dwave_networkx as dnx
import networkx as nx


from minorminer.utils.polynomialembedder import processor

__all__ = ['find_clique_embedding',
           'find_biclique_embedding',
           'find_grid_embedding',
           ]


[docs]@nx.utils.decorators.nodes_or_number(0) def find_clique_embedding(k, m, n=None, t=None, target_edges=None): """Find an embedding for a clique in a Chimera graph. Given the node labels or size of a clique (fully connected graph) and size or edges of the target :term:`Chimera` graph, attempts to find an embedding. Args: k (int/iterable): Clique to embed. If k is an integer, generates an embedding for a clique of size k labelled [0,k-1]. If k is an iterable of nodes, generates an embedding for a clique of size len(k) labelled for the given nodes. m (int): Number of rows in the Chimera lattice. n (int, optional, default=m): Number of columns in the Chimera lattice. t (int, optional, default 4): Size of the shore within each Chimera tile. target_edges (iterable[edge]): A list of edges in the target Chimera graph. Nodes are labelled as returned by :func:`~dwave_networkx.chimera_graph`. Returns: dict: An embedding mapping a clique to the Chimera lattice. Examples: The first example finds an embedding for a :math:`K_4` complete graph in a single Chimera unit cell. The second for an alphanumerically labeled :math:`K_3` graph in 4 unit cells. >>> from dwave.embedding.chimera import find_clique_embedding ... >>> embedding = find_clique_embedding(4, 1, 1) >>> embedding # doctest: +SKIP {0: [4, 0], 1: [5, 1], 2: [6, 2], 3: [7, 3]} >>> from dwave.embedding.chimera import find_clique_embedding ... >>> embedding = find_clique_embedding(['a', 'b', 'c'], m=2, n=2, t=4) >>> embedding # doctest: +SKIP {'a': [20, 16], 'b': [21, 17], 'c': [22, 18]} """ import random _, nodes = k m, n, t, target_edges = _chimera_input(m, n, t, target_edges) # Special cases to return optimal embeddings for small k. The general clique embedder uses chains of length # at least 2, whereas cliques of size 1 and 2 can be embedded with single-qubit chains. if len(nodes) == 1: # If k == 1 we simply return a single chain consisting of a randomly sampled qubit. qubits = set().union(*target_edges) qubit = random.choice(tuple(qubits)) embedding = [[qubit]] elif len(nodes) == 2: # If k == 2 we simply return two one-qubit chains that are the endpoints of a randomly sampled coupler. if not isinstance(target_edges, abc.Sequence): target_edges = list(target_edges) edge = random.choice(target_edges) embedding = [[edge[0]], [edge[1]]] else: # General case for k > 2. embedding = processor(target_edges, M=m, N=n, L=t).tightestNativeClique(len(nodes)) if not embedding: raise ValueError("cannot find a K{} embedding for given Chimera lattice".format(len(nodes))) return dict(zip(nodes, embedding))
[docs]@nx.utils.decorators.nodes_or_number(0) @nx.utils.decorators.nodes_or_number(1) def find_biclique_embedding(a, b, m, n=None, t=None, target_edges=None): """Find an embedding for a biclique in a Chimera graph. Given a biclique (a bipartite graph where every vertex in a set in connected to all vertices in the other set) and a target :term:`Chimera` graph size or edges, attempts to find an embedding. Args: a (int/iterable): Left shore of the biclique to embed. If a is an integer, generates an embedding for a biclique with the left shore of size a labelled [0,a-1]. If a is an iterable of nodes, generates an embedding for a biclique with the left shore of size len(a) labelled for the given nodes. b (int/iterable): Right shore of the biclique to embed.If b is an integer, generates an embedding for a biclique with the right shore of size b labelled [0,b-1]. If b is an iterable of nodes, generates an embedding for a biclique with the right shore of size len(b) labelled for the given nodes. m (int): Number of rows in the Chimera lattice. n (int, optional, default=m): Number of columns in the Chimera lattice. t (int, optional, default 4): Size of the shore within each Chimera tile. target_edges (iterable[edge]): A list of edges in the target Chimera graph. Nodes are labelled as returned by :func:`~dwave_networkx.chimera_graph`. Returns: tuple: A 2-tuple containing: dict: An embedding mapping the left shore of the biclique to the Chimera lattice. dict: An embedding mapping the right shore of the biclique to the Chimera lattice. Examples: This example finds an embedding for an alphanumerically labeled biclique in a single Chimera unit cell. >>> from dwave.embedding.chimera import find_biclique_embedding ... >>> left, right = find_biclique_embedding(['a', 'b', 'c'], ['d', 'e'], 1, 1) >>> print(left, right) # doctest: +SKIP {'a': [4], 'b': [5], 'c': [6]} {'d': [0], 'e': [1]} """ _, anodes = a _, bnodes = b m, n, t, target_edges = _chimera_input(m, n, t, target_edges) embedding = processor(target_edges, M=m, N=n, L=t).tightestNativeBiClique(len(anodes), len(bnodes)) if not embedding: raise ValueError("cannot find a K{},{} embedding for given Chimera lattice".format(a, b)) left, right = embedding return dict(zip(anodes, left)), dict(zip(bnodes, right))
[docs]def find_grid_embedding(dim, m, n=None, t=4): """Find an embedding for a grid in a Chimera graph. Given grid dimensions and a target :term:`Chimera` graph size, attempts to find an embedding. Args: dim (iterable[int]): Sizes of each grid dimension. Length can be between 1 and 3. m (int): Number of rows in the Chimera lattice. n (int, optional, default=m): Number of columns in the Chimera lattice. t (int, optional, default 4): Size of the shore within each Chimera tile. Returns: dict: An embedding mapping a grid to the Chimera lattice. Examples: This example finds an embedding for a 2x3 grid in a 12x12 lattice of Chimera unit cells. >>> from dwave.embedding.chimera import find_grid_embedding ... >>> embedding = find_grid_embedding([2, 3], m=12, n=12, t=4) >>> embedding # doctest: +SKIP {(0, 0): [0, 4], (0, 1): [8, 12], (0, 2): [16, 20], (1, 0): [96, 100], (1, 1): [104, 108], (1, 2): [112, 116]} """ m, n, t, target_edges = _chimera_input(m, n, t, None) indexer = dnx.generators.chimera.chimera_coordinates(m, n, t) dim = list(dim) num_dim = len(dim) if num_dim == 1: def _key(row, col, aisle): return row dim.extend([1, 1]) elif num_dim == 2: def _key(row, col, aisle): return row, col dim.append(1) elif num_dim == 3: def _key(row, col, aisle): return row, col, aisle else: raise ValueError("find_grid_embedding supports between one and three dimensions") rows, cols, aisles = dim if rows > m or cols > n or aisles > t: msg = ("the largest grid that find_grid_embedding can fit in a ({}, {}, {}) Chimera-lattice " "is {}x{}x{}; given grid is {}x{}x{}").format(m, n, t, m, n, t, rows, cols, aisles) raise ValueError(msg) return {_key(row, col, aisle): [indexer.chimera_to_linear((row, col, 0, aisle)), indexer.chimera_to_linear((row, col, 1, aisle))] for row in range(dim[0]) for col in range(dim[1]) for aisle in range(dim[2])}
def _chimera_input(m, n=None, t=None, target_edges=None): if not isinstance(m, int): raise TypeError('Chimera lattice parameter m must be an int and >= 1') if m <= 0: raise ValueError('Chimera lattice parameter m must be an int and >= 1') if n is None: n = m else: if not isinstance(n, int): raise TypeError('Chimera lattice parameter n must be an int and >= 1') if n <= 0: raise ValueError('Chimera lattice parameter n must be an int and >= 1') if t is None: t = 4 else: if not isinstance(t, int): raise TypeError('Chimera lattice parameter t must be an int and >= 1') if t <= 0: raise ValueError('Chimera lattice parameter t must be an int and >= 1') if target_edges is None: target_edges = dnx.chimera_graph(m, n, t).edges return m, n, t, target_edges