Minor-Embedding a Problem onto the Chimera Graph

In this chapter, we show how to minor-embed the QUBO created in the previous chapter into a Chimera graph. Minor embedding often requires chains, which are described here. A solution received from the QPU can be unembedded by reversing the embedding steps.

Note

While this example is intended to walk you through the minor-embedding and unembedding process for a simple problem so that you understand how it works, be aware that D-Wave has automatic embedding and unembedding tools available to streamline this process.

Create a Chain

To determine how a triangular graph fits on the Chimera graph, we need to take a closer look at the Chimera structure shown in Figure 16. Notice that there is no way to set up 3 qubits in a closed loop to achieve the triangle graph configuration of Figure 15. However, we can make a closed loop of 4 qubits using, say, qubits 0, 1, 4, and 5.

Unit cell

Fig. 16 Chimera unit cell.

To fit the 3-qubit loop into a 4-sided structure, we create a chain of 2 physical qubits that will represent a single variable; see Figure 17. In this case, we chain qubit 0 and qubit 5 to represent variable \(b\).

Embedding a triangular graph into Chimera by using a chain.

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

The strength of the coupler between \(q_0\) and \(q_5\), which we want to represent variable \(b\), must be set to correlate the qubits strongly (discussed next), so that in most optimal solutions, \(q_0 = q_5 = b\). The mapping from variables to qubits is known as minor embedding.

Choose the Unit Cells to Work With

As explained in the D-Wave QPU Architecture: Chimera chapter, the subset of the Chimera graph accessible to users is the working graph. Before embedding a problem on the working graph, review the physical layout of the QPU to understand which qubits and couplers are absent from the fabric and therefore which unit cells are good choices.

Map the Problem Parameters to the Working Graph

Now, we translate the work we did in the previous step to map the problem to the actual working graph of the physical QPU. We already know which variables we want to map to which qubit, and we know the node biases and edge strengths from our original graph. Node biases translate to qubit biases for the qubits that represent variables \(a\) and \(c\). See the tables below.

Qubit 0 5 4 1
Variable b b a c
Bias ? ? -1 -1
Coupler (0,4) (5,0) (4,1) (1,5)
Strength 2 ? 2 2

But what about the 2 qubits that represent variable \(b\) and the coupling strength between them? We need a strong negative coupler to chain qubits 0 and 5 thereby create a single logical qubit with the connectivity we need. We also need to add to the existing qubit values to compensate for the negative coupling we are adding.[1]

[1]In the Ising model, we can introduce a bias on the quadratic term without changing the ground state of the problem. For a QUBO problem, however (as we have here), changing the bias on the quadratic term changes the ground state unless we compensate by adding biases (0.5 of the quadratic bias) to each of the two linear terms.

This process requires a few steps:

  1. Evenly split the bias of \(-1\) from variable \(b\) between \(q_0\) and \(q_{5}\). Now the bias of these 2 qubits is \(-0.5\).
  2. Choose a strong negative coupling strength for the chain between \(q_0\) and \(q_{5}\). In this example, we arbitrarily choose \(-3\) as a coupling strength because it is a stronger value than the other couplers around it and is negative, which forces the 2 qubits to be equal.
  3. We now need to add \(1.5\) to each bias of \(q_0\) and \(q_{5}\) to compensate for the \(-3\) we added in step 2. Now the bias for both \(q_0\) and \(q_{5}\) is \(1\).
  4. Finally, we normalize the entire graph to fit within the physical bounds of the system by dividing by all values by \(3\) so that the largest coupler strength is \(-1\).

Our resulting values are as follows, with the chained qubits having a strong negative coupling (\(-1\)):[2]

Qubit 0 5 4 1
Variable b b a c
Bias 0.33 0.33 -0.33 -0.33
Coupler (0,4) (5,0) (4,1) (1,5)
Strength 0.667 -1 0.667 0.667
[2]Some solvers support an extended \(J\) range to allow for even stronger couplings. For more information on extended \(J\) ranges and related controls, see Technical Description of the D-Wave Quantum Processing Unit.

The problem can be sent to the QPU for solution.

Unembed the Solution

After the QPU has solved the exactly-one-true problem and returned a sample of solutions to the embedded problem, those solutions must be unembedded to obtain solutions to the original problem.

Possible returned values for our problem are:

  • \(q_0 = 1\)
  • \(q_{5} = 1\)
  • \(q_{4} = 0\)
  • \(q_1 = 0\)

Reverse the embedding process to get the solution to our original problem:

  • \(a = q_{4} = 0\)
  • \(b = q_0, q_{5} = 1\)
  • \(c = q_1 = 0\)

And this gives us one of the three expected solutions:

\[(a, b, c) = (0, 1, 0).\]

Other possible solutions are \((1, 0, 0)\) and \((0, 0, 1)\).

Note

If a chain is broken, two strongly coupled qubits might “disagree” on what their logical value should be. To address this issue, SAPI includes postprocessing utilities that convert solutions with broken chains into intact solutions.