Constraints Example: Minor-Embedding

This chapter shows how to minor-embed the QUBO created in the previous chapter onto a QPU, in this case, a D-Wave 2000Q with its Chimera graph.

It is intended to walk you through the minor-embedding and unembedding process for a simple problem so that you understand how it works. 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. For more information, see the Ocean software documentation.

Chains

As stated in the Solving Problems with Quantum Samplers chapter, objective functions can be represented by graphs and this graphic representation means you can map the objective function to the QPU: nodes that represent variables (sometimes called logical qubits) with linear coefficient are mapped to (physical) qubits and their biases, while edges that represent quadratic coefficients are mapped to couplers and their coupling strengths.

The simple example of the Unconstrained Example: Solving a SAT Problem chapter noted that its two-node graph can be mapped to any two QPU qubits with a shared coupler. But as you saw in the D-Wave QPU Architecture: Topologies chapter, not all qubits share couplers. How do you minor-embed more complex graphs? Minor embedding often requires chains, which are described here.

The QUBO developed for an exactly-one-true constraint with three variables in the Constraints Example: Problem Formulation chapter can be represented by the triangular graph shown in Figure 30.

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

To see how a triangular graph fits on the Chimera graph, take a closer look at the Chimera structure shown in Figure 31. 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.

Fig. 31 Chimera unit cell.

To make a three-node loop of a four-node structure, represent a single variable with a chain of two qubits, as shown in Figure 32, by chaining qubit 0 and qubit 5 to represent variable \(b\).

Fig. 32 Embedding a triangular graph into Chimera by using a chain.

Chaining qubits is done 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.

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

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. You are unlikely to manually embed a random 100-variable problem.

Note

For simplicity, this example uses the first Chimera unit cell with qubits 0 to 7. As explained in the D-Wave QPU Architecture: Topologies chapter, the subset of the graph accessible to users is the working graph, and it’s possible some qubits or couplers used here are not available in a particular QPU. In such a situation, a different unit cell can be selected.

The mapping of Figure 32 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:

1. Evenly split the bias of \(-1\) from variable \(b\) between qubits 0 and 5. Now the bias of these two qubits is \(-0.5\).

2. 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

3. 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\).

1

Setting chain strengths is further discussed in the Appendix: Next Learning Steps chapter.

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. The next section shows and makes sense of the results.

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.

Unembedding

Below are results from submitting2 this problem to a D-Wave 2000Q system for 1000 anneals:

2

The next chapter, Constraints Example: Submitting to a QPU Solver, shows how you submit your objective function to a D-Wave solver.

Energy	Qubit				Occurrences
	0	5	4	1
-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

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 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\).