Embedding

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

For an introduction to minor-embedding, see Minor-Embedding.

Generators

Tools for finding embeddings.

Generic

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

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

Minor-embedding in Pegasus-structured target graphs.

pegasus.find_clique_embedding(k[, m, …])

Find an embedding for a clique in a Pegasus graph.

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 a sample set.

Diagnostics

chain_break_frequency(samples_like, embedding)	Determine the frequency of chain breaks in the given samples.
diagnose_embedding(emb, source, target)	Diagnose a minor embedding.
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

Unembedding samples with broken chains.

Generators

chain_breaks.discard(samples, chains)	Discard broken chains.
chain_breaks.majority_vote(samples, chains)	Unembed samples using the most common value for broken chains.
chain_breaks.weighted_random(samples, chains)	Unembed samples using weighed random choice for broken chains.

Callable Objects

chain_breaks.MinimizeEnergy(bqm, embedding)

Unembed samples by minimizing local energy for broken chains.

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.

Classes

class EmbeddedStructure(target_edges, embedding)

Processes an embedding and a target graph to collect target edges into those within individual chains, and those that connect chains. This is used elsewhere to embed binary quadratic models into the target graph.

Parameters:

• target_edges (iterable[edge]) – An iterable of edges in the target graph. Each edge should be an iterable of 2 hashable objects.
• embedding (dict) – Mapping from source graph to target graph as a dict of form {s: {t, …}, …}, where s is a source-model variable and t is a target-model variable.

This class is a dict, and acts as an immutable duplicate of embedding.