Minor-Embedding¶
To solve an arbitrarily posed binary quadratic problem directly on a D-Wave
system requires mapping, called minor embedding, to the QPU Topology
of the system’s quantum processing unit (QPU). This preprocessing can be done
by a composed sampler consisting of the
DWaveSampler()
and a composite that performs
minor-embedding. (This step is handled automatically by
LeapHybridSampler()
and
dwave-hybrid reference samplers.)
For example, a simple two-variable bqm,
might be embedded to two connected qubits, such as 1929 and 1801 on a D-Wave 2000Q system:

Two-variable problem, shown on the left as a graph, is embedded in two connected qubits on a D-Wave 2000Q, shown on the right against the Chimera topology. Variable \(s_1\), highlighted in dark magenta, is represented by qubit number 1929 and variable \(s_0\) is represented by qubit 1801. (This and similar images in this section are generated by Ocean’s problem inspector tool.¶
In the D-Wave 2000Q Chimera topology, most qubits are conencted to six other qubits, so other valid minor-embeddings might be \(s_1=1929, s_0=1933\) or \(s_0=1801, s_0=1807\) or \(s_0=0, s_1=4\).
Chains¶
Larger problems often require chains because the QPU topology is not fully connected.
For example, a fully-conected \(K_3\) three-variable bqm,
cannot be represented by three qubits in the Chimera topology—a \(K_3\) graph is not native to the Chimera graph. (Look at the Chimera “unit cell” shown in the QPU Topology section and notice there is no way to connect three qubits in a closed loop to form a triangle graph.)
Instead, a variable is represented by a chain of physical qubits:

Three-variable \(K_3\) fully-connected problem, shown on the left as a graph, is embedded in four qubits on a D-Wave 2000Q, shown on the right against the Chimera topology. Variable \(s_0\), highlighted in dark magenta, is represented by two qubits, numbers 251 and 253.¶
The embedding above was derived from the hueristic used by
EmbeddingComposite()
on the working graph of a D-Wave 2000Q selected by DWaveSampler()
:
sampler = EmbeddingComposite(DWaveSampler())
Other qubits might have been chosen; for example,
sampler = FixedEmbeddingComposite(DWaveSampler(solver={'qpu': True}),
embedding={'s0': [0, 4, 7], 's1': [2], 's2': [3, 6]})
intentionally sets the embedding shown below to represent this same \(K_3\) graph:
![]()
Three-variable \(K_3\) fully-connected problem is embedded in six qubits on a D-Wave 2000Q. Variable \(s_0\), highlighted in dark magenta, is represented by three qubits, numbers 0, 4, and 7; Variable \(s_2\) is represented by two qubits, numbers 3 and 6, shown with their connecting edge emphasized (and displaying a solution of \(+1\)).¶
Chain Strength¶
For a chain of qubits to represent a variable, all its constituent qubits must return the same value for a sample. This is accomplished by setting a strong coupling to the edges connecting these qubits. For the solutions shown above to the \(K_3\) problem, the default chain strength achieved identical values and the qubit chains properly represented the variables of the problem.
However, that is not always the case. For the qubits in a chain to be likely to return identical values, the coupling strength for their connecting edges must be strong compared to the coupling with other qubits that influence non-identical outcomes.
For example, another three-variable \(K_3\) fully-connected BQM,
might be embedded on a D-Wave 2000Q QPU by representing one variable with two qubits, for example:
sampler = FixedEmbeddingComposite(DWaveSampler(solver={'qpu': True}),
embedding={'s0': [0, 4], 's1': [2], 's2': [7]})
This BQM has six ground states (best solutions). These are shown below—solved by brute-force stepping through all possible configurations of values for the variables—with lowest energy of -1.0:
>>> bqm = dimod.BQM({}, {('s0', 's1'): -1, ('s0', 's2'): -1, ('s1', 's2'): 1},
... 0, dimod.Vartype.SPIN)
>>> print(dimod.ExactSolver().sample(bqm))
s0 s1 s2 energy num_oc.
0 -1 -1 -1 -1.0 1
2 +1 +1 -1 -1.0 1
3 -1 +1 -1 -1.0 1
5 +1 +1 +1 -1.0 1
6 +1 -1 +1 -1.0 1
7 -1 -1 +1 -1.0 1
1 +1 -1 -1 3.0 1
4 -1 +1 +1 3.0 1
['SPIN', 8 rows, 8 samples, 3 variables]
In this case, solving on a quantum computer with the default chain strength might not always sufficient:
>>> sampleset = sampler.sample(bqm, num_reads=1000)
>>> print(sampleset)
s0 s1 s2 energy num_oc. chain_b.
0 -1 +1 -1 -1.0 85 0.0
1 -1 -1 +1 -1.0 147 0.0
2 +1 +1 -1 -1.0 81 0.333333
3 +1 -1 +1 -1.0 60 0.0
4 +1 +1 +1 -1.0 162 0.0
5 -1 -1 -1 -1.0 128 0.0
6 +1 -1 +1 -1.0 89 0.333333
7 +1 +1 -1 -1.0 248 0.0
['SPIN', 8 rows, 1000 samples, 3 variables]
The solutions of line 2 and 6 above shown a chains broken in a third of the variables, meaning that for variable \(s_0\) the two qubits representing it did not return identical values.
![]()
Three-variable \(K_3\) fully-connected problem is embedded in four qubits on a D-Wave 2000Q using the default chain strength. Variable \(s_0\), highlighted in dark magenta, is represented by two qubits, numbers 0 and 4. The displayed solution has a broken chain: qubit 0 returned a value of \(-1\) (represented by a white dot) while qubit 4 returned a value of \(+1\) (a blue dot). The logical representation of the problem, on the left, shows a half-white, half-blue dot to represent a value based on a broken chain.¶
For information on handling embedding and chains, see the following documentation:
Boolean AND Gate, Multiple-Gate Circuit, and Using the Problem Inspector examples
Show through some simple examples how to embed and set chain strength.
minorminer tool
Is the hueristic used by common Ocean embedding composites.
problem inspector tool
Visualizes embeddings.
dwave-system Composites section
Provides embedding composites
dwave-system Embedding section
Describes chain-related functionality.