Constraints Example: Minor-Embedding#

This chapter explains how the QUBO created in the previous chapter is minor-embedded onto a QPU, in this case, an Advantage with its Pegasus graph.

D-Wave provides automatic minor-embedding tools, and if you are submitting your problem to a Leap quantum-classical hybrid solver, the solver handles all interactions with the QPU.

The QUBO developed for an exactly-one-true constraint with three variables in the Constraints Example: Problem Formulation chapter, \(2ab + 2ac + 2bc - a - b - c\), can be represented by the triangular graph shown in Figure 31.

Fig. 31 Triangular graph for an exactly-one-true constraint with its biased nodes and edges.#

As explained in the Solving Problems with Quantum Samplers chapter, nodes that represent the objective function’s variables such as \(a\) are mapped to qubits on the QPU while edges that represent the objective function’s quadratic terms such as \(ab\) are mapped to couplers.

Figure 32 shows such a mapping, between the graph representing the QUBO on the left and one particular minor-embedding on the right. (Rerunning Ocean software’s minorminer tool, which produced this minor embedding, generates embeddings to various qubits across the QPU; the particular qubit numbers noted here are unimportant.)

Nodes \(a, b, c\) (grey circles in the left-hand panel) map to qubits \(1812, 5169, 1827\) (blue circles in the right-hand panel), respectively.
Edges \(ab, bc, ca\) (orange lines in the left-hand panel) map to couplers \([1812, 5619], [1827, 5619], [1812, 1827]\) (blue lines in the right-hand panel), respectively.

Fig. 32 Pegasus embedding for an exactly-one-true constraint rendered by Ocean’s problem inspector. The original QUBO is represented on the left and its embedded representation on the right.#

But, as the D-Wave QPU Architecture: Topologies chapter notes, D-Wave QPUs are not fully connected. For larger graphs than the example above, you may not always be able to map each node to a qubit and find connecting couplers to represent all edges.

How are more complex graphs minor-embedded? Minor embedding often requires chains.

Chains#

To understand how chaining qubits overcomes the problem of sparse connectivity, consider minor embedding the triangular graph of Figure 31 into two target graphs, one sparser than the other. Figure 33 shows two such embeddings: the triangular graph is mapped on the left to a fully-connected graph of four nodes (called a \(K_4\) complete graph ) and on the right to a sparser graph, also of four nodes. For the left-hand embedding, you can choose any mapping between \(a, b, c\) and \(0, 1, 2, 3\); here \(a, b, c\) are mapped to \(2, 0, 1\), respectively. For the right-hand embedding, however, no choice of just three target nodes suffices. The same \(2, 0, 1\) target nodes leaves \(b\) disconnected from \(c\). Chaining target nodes \(0\) and \(3\) to represent node \(b\) makes use of both the connection between \(0\) to \(2\) and the connection between \(3\) and \(1\).

Embedding a triangular graph into Chimera by using a chain. — Fig. 33 Embedding a triangular graph into fully connected and sparse four-node graphs.#

On QPUs, chaining qubits is accomplished by setting the strength of their connecting couplers negative enough to strongly correlate the states of the chained qubits; if at the end of most anneals these qubits are in the same classical state, representing the same binary value in the objective function, they are in effect acting as a single variable.

As an example, consider a fully-connected graph of five nodes (a \(K_5\) graph). Such a graph cannot be mapped to five qubits of an Advantage QPU because the Pegasus graph’s connectivity is too sparse. Instead, some nodes are mapped to chains of qubits.

Figure 34 shows a \(K_5\) graph of some arbitrary problem on the left and a minor-embedding on the right. Here, variable 3 (highlighted magenta) is represented by a two-qubit chain of qubits 4408 and 2437 (highlighted magenta) while variables 0, 1, 2, and 4 are represented by single qubits 4333, 4348, 2497, and 2512.

Pegasus embedding of K5 — Fig. 34 Pegasus embedding for a \(K_5\) fully connected graph rendered by Ocean’s problem inspector. The original QUBO is represented on the left and its embedded representation, with its two-qubit chain, on the right.#

Manual Minor-Embedding#

Manually minor-embedding a problem is typically undertaken only for problems that have either very few variables or a repetitive structure that maps to unit cells of the QPU topology—in both cases you work with one or more unit cells. Additionally, you might make minor adjustments to an embedding found by software. You are unlikely to manually embed a random 100-variable problem.

