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