# 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:

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:

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:

## 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)) # 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, solving on a quantum computer with the default chain strength might 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, 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.