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,

\[E(\bf{s}) = - s_0 s_1 \qquad\qquad s_i\in\{-1,+1\}\]

might be embedded to two connected qubits, such as 633 and 3603 on an Advantage system:

Two-variable problem embedded into two qubits.

Two-variable problem, shown on the left as a graph, is embedded in two connected qubits on an Advantage, shown on the right against the Pegasus topology. Variable \(s_0\), highlighted in dark magenta, is represented by qubit number 633 and variable \(s_1\) is represented by qubit 3603. (This and similar images in this section are generated by Ocean’s problem inspector tool.

In the Advantage Pegasus topology, most qubits are connected to fifteen other qubits, so other valid minor-embeddings might be 633 for \(s_0\) and 634 for \(s_1\) or 4628 for \(s_0\) and 1749 for \(s_1\).

Chains

Larger problems often require chains because the QPU topology is not fully connected. For example, a \(K_5\) graph is not native to the Pegasus topology, meaning that the following five-variable bqm with a clique (fully-connected) \(K_5\) graph cannot be represented by five qubits on an Advantage QPU.

>>> import dimod
>>> bqm = dimod.generators.doped(1, 5)
>>> bqm.add_linear_from({v: 1 for v in bqm.variables})

Instead, at least one variable is represented by a chain of physical qubits, as in this minor-embedding:

Five-variable fully-connected problem embedded into six qubits.

Five-variable \(K_5\) fully-connected problem, shown on the left as a graph, is embedded in six qubits on an Advantage, shown on the right against the Pegasus topology. Variable 0, highlighted in dark magenta, is represented by two qubits, 1975 and 4840.

The minor-embedding above was derived from the hueristic used by EmbeddingComposite() on the working graph of an Advantage selected by DWaveSampler():

>>> from dwave.system import DWaveSampler, EmbeddingComposite, FixedEmbeddingComposite
>>> sampler = EmbeddingComposite(DWaveSampler())

Other qubits might have been chosen; for example,

>>> sampler = FixedEmbeddingComposite(DWaveSampler(),
...     embedding={0: [4408, 2437], 1: [4333], 2: [4348], 3: [2497], 4: [2512]})

intentionally sets the embedding shown below to represent this same \(K_5\) graph:

Three-variable fully-connected problem embedded into six qubits.

Five-variable \(K_5\) fully-connected problem, shown on the left as a graph, is embedded in six qubits on an Advantage, shown on the right against the Pegasus topology. Variable 0, highlighted in dark magenta, is represented by two qubits, 4408 and 2437.

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. That is, 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.

The \(K_5\) BQM has ten ground states (best solutions). These are shown below—solved by brute-force stepping through all possible configurations of values for the variables—with ground-state energy -3.0:

>>> print(dimod.ExactSolver().sample(bqm).lowest())
   0  1  2  3  4 energy num_oc.
0 +1 +1 -1 -1 -1   -3.0       1
1 -1 +1 +1 -1 -1   -3.0       1
2 +1 -1 +1 -1 -1   -3.0       1
3 -1 -1 +1 +1 -1   -3.0       1
4 -1 +1 -1 +1 -1   -3.0       1
5 +1 -1 -1 +1 -1   -3.0       1
6 -1 -1 -1 +1 +1   -3.0       1
7 -1 -1 +1 -1 +1   -3.0       1
8 -1 +1 -1 -1 +1   -3.0       1
9 +1 -1 -1 -1 +1   -3.0       1
['SPIN', 10 rows, 10 samples, 5 variables]

These solutions are states in which two variables are assigned one value and the remaining three variables the complementary value; for example two are \(-1\) and three \(+1\) as shown below.

Three-variable fully-connected problem embedded into six qubits.

Ground state of the five-variable \(K_5\) fully-connected problem.

A typical submission of the problem to a quantum computer, using the same minor-embedding as the previous subsection and the default chain strength, returned all the ground states, with these solutions constituting over 90% of the returned samples.

>>> sampleset = sampler.sample(bqm, num_reads=1000)     
>>> print(sampleset.lowest())       
    0  1  2  3  4 energy num_oc. chain_.
0  -1 +1 +1 -1 -1   -3.0      69     0.0
1  +1 -1 -1 +1 -1   -3.0     115     0.0
2  +1 -1 -1 -1 +1   -3.0      95     0.0
3  +1 -1 +1 -1 -1   -3.0      84     0.0
4  -1 -1 -1 +1 +1   -3.0     116     0.0
5  -1 -1 +1 +1 -1   -3.0      99     0.0
6  -1 -1 +1 -1 +1   -3.0      91     0.0
7  +1 +1 -1 -1 -1   -3.0      71     0.0
8  -1 +1 -1 +1 -1   -3.0      98     0.0
9  -1 +1 -1 -1 +1   -3.0      95     0.0
10 +1 -1 -1 +1 -1   -3.0       1     0.2
['SPIN', 11 rows, 934 samples, 5 variables]

The default chain strength is set by the uniform_torque_compensation() function:

>>> print(round(sampleset.info['embedding_context']['chain_strength'], 3))              
2.828

Resubmitting with a much lower chain strength produced less satisfactory results (only ~10% of returned samples are ground states).

>>> sampleset = sampler.sample(bqm, num_reads=1000, chain_strength=1)       
>>> print(sampleset.lowest())           
   0  1  2  3  4 energy num_oc. chain_.
0 -1 +1 +1 -1 -1   -3.0      12     0.0
1 +1 -1 -1 +1 -1   -3.0      13     0.0
2 +1 -1 -1 -1 +1   -3.0      13     0.0
3 +1 -1 +1 -1 -1   -3.0      16     0.0
4 -1 -1 -1 +1 +1   -3.0       6     0.0
5 -1 -1 +1 +1 -1   -3.0      10     0.0
6 -1 -1 +1 -1 +1   -3.0      17     0.0
7 +1 +1 -1 -1 -1   -3.0      17     0.0
8 -1 +1 -1 +1 -1   -3.0      10     0.0
9 -1 +1 -1 -1 +1   -3.0       7     0.0
['SPIN', 10 rows, 121 samples, 5 variables]

Many of the remaining ~90% of returned samples have “broken chains”, meaning qubits of a chain did not have identical values due to insufficiently strong coupling compared to quadratic coefficients of interactions (of the variable the chain represented) with other variables.

Three-variable fully-connected problem embedded into six qubits with a broken chain.

Five-variable \(K_5\) fully-connected problem is embedded in six qubits on an Advantage using a low chain strength. Variable 0, highlighted in dark magenta, is represented by two qubits, numbers 2437 and 4408. The displayed solution has a broken chain: qubit 4408 returned a value of \(-1\) (represented by a white dot) while qubit 2347 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: