Embedding

Provides functions that map binary quadratic models and samples between a source graph and a target graph.

Example

A sampler may not natively support a given problem graph. For example, the D-Wave system does not natively support \(K_3\) graphs. The Boolean AND gate (\(x_3 \Leftrightarrow x_1 \wedge x_2\) where \(x_3\) is the AND gate’s output and \(x_1, x_2\) the inputs) may be represented as penalty model

\[x_1 x_2 - 2(x_1+x_2)x_3 +3x_3.\]

This penalty model can in turn be represented as the QUBO,

\[E(a_i, b_{i,j}; x_i) = 3x_3 + x_1x_2 - 2x_1x_3 - 2x_2x_3,\]

which is a fully connected \(K_3\) graph.

Sampling this problem on a D-Wave system, therefore, requires minor-embedding. Embedding in this case is accomplished by an edge contraction operation on the target graph: two nodes (qubits) are chained to represent a single node.

Embedding an AND gate represented by a \(K_3\) graph onto the D-Wave system’s graph. The leftmost graph is the source graph, which is the QUBO representing the AND gate; the middle one is the target graph, representing the D-Wave system; and in the rightmost graph, qubits 0 and 4 of the D-Wave system’s graph are chained to represent the single node \(z\) of the source graph.

Functions

embed_bqm(source_bqm, embedding, …[, …])	Embed a binary quadratic model onto a target graph.
embed_ising(souce_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.
iter_unembed(target_samples, embedding[, …])	Yield unembedded samples.
unembed_response(target_response, embedding, …)	Unembed the response.
chain_break_frequency(samples, embedding)	Determine the frequency of chain breaks in the given samples.

Chain-Break Resolution

Chain-break-resolution generators available to iter_unembed().

Chain-break-resolution generators enable iter_unembed() to use different techniques of resolving chain breaks without keeping large numbers of samples in memory. Each generator yields zero or more unembedded samples.

Generators

discard(sample, embedding)	Discard the sample if a chain is broken.
majority_vote(sample, embedding)	Determine the sample values for chains by majority vote.
weighted_random(sample, embedding)	Determine the sample values of chains by weighed random choice.

Callable Objects

MinimizeEnergy([linear, quadratic])

Determine the sample values of broken chains by minimizing local energy.