Python Interface

General Embedding

find_embedding(S, T, **params)

Heuristically attempt to find a minor-embedding of a graph representing an Ising/QUBO into a target graph.

Args:

S: an iterable of label pairs representing the edges in the source graph, or a NetworkX Graph

T: an iterable of label pairs representing the edges in the target graph, or a NetworkX Graph

**params (optional): see below

Returns:

When return_overlap = False (the default), returns a dict that maps labels in S to lists of labels in T.
    If the heuristic fails to find an embedding, an empty dictionary is returned

When return_overlap = True, returns a tuple consisting of a dict that maps labels in S to lists of
    labels in T and a bool indicating whether or not a valid embedding was found

When interrupted by Ctrl-C, returns the best embedding found so far

Note that failure to return an embedding does not prove that no embedding exists

Optional parameters:

max_no_improvement: Maximum number of failed iterations to improve the
    current solution, where each iteration attempts to find an embedding
    for each variable of S such that it is adjacent to all its
    neighbours. Integer >= 0 (default = 10)

random_seed: Seed for the random number generator that find_embedding
    uses. Integer >=0 (default is randomly set)

timeout: Algorithm gives up after timeout seconds. Number >= 0 (default
    is approximately 1000 seconds, stored as a double)

max_beta: Qubits are assigned weight according to a formula (beta^n)
    where n is the number of chains containint that qubit.  This value
    should never be less than or equal to 1. (default is effectively
    infinite, stored as a double)

tries: Number of restart attempts before the algorithm stops. On
    D-WAVE 2000Q, a typical restart takes between 1 and 60 seconds.
    Integer >= 0 (default = 10)

inner_rounds: the algorithm takes at most this many iterations between
    restart attempts; restart attempts are typically terminated due to
    max_no_improvement. Integer >= 0 (default = effectively infinite)

chainlength_patience: Maximum number of failed iterations to improve
    chainlengths in the current solution, where each iteration attempts
    to find an embedding for each variable of S such that it is adjacent
    to all its neighbours. Integer >= 0 (default = 10)

max_fill: Restricts the number of chains that can simultaneously
    incorporate the same qubit during the search. Integer >= 0, values
    above 63 are treated as 63 (default = effectively infinite)

threads: Maximum number of threads to use. Note that the
    parallelization is only advantageous where the expected degree of
    variables is significantly greater than the number of threads.
    Integer >= 1 (default = 1)

return_overlap: This function returns an embedding whether or not qubits
    are used by multiple variables. Set this value to 1 to capture both
    return values to determine whether or not the returned embedding is
    valid. Logical 0/1 integer (default = 0)

skip_initialization: Skip the initialization pass. Note that this only
    works if the chains passed in through initial_chains and
    fixed_chains are semi-valid. A semi-valid embedding is a collection
    of chains such that every adjacent pair of variables (u,v) has a
    coupler (p,q) in the hardware graph where p is in chain(u) and q is
    in chain(v). This can be used on a valid embedding to immediately
    skip to the chainlength improvement phase. Another good source of
    semi-valid embeddings is the output of this function with the
    return_overlap parameter enabled. Logical 0/1 integer (default = 0)

verbose: Level of output verbosity. Integer < 4 (default = 0).
    When set to 0, the output is quiet until the final result.
    When set to 1, output looks like this:

        initialized
        max qubit fill 3; num maxfull qubits=3
        embedding trial 1
        max qubit fill 2; num maxfull qubits=21
        embedding trial 2
        embedding trial 3
        embedding trial 4
        embedding trial 5
        embedding found.
        max chain length 4; num max chains=1
        reducing chain lengths
        max chain length 3; num max chains=5

    When set to 2, outputs the information for lower levels and also
        reports progress on minor statistics (when searching for an
        embedding, this is when the number of maxfull qubits decreases;
        when improving, this is when the number of max chains decreases)
    When set to 3, report before each before each pass. Look here when
        tweaking `tries`, `inner_rounds`, and `chainlength_patience`
    When set to 4, report additional debugging information. By default,
        this package is built without this functionality. In the c++
        headers, this is controlled by the CPPDEBUG flag
    Detailed explanation of the output information:
        max qubit fill: largest number of variables represented in a qubit
        num maxfull: the number of qubits that has max overfill
        max chain length: largest number of qubits representing a single variable
        num max chains: the number of variables that has max chain size

