Python Interface¶

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)

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
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
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

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. 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