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

Heuristically attempt to find a minor-embedding of source graph S into a target graph T.

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

Utility functions for calculating chain strength.

Examples

This example uses uniform_torque_compensation(), given a prefactor of 2, to calculate a chain strength that EmbeddingComposite then uses.

>>> from functools import partial
>>> from dwave.system import EmbeddingComposite, DWaveSampler
>>> from dwave.embedding.chain_strength import uniform_torque_compensation
...
>>> Q = {(0,0): 1, (1,1): 1, (2,3): 2, (1,2): -2, (0,3): -2}
>>> sampler = EmbeddingComposite(DWaveSampler())
>>> # partial() can be used when the BQM or embedding is not accessible
>>> chain_strength = partial(uniform_torque_compensation, prefactor=2)
>>> sampleset = sampler.sample_qubo(Q, chain_strength=chain_strength, return_embedding=True)
>>> sampleset.info['embedding_context']['chain_strength']
1.224744871391589

`chain_strength.uniform_torque_compensation`(bqm)	Chain strength that attempts to compensate for torque that would break the chain.
`chain_strength.scaled`(bqm[, embedding, ...])	Chain strength that is scaled to the problem bias range.

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)[source]¶

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.