interactive: If `logging` is None or False, the verbose output will be printed
    to stdout/stderr as appropriate, and keyboard interrupts will stop the embedding
    process and the current state will be returned to the user.  Otherwise, output
    will be directed to the logger `logging.getLogger(minorminer.__name__)` and
    keyboard interrupts will be propagated back to the user.  Errors will use
    `logger.error()`, verbosity levels 1 through 3 will use `logger.info()` and level
    4 will use `logger.debug()`.  bool, default False

initial_chains: Initial chains inserted into an embedding before
    fixed_chains are placed, which occurs before the initialization
    pass. These can be used to restart the algorithm in a similar state
    to a previous embedding; for example, to improve chainlength of a
    valid embedding or to reduce overlap in a semi-valid embedding (see
    skip_initialization) previously returned by the algorithm. Missing
    or empty entries are ignored. A dictionary, where initial_chains[i]
    is a list of qubit labels.

fixed_chains: Fixed chains inserted into an embedding before the
    initialization pass. As the algorithm proceeds, these chains are not
    allowed to change, and the qubits used by these chains are not used by
    other chains. Missing or empty entries are ignored. A dictionary, where
    fixed_chains[i] is a list of qubit labels.

restrict_chains: Throughout the algorithm, we maintain the condition
    that chain[i] is a subset of restrict_chains[i] for each i, except
    those with missing or empty entries. A dictionary, where
    restrict_chains[i] is a list of qubit labels.

suspend_chains: This is a metafeature that is only implemented in the Python
    interface.  suspend_chains[i] is an iterable of iterables; for example
        suspend_chains[i] = [blob_1, blob_2],
    with each blob_j an iterable of target node labels.
    this enforces the following:
        for each suspended variable i,
            for each blob_j in the suspension of i,
                at least one qubit from blob_j will be contained in the
                chain for i

    we accomplish this trhough the following problem transformation
    for each iterable blob_j in suspend_chains[i],
        * add an auxiliary node Zij to both source and target graphs
        * set fixed_chains[Zij] = [Zij]
        * add the edge (i,Zij) to the source graph
        * add the edges (q,Zij) to the target graph for each q in blob_j

Clique Embedding

class busgraph_cache
find_clique_embedding()

Finds a clique embedding in the graph g using a polynomial-time algorithm.

Inputs:

g: either a dwave_networkx.chimera_graph or dwave_networkx.pegasus_graph nodes: a number (indicating the size of the desired clique) or an

iterable (specifying the node labels of the desired clique)
use_cache: bool, default True – whether or not to compute / restore a
cache of clique embeddings for g. Note that this function only uses the filesystem cache, and does not maintain the cache in memory. If many (or even several) embeddings are desired in a single session, it is recommended to use busgraph_cache
Returns:
dict mapping node labels (either nodes, or range(nodes)) to chains
of a clique embedding
Return type:emb

Note: due to internal optimizations, not all chimera graphs are supported by this code. Specifically, the graphs

dwave_networkx.chimera_graph(m, n, t)

are only supported for t <= 8. Thus, we support current D-Wave products (which have t = 4) but not all graphs. For graphs with t > 8, use the legacy chimera-embedding package.

Note: when the cache is used, clique embeddings of all sizes are computed and cached. This takes somewhat longer than a single embedding, but tends to pay off after a fairly small number of calls. An exceptional use case is when there are a large number of missing internal couplers, where the result is nondeterministic – avoiding the cache in this case may be preferable.

Layout & Placement Embedding