This section provides an example of how you can calculate the biases needed for minor-embedding on a simple problem. Ocean software’s minor-embedding tools, such as minorminer, do similar calculations.

Example of Manual Minor Embedding

This example returns to the QUBO developed for an exactly-one-true constraint with three variables in the Constraints Example: Problem Formulation chapter, \(2ab + 2ac + 2bc - a - b - c\), as represented by the triangular graph shown in Figure 31 above. For simplicity, it is minor-embedded into a Chimera graph.

To see how a triangular graph fits on the Chimera graph, take a closer look at the Chimera structure shown in Figure 35. Notice that there is no way to make a triangular closed loop of three qubits and their connecting edges. However, you can make a closed loop of four qubits and their edges using, say, qubits 0, 1, 4, and 5.

As in the example of the Chains section, make a three-node loop of a four-node structure by representing a single variable with a chain of two qubits. Figure 36 shows a chaining of qubit 0 and qubit 5 to represent variable \(b\).

Here, for qubits 0 and 5 to represent variable \(b\), the strength of the coupler between them must be set negative enough.

The mapping of Figure 36 is straightforward for non-chained qubits with biases being the linear coefficients of the objective function and coupler strengths the quadratic coefficients:

Variables \(a\) and \(c\), represented by qubits 4 and 1, respectively, have bias \(-1\).
Edges \((a,b), (a,c), (b,c)\), represented by couplers \((0,4), (1,4), (1,5)\), respectively, have strengths \(2\).

To chain qubits 0 and 5 to represent variable \(b\) requires that you add a strong negative coupling strength between them. This coupling has no corresponding quadratic coefficient in the objective function, so other biases must be adjusted to compensate. This process requires a few steps:

Evenly split the bias of \(-1\) from variable \(b\) between qubits 0 and 5. Now the bias of these two qubits is \(-0.5\).
Choose a strong negative coupling strength for the chain between qubits 0 and 5. This example arbitrarily chooses \(-3\) because it is stronger than the values for couplers around it.[1]
Compensate for the \(-3\) added in step 2 by adding \(-\frac{-3}{2} = 1.5\) to each bias of qubits 0 and 5. Now the biases for these qubits are \(1\).

The resulting minor-embedding values are shown in the tables below.

Table 1 Minor Embedding: Linear Coefficients.#
Node	Linear Coefficient	Qubits	Bias
a	-1	4	-1
b	-1	0, 5	1, 1
c	-1	1	-1

Table 2 Minor Embedding: Quadratic Coefficients.#
Edge	Quadratic Coefficient	Coupler	Strength
(a,b)	2	(0,4)	2
(a,c)	2	(1,4)	2
(b,c)	2	(1,5)	2
		(0,5)	-3

You program the quantum computer to solve this problem by configuring the QPU’s qubits with these biases and its couplers with these strengths.

Note

When using the QUBO formulation, as in this example, you compensate for the quadratic term a chain introduces into the objective by adding its negative, divided by the number of qubits in the chain, to the biases of the chain’s qubits; this compensation is not used for the Ising formulation, where the the energies of valid solutions are simply shifted by the introduced quadratic term.

The solutions returned from the QPU express the states of qubits at the end of each anneal. To translate qubit states to values of the problem variables, the solutions must be unembedded.

For example, consider the following results for 1000 anneals:

Energy	Qubit				Occurrences
Energy	0	5	4	1	Occurrences
-1.0	0	0	1	0	206
-1.0	0	0	0	1	526
-1.0	1	1	0	0	267
0.0	1	1	0	1	1

For this simple example with its single chain, unembedding consists of mapping qubits 4, 1 to variables \(a, c\), and qubits 0, 5 to variable \(b\). The results in the table above unembed to:

Row 1: Solution \((a, b, c) = (1, 0, 0)\) with energy \(-1\) was found 206 times.
Row 2: Solution \((a, b, c) = (0, 0, 1)\) with energy \(-1\) was found 526 times.
Row 3: Solution \((a, b, c) = (0, 1, 0)\) with energy \(-1\) was found 267 times.

One anneal ended with result \((a, b, c) = (0, 1, 1)\), which is not a correct solution, and has a higher energy than the correct solutions.

Note

Notice also that the energy of the valid solutions, the ground-state energy, is \(-1\), not the zero calculated in the Constraints Example: Problem Formulation chapter’s truth table. This is because of the constant \(+1\) dropped from the objective function, \(E(a,b,c) = 2ab + 2ac + 2bc - a - b - c + 1\).