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 1929 and 1801 on a D-Wave 2000Q 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 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,

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

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 fully-connected problem embedded into four 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 fully-connected problem embedded into six qubits.

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,

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

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 fully-connected problem embedded into six qubits with a broken chain.

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: