MinorEmbedding¶
To solve an arbitrarily posed binary quadratic problem directly on a DWave system requires mapping,
called minor embedding, to a Chimera graph that represents the system’s quantum processing unit.
This preprocessing can be done by a composed sampler consisting of the
DWaveSampler()
and a composite that performs minorembedding.
(This step is handled automatically by LeapHybridSampler()
and dwavehybrid reference samplers.)
For example, a simple twovariable bqm,
might be embedded to two connected qubits, such as 1929 and 1801 on a DWave 2000Q system:
In the DWave 2000Q Chimera topology, most qubits are conencted to six other qubits, so other valid minorembeddings 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 fullyconected \(K_3\) threevariable 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:
The embedding above derived from the hueristic used by EmbeddingComposite()
on the working graph of a DWave 2000Q selected by DWaveSampler()
:
sampler = EmbeddingComposite(DWaveSampler(solver={'qpu': True}))
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:
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 nonidentical outcomes.
For example, another threevariable \(K_3\) fullyconnected BQM,
can be embedded 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, shown below—solved by bruteforce 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)) # doctest: +SKIP
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, the default chain strength is not always sufficient:
>>> sampleset = sampler.sample(bqm, num_reads=1000) # doctest: +SKIP
>>> print(sampleset) # doctest: +SKIP
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.
For information on handling embedding and chains, see the following documentation:
Boolean AND Gate, MultipleGate Circuit, and Using the Problem Inspector examples
Shows 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.

Provides embedding composites.