dimod.embed_qubo

embed_qubo(source_Q, embedding, target_adjacency, chain_strength=1.0)

Embed a QUBO onto a target graph.

Parameters:

• source_Q (dict[(variable, variable), bias]) – Coefficients of a quadratic unconstrained binary optimization (QUBO) model.
• 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.
• target_adjacency (dict/networkx.Graph) – Adjacency of the target graph as a dict of form {t: Nt, …}, where t is a target-graph variable and Nt is its set of neighbours.
• chain_strength (float, optional) – Magnitude of the quadratic bias (in SPIN-space) applied between variables to form a chain. Note that the energy penalty of chain breaks is 2 * chain_strength.

Returns:

Quadratic biases of the target QUBO.

Return type:

dict[(variable, variable), bias]

Examples

This example embeds a square source graph onto fully connected \(K_5\) graph. Embedding is accomplished by an edge deletion operation on the target graph: target-node 0 is not used.

>>> import dimod
>>> import networkx as nx
>>> # QUBO problem for a square graph
>>> Q = {(1, 1): -4.0, (1, 2): 4.0, (2, 2): -4.0, (2, 3): 4.0,
...      (3, 3): -4.0, (3, 4): 4.0, (4, 1): 4.0, (4, 4): -4.0}
>>> # Target graph is a fully connected k5 graph
>>> K_5 = nx.complete_graph(5)
>>> 0 in K_5
True
>>> # Embedding from source to target graph
>>> embedding = {1: {4}, 2: {3}, 3: {1}, 4: {2}}
>>> # Embed the QUBO
>>> target_Q = dimod.embed_qubo(Q, embedding, K_5)
>>> (0, 0) in target_Q
False
>>> target_Q     
{(1, 1): -4.0,
 (1, 2): 4.0,
 (2, 2): -4.0,
 (2, 4): 4.0,
 (3, 1): 4.0,
 (3, 3): -4.0,
 (4, 3): 4.0,
 (4, 4): -4.0}

This example embeds a square graph onto the target graph of a dimod reference structured sampler, StructureComposite, using the dimod reference ExactSolver sampler with a fully connected \(K_5\) graph specified.

>>> import dimod
>>> import networkx as nx
>>> # QUBO problem for a square graph
>>> Q = {(1, 1): -4.0, (1, 2): 4.0, (2, 2): -4.0, (2, 3): 4.0,
...      (3, 3): -4.0, (3, 4): 4.0, (4, 1): 4.0, (4, 4): -4.0}
>>> # Structured dimod sampler with a structure defined by a K5 graph
>>> sampler = dimod.StructureComposite(dimod.ExactSolver(), list(K_5.nodes), list(K_5.edges))
>>> sampler.adjacency      
{0: {1, 2, 3, 4},
 1: {0, 2, 3, 4},
 2: {0, 1, 3, 4},
 3: {0, 1, 2, 4},
 4: {0, 1, 2, 3}}
>>> # Embedding from source to target graph
>>> embedding = {0: {4}, 1: {3}, 2: {1}, 3: {2}}
>>> # Embed the QUBO
>>> target_Q = dimod.embed_qubo(Q, embedding, sampler.adjacency)
>>> # Sample
>>> response = sampler.sample_qubo(target_Q)
>>> for datum in response.data():   
...     print(datum)
...
Sample(sample={1: 0, 2: 1, 3: 1, 4: 0}, energy=-8.0)
Sample(sample={1: 1, 2: 0, 3: 0, 4: 1}, energy=-8.0)
Sample(sample={1: 1, 2: 0, 3: 0, 4: 0}, energy=-4.0)
Sample(sample={1: 1, 2: 1, 3: 0, 4: 0}, energy=-4.0)
Sample(sample={1: 0, 2: 1, 3: 0, 4: 0}, energy=-4.0)
Sample(sample={1: 1, 2: 1, 3: 1, 4: 0}, energy=-4.0)
>>> # Snipped above response for brevity