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 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.
`pegasus.find_biclique_embedding`(a, b[, m, ...])	Find an embedding for a biclique in a Pegasus graph.

Zephyr#

Minor-embedding in Zephyr-structured target graphs.

`zephyr.find_clique_embedding`(k[, m, ...])	Find an embedding for a clique in a Zephyr graph.
`zephyr.find_biclique_embedding`(a, b[, m, ...])	Find an embedding for a biclique in a Zephyr 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.