class Layout(G, layout=None, dim=None, center=None, scale=None, pack_components=True, **kwargs)[source]
p_norm(G, p=2, starting_layout=None, G_distances=None, dim=None, center=None, scale=None, **kwargs)[source]

Embeds a graph in R^d with the p-norm and minimizes a Kamada-Kawai-esque objective function to achieve an embedding with low distortion. This computes a layout where the graph distance and the p-distance are very close to each other.

Parameters:
  • G (NetworkX graph) – The graph you want to compute the layout for.
  • p (int (default 2)) – The order of the p-norm to use as a metric.
  • starting_layout (dict (default None)) – A mapping from the vertices of G to points in R^d. If None, nx.spectral_layout is used if possible, otherwise nx.random_layout is used.
  • G_distances (dict (default None)) – A dictionary of dictionaries representing distances from every vertex in G to every other vertex in G. If None, it is computed.
  • dim (int (default None)) – The desired dimension of the layout, R^dim. If None, check the dimension of center, if center is None, set dim to 2.
  • center (tuple (default None)) – The desired center point of the layout. If None, it is set as the origin in R^dim space.
  • scale (float (default None)) – The desired scale of the layout; i.e. the layout is in [center - scale, center + scale]^d space. If None, do not set a scale.
Returns:

layout – A mapping from vertices of G (keys) to points in R^d (values).

Return type:

dict

dnx_layout(G, dim=None, center=None, scale=None, **kwargs)[source]

The Chimera or Pegasus layout from dwave_networkx centerd at the origin with scale a function of the number of rows or columns. Note: As per the implementation of dnx.*_layout, if dim > 2, coordinates beyond the second are 0.

Parameters:
  • G (NetworkX graph) – The graph you want to compute the layout for.
  • dim (int (default None)) – The desired dimension of the layout, R^dim. If None, check the dimension of center, if center is None, set dim to 2.
  • center (tuple (default None)) – The desired center point of the layout. If None, it is set as the origin in R^dim space.
  • scale (float (default None)) – The desired scale of the layout; i.e. the layout is in [center - scale, center + scale]^d space. If None, it is set as max(n, m)/2, where n, m are the number of columns, rows respectively in G.
Returns:

layout – A mapping from vertices of G (keys) to points in R^d (values).

Return type:

dict

class Placement(S_layout, T_layout, placement=None, scale_ratio=None, **kwargs)[source]
intersection(S_layout, T_layout, **kwargs)[source]

Map each vertex of S to its nearest row/column intersection qubit in T (T must be a D-Wave hardware graph). Note: This will modifiy S_layout.

Parameters:
  • S_layout (layout.Layout) – A layout for S; i.e. a map from S to R^d.
  • T_layout (layout.Layout) – A layout for T; i.e. a map from T to R^d.
  • scale_ratio (float (default None)) – If None, S_layout is not scaled. Otherwise, S_layout is scaled to scale_ratio*T_layout.scale.
Returns:

placement – A mapping from vertices of S (keys) to vertices of T (values).

Return type:

dict

closest(S_layout, T_layout, subset_size=(1, 1), num_neighbors=1, **kwargs)[source]

Maps vertices of S to the closest vertices of T as given by S_layout and T_layout. i.e. For each vertex u in S_layout and each vertex v in T_layout, map u to the v with minimum Euclidean distance (||u - v||_2).

Parameters:
  • S_layout (layout.Layout) – A layout for S; i.e. a map from S to R^d.
  • T_layout (layout.Layout) – A layout for T; i.e. a map from T to R^d.
  • subset_size (tuple (default (1, 1))) – A lower (subset_size[0]) and upper (subset_size[1]) bound on the size of subets of T that will be considered when mapping vertices of S.
  • num_neighbors (int (default 1)) – The number of closest neighbors to query from the KDTree–the neighbor with minimium overlap is chosen. Increasing this reduces overlap, but increases runtime.
Returns:

placement – A mapping from vertices of S (keys) to subsets of vertices of T (values).

Return type:

dict