D-Wave Embedding Utilities¶
This package provides functions that map samples between a source graph and a target graph.
Terminology¶
model - A collection of variables with associated linear and quadratic biases. Sometimes referred to in other projects as a problem. In this project all models are expected to be spin-valued - that is the variables in the model can be -1 or 1.
graph - A collection of nodes and edges. A graph can be derived from a model; a node for each variable and an edge for each pair of variables with a non-zero quadratic bias.
source - The model or induced graph that we wish to embed. Sometimes referred to in other projects as the logical graph/model.
target - Embedding attempts to create a target model from a target graph. The process of embedding takes a source model, derives the source graph, maps the source graph to the target graph, then derives the target model. Sometimes referred to in other projects at the embedded graph/model.
chain - A collection of nodes or variables in the target graph/model that we want to act like a single node/variable.
chain strength - The magnitude of the negative quadratic bias applied between variables within a chain.
Examples
Imagine that we have a sampler which is structured as a 4-cycle graph.
import networkx as nx
target_graph = nx.cycle_graph(4)
# target_graph = {0: {1, 3}, 1: {0, 2}, 2: {1, 3}, 3: {0, 2}} # equivalent
We have a model on a 3-cycle that we wish to embed.
source_linear = {'a': 0., 'b': 0., 'c': 0.}
source_quadratic = {('a', 'b'): 1., ('b', 'c'): 1., ('a', 'c'): 1.}
Finally, we have an embedding that maps a 3-cycle to a 4-cycle. In this case we want variables 1, 2 in the target to behave as a single variable.
embedding = {'a': {0}, 'b': {1, 2}, 'c': {3}}
To get the target model, use the embed_ising()
function.
target_linear, target_quadratic, chain_quadratic = embed_ising(
source_linear, source_quadratic, embedding, target_graph)
Say that we sample from the target model using some sampler, we can then
umembed the samples using unembed_samples()
.
samples = {0: -1, 1: -1, 2: 1, 3: 1}
source_samples = unembed_samples(samples, embedding)
Functions¶
-
embed_ising
(source_linear, source_quadratic, embedding, target_adjacency, chain_strength=1.0)[source]¶ Embeds a logical Ising model onto another graph via an embedding.
Parameters: - source_linear (dict) – The linear biases to be embedded. Should be a dict of the form {v: bias, …} where v is a variable in the source model and bias is the linear bias associated with v.
- source_quadratic (dict) – The quadratic biases to be embedded. Should be a dict of the form {(u, v): bias, …} where u, v are variables in the source model and bias is the quadratic bias associated with (u, v).
- embedding (dict) – The mapping from the source graph to the target graph. Should be of the form {v: {s, …}, …} where v is a variable in the source model and s is a variable in the target model.
- target_adjacency (dict/
networkx.Graph
) – The adjacency dict of the target graph. Should be a dict of the form {s: Ns, …} where s is a variable in the target graph and Ns is the set of neighbours of s. - chain_strength (float, optional) – The quadratic bias that should be used to create chains.
Returns: A 3-tuple containing:
dict: The linear biases of the target problem. In the form {s: bias, …} where s is a node in the target graph and bias is the associated linear bias.
dict: The quadratic biases of the target problem. A dict of the form {(s, t): bias, …} where (s, t) is an edge in the target graph and bias is the associated quadratic bias.
dict: The quadratic biases that induce the variables in the target problem to act as one. A dict of the form {(s, t): -chain_strength, …} which is the quadratic biases associated with the chains.
Return type: Examples
>>> source_linear = {'a': 1, 'b': 1} >>> source_quadratic = {('a', 'b'): -1} >>> embedding = {'a': [0, 1], 'b': [2]} >>> target_adjacency = {0: {1, 2}, 1: {0, 2}, 2: {0, 1}} >>> target_linear, target_quadratic, chain_quadratic = embed_ising( ... source_linear, source_quadratic, embedding, target_adjacency) >>> target_linear {0: 0.5, 1: 0.5, 2: 1.0} >>> target_quadratic {(0, 2): -0.5, (1, 2): -0.5} >>> chain_quadratic {(0, 1): -1.0}
-
target_to_source
(target_adjacency, embedding)[source]¶ Derive the source adjacency from an embedding and target adjacency.
Parameters: - target_adjacency (dict/
networkx.Graph
) – A dict of the form {v: Nv, …} where v is a node in the target graph and Nv is the neighbors of v as an iterable. This can also be a networkx graph. - embedding (dict) – A mapping from a source graph to a target graph.
Returns: The adjacency of the source graph.
Return type: Raises: ValueError
– If any node in the target_adjacency is assigned more than one node in the source graph by embedding.- target_adjacency (dict/
-
chain_break_frequency
(samples, embedding)[source]¶ Determines the frequency of chain breaks in the given samples.
Parameters: - samples (iterable) – An iterable of samples where each sample is a dict of the form {v: val, …} where v is a variable in the target graph and val is the associated value as determined by a binary quadratic model sampler.
- embedding (dict) – The mapping from the source graph to the target graph. Should be of the form {v: {s, …}, …} where v is a variable in the source model and s is a variable in the target model.
Returns: The frequency of chain breaks in the form {v: f, …} where v is a variable in the source graph and frequency is the fraction of chains that were broken as a float.
Return type:
-
edgelist_to_adjacency
(edgelist)[source]¶ Converts an iterator of edges to an adjacency dict.
Parameters: edgelist (iterable) – An iterator over 2-tuples where each 2-tuple is an edge. Returns: The adjacency dict. A dict of the form {v: Nv, …} where v is a node in a graph and Nv is the neighbors of v as an set. Return type: dict
-
chain_to_quadratic
(chain, target_adjacency, chain_strength)[source]¶ Determine the quadratic biases that induce the given chain.
Parameters: - chain (set/list/tuple) – The variables that make up a chain.
- target_adjacency (dict/
networkx.Graph
) – The adjacency dict of the target graph. Should be a dict of the form {s: Ns, …} where s is a variable in the target graph and Ns is the set of neighbours of s. - chain_strength (float) – The quadratic bias that should be used to create chains.
Returns: The quadratic biases that induce the given chain.
Return type: Examples
>>> chain = {1, 2} >>> target_adjacency = {0: {1, 2}, 1: {0, 2}, 2: {0, 1}} >>> chain_to_quadratic(chain, target_adjacency, 1) {(1, 2): -1}
-
unembed_samples
(samples, embedding, chain_break_method=None)[source]¶ Return samples over the variables in the source graph.
Parameters: - samples (iterable) – An iterable of samples where each sample is a dict of the form {v: val, …} where v is a variable in the target model and val is the associated value as determined by a binary quadratic model sampler.
- embedding (dict) – The mapping from the source graph to the target graph. Should be of the form {v: {s, …}, …} where v is a node in the source graph and s is a node in the target graph.
- chain_break_method (function, optional) – The method used to resolve chain breaks. Default is :method:`majority_vote`.
Returns: A list of unembedded samples. Each sample is a dict of the form {v: val, …} where v is a variable in the source graph and val is the value associated with the variable.
Return type: list
Chain Break Methods¶
-
discard
(sample, embedding)[source]¶ Discards the sample if broken.
Parameters: - sample (dict) – A sample of the form {v: val, …} where v is a variable in the target graph and val is the associated value as determined by a binary quadratic model sampler.
- embedding (dict) – The mapping from the source graph to the target graph. Should be of the form {v: {s, …}, …} where v is a node in the source graph and s is a node in the target graph.
Yields: dict – The unembedded sample is no chains were broken.
-
majority_vote
(sample, embedding)[source]¶ Determines the sample values by majority vote.
Parameters: - sample (dict) – A sample of the form {v: val, …} where v is a variable in the target graph and val is the associated value as determined by a binary quadratic model sampler.
- embedding (dict) – The mapping from the source graph to the target graph. Should be of the form {v: {s, …}, …} where v is a node in the source graph and s is a node in the target graph.
Yields: dict – The unembedded sample. When there is a chain break, the value is chosen to match the most common value in the chain.
-
weighted_random
(sample, embedding)[source]¶ Determines the sample values by weighed random choice.
Parameters: - sample (dict) – A sample of the form {v: val, …} where v is a variable in the target graph and val is the associated value as determined by a binary quadratic model sampler.
- embedding (dict) – The mapping from the source graph to the target graph. Should be of the form {v: {s, …}, …} where v is a node in the source graph and s is a node in the target graph.
Yields: dict – The unembedded sample. When there is a chain break, the value is chosen randomly, weighted by the frequency of the values within the chain.