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