Embedding

Provides functions that map binary quadratic models and samples between a source graph and a target graph.

Example

A sampler may not natively support a given problem graph. For example, the D-Wave system does not natively support \(K_3\) graphs. The Boolean AND gate (\(x_3 \Leftrightarrow x_1 \wedge x_2\) where \(x_3\) is the AND gate’s output and \(x_1, x_2\) the inputs) may be represented as penalty model

\[x_1 x_2 - 2(x_1+x_2)x_3 +3x_3.\]

This penalty model can in turn be represented as the QUBO,

\[E(a_i, b_{i,j}; x_i) = 3x_3 + x_1x_2 - 2x_1x_3 - 2x_2x_3,\]

which is a fully connected \(K_3\) graph.

Sampling this problem on a D-Wave system, therefore, requires minor-embedding. Embedding in this case is accomplished by an edge contraction operation on the target graph: two nodes (qubits) are chained to represent a single node.

Embedding a :math:`K_3` graph onto the D-Wave system's graph.

Embedding an AND gate represented by a \(K_3\) graph onto the D-Wave system’s graph. The leftmost graph is the source graph, which is the QUBO representing the AND gate; the middle one is the target graph, representing the D-Wave system; and in the rightmost graph, qubits 0 and 4 of the D-Wave system’s graph are chained to represent the single node \(z\) of the source graph.

Generating Embeddings

MinorMiner

minorminer is a heuristic tool for minor embedding: given a minor and target graph, it tries to find a mapping that embeds the minor into the target.

minorminer.find_embedding(S, T, **params) Heuristically attempt to find a minor-embedding of a graph representing an Ising/QUBO into a target graph.

Chimera

Functionality for minor-embedding in Chimera-structured target graphs.

chimera.find_clique_embedding(k, m[, n, t, …]) Find an embedding for a clique in a Chimera graph.
chimera.find_biclique_embedding(a, b, m[, …]) Find an embedding for a biclique in a Chimera graph.
chimera.find_grid_embedding(dim, m[, n, t]) Find an embedding for a grid in a Chimera graph.

Pegasus

Functionality for minor-embedding in Pegasus-structured target graphs.

pegasus.find_clique_embedding(k[, m, …]) Find an embedding of a k-sized clique on a Pegasus graph (target_graph).

Embedding Utilities

Utilities

embed_bqm(source_bqm, embedding, …[, …]) Embed a binary quadratic model onto a target graph.
embed_ising(source_h, source_J, embedding, …) Embed an Ising problem onto a target graph.
embed_qubo(source_Q, embedding, target_adjacency) Embed a QUBO onto a target graph.
unembed_sampleset(target_sampleset, …[, …]) Unembed the samples set.
chain_break_frequency(samples_like, embedding) Determine the frequency of chain breaks in the given samples.

Diagnostics

diagnose_embedding(emb, source, target) A detailed diagnostic for minor embeddings.
is_valid_embedding(emb, source, target) A simple (bool) diagnostic for minor embeddings.
verify_embedding(emb, source, target[, …]) A simple (exception-raising) diagnostic for minor embeddings.

Chain-Break Resolution

Generators

chain_breaks.discard(samples, chains) Discard broken chains.
chain_breaks.majority_vote(samples, chains) Use the most common element in broken chains.
chain_breaks.weighted_random(samples, chains) Determine the sample values of chains by weighed random choice.

Callable Objects

chain_breaks.MinimizeEnergy(bqm, embedding) Determine the sample values of broken chains by minimizing local energy.

Exceptions

exceptions.EmbeddingError Base class for all embedding exceptions.
exceptions.MissingChainError(snode) Raised if a node in the source graph has no associated chain.
exceptions.ChainOverlapError(tnode, snode0, …) Raised if two source nodes have an overlapping chain.
exceptions.DisconnectedChainError(snode) Raised if a chain is not connected in the target graph.
exceptions.InvalidNodeError(snode, tnode) Raised if a chain contains a node not in the target graph.
exceptions.MissingEdgeError(snode0, snode1) Raised when two source nodes sharing an edge to not have a corresponding edge between their chains.