Two Illustrative Examples

This chapter, building on the introductory descriptions of the Getting Started with the D-Wave System guide, illustrates the main steps of solving problems on the D-Wave system through two “toy” problems.

The first follows the intuitive approach of the Getting Started with the D-Wave System guide to further familiarize new users with the technology.

The second exploits the techniques of this guide but on a small-scale problem and favoring clarity over efficiency, while pointing out ways to expand the techniques used to larger problems.

Simple Map Coloring Problem

The map-coloring problem is to assign a color to each region of a map such that any two regions sharing a border have different colors.

image

Fig. 19 Coloring a map of Canada with four colors.

A solution to a map-coloring problem for a map of Canada with four colors is shown in Figure 19.

The following is a simple example that demonstrates some of the workflow steps for formulating a given problem that can be solved on the D-Wave system. This section serves as an introduction to the techniques used in other sections.

Formulating the Problem

Generally, the first step in solving a problem is to state it mathematically. In this example, an intuitive approach is to think of the regions as variables representing the possible set of colors, the values of which must be selected from some numerical scheme, such as natural numbers. The selection function must express the problem’s constraints:

  • Each region is assigned one color only, of \(C\) possible colors.
  • The color assigned to one region cannot be assigned to adjacent regions.

Solving the problem means finding a permissible value for each of the variables.

Solving such a problem on the D-Wave system necessitates additional steps due to the following considerations:

  • The mathematical formulation must use binary variables because the solution is implemented physically with qubits, and so must translate to spins \(s_i\in\{-1,+1\}\) or equivalent binary values \(x_i\in \{0,1\}\).
  • Relationships between variables must be reducible to quadratic (e.g., a QUBO) because the problem’s parameters are represented by qubits’ weights and couplers’ strengths on a QPU.
  • The mathematical formulation should be sparing in its number of variables because a QPU has a limited number of qubits and couplers[1].
  • Alternative formulations may have different implications for performance.
[1]The Decomposing a Large Problem chapter discusses this topic and approaches for solving problems with many variables on the D-Wave system.

In particular, the D-Wave system solves problems by minimizing an objective function, which expressed as a QUBO in scalar notation is

\[\text{E}(a_i, b_{i,j}; q_i) = \sum_{i} a_i q_i + \sum_{i<j} b_{i,j} q_i q_j,\]

where \(a_i\) are the biases or weights for each qubit, \(q_i\), and \(b_{i,j}\) the coupler strength between qubits \(i\) and \(j\). The map coloring problem is solved by setting biases \(a_i\) and coupler strengths \(b_{i,j}\) such that the qubits \(q_i\) in the minimized objective satisfy the constraints on coloring for all the regions.

Translating to Binary

The Reformulating a Problem chapter describes techniques to map problems with integer variables to binary formulations, and the Formulating an Integer CSP as a QUBO Problem section gives a larger example.

This example simply maps the \(C\) possible colors to a unary encoding (rather than using natural numbers). Each region is represented by \(C\) qubits, one for each possible color, which is set to value \(1\) if selected, while the remaining \(C-1\) qubits are \(0\).

Table 5 shows two schemes for representing colors for a map with \(C=4\) possible colors, where \(q_B\) is a qubit representing blue, \(q_G\) green, \(q_R\) red, and \(q_Y\) yellow.

Table 5 Translating Color to Binary.
Color Naturals Unary Encoding
Blue 1 \(q_B,q_G,q_R,q_Y = 1,0,0,0\)
Green 2 \(q_B,q_G,q_R,q_Y = 0,1,0,0\)
Red 3 \(q_B,q_G,q_R,q_Y = 0,0,1,0\)
Yellow 4 \(q_B,q_G,q_R,q_Y = 0,0,0,1\)

Expressing a Constraint

The Reformulating a Problem chapter describes various methods for incorporating constraints into the formulation of a problem. This example’s simple constraints are formulated intuitively as follows.[2]

[2]This is explained in more detail for a simple two-qubit example in Getting Started with the D-Wave System.

Consider for a two-color problem the constraint that a region be assigned a single color only. Here, the \(C=2\) colors are unary encoded by \(q_B,q_G\), with allowed states being either blue selected, \(q_B,q_G=1,0\), or green selected, \(q_B,q_G=0,1\), but not both or neither selected. The objective in QUBO format for two qubits, each with its bias and a single coupler between them, is

\[\text{E}(a_i, b_{i,j}; q_i) = a_B q_B + a_G q_G + b_{B,G} q_B q_G.\]

Table 6 shows all the possible states for a single-region, two-color problem. In this table, column \(\mathbf{q_B}\) and \(\mathbf{q_G}\) are all possible states of the two qubits encoding the region’s two colors; column Constraint shows whether or not the state of the qubits meet the constraint that one color is selected; column \(\mathbf{\text{E}(a_i, b_{i,j}; q_i)}\) is the energy calculated for the state from the objective function.

Table 6 States for a Constraint Selecting One of Two Colors.
\(\mathbf{q_B}\) \(\mathbf{q_G}\) Constraint \(\mathbf{\text{E}(a_i, b_{i,j}; q_i)}\)
0 0 Violates \(0\)
0 1 Meets \(a_G\)
1 0 Meets \(a_B\)
1 1 Violates \(a_B+a_G+b_{B,G}\)

Coefficients that minimize the objective for this constraint can be guessed from looking at Table 6 and the following considerations:

  • Both colors are equally preferred, so setting \(a_B=a_G\) ensures identical energy for both states that meet the constraint (\(q_B, q_G=0,1\) and \(q_B, q_G=1,0\)).
  • The state \(q_B, q_G=0,0\), which violates the constraint, has energy \(0\), so to ensure that the non-violating states have lower energy, set \(a_B = a_G < 0\).
  • Having set the minimum energy to negative for the valid states, setting \(a_B+a_G+b_{B,G}=0\) for non-valid state \(q_B, q_G=1,1\) ensures that state has a higher energy.

One solution[3] is to set \(a_B=a_G=-1\) and \(b_{B,G}=2\). Setting these values for the qubit biases and coupler strength sets the minimum energy for this objective to \(-1\) for both valid states and zero for the states that violate the constraint; that is, this objective has lowest energy if just one color is selected (only one qubit is \(1\)), where either color (qubit) has an equal probability of selection.

[3]Getting Started with the D-Wave System discusses the effects of different choices of values in the section on problem scaling. See also the considerations discussed in the Overcoming Imprecisions of Qubit Biases and Coupling Strengths section.

The two-color formulation above can be easily expanded to a three-color problem: \(C=3\) possible colors are encoded as \(q_B,q_G,q_R\). The objective to minimize in QUBO format is

\[ \text{E}(a_i, b_{i,j}; q_i) = a_B q_B + a_G q_G + a_R q_R +b_{B,G} q_B q_G + b_{B,R} q_B q_R +b_{G,R} q_G q_R.\]

Coefficients that minimize the objective can be guessed by applying the previous considerations more generically. All colors are equally preferred, so set \(a_i=a\) to ensure identical energy for states that meet the constraint. Simplify by setting \(b_{i,j}=b=2\) and \(a=-1\) for an objective

\[ \begin{align}\begin{aligned} \text{E}(a, b; q_i) &= a(q_B + q_G + q_R) +b(q_B q_G + q_B q_R + q_G q_R)\\&= -(q_B + q_G + q_R) +2(q_B q_G + q_B q_R + q_G q_R).\end{aligned}\end{align} \]

Table 7 enumerates all states of the objective for three possible colors. The meanings of the columns in this table are identical to those for Table 6 above.

Table 7 States for a Constraint Selecting One of Three Colors.
\(\mathbf{q_B,q_G,q_R}\) Constraint \(\mathbf{\text{E}(a=-1, b=2; q_i)}\)
0,0,0 Violates \(-(0) +2(0)=0\)
0,0,1 Meets \(-(1) + 2(0)=-1\)
0,1,0 Meets \(-(1) + 2(0)=-1\)
0,1,1 Violates \(-(2) + 2(1)=0\)
1,0,0 Meets \(-(1) + 2(0)=-1\)
1,0,1 Violates \(-(2) + 2(1)=0\)
1,1,0 Violates \(-(2) + 2(1)=0\)
1,1,1 Violates \(-(3) + 2(3)=3\)

Again, the minimum energy for this objective is \(-1\) for valid states and higher for states that violate the constraint; that is, this objective has lowest energy if just one color is selected (one qubit is \(1\)), where the three colors (qubits) have equal probability of selection.

For the four-color map problem, the one-color-per-region constraint can likewise be simplified to a QUBO objective, with \(b_{i,j}=b=2\) and \(a_i=a=-1\),

\[ \text{E}(a, b; q_i) = -(q_B + q_G + q_R + q_Y) +2(q_B q_G + q_B q_R + q_B q_Y + q_G q_R + q_G q_Y + q_R q_Y).\]

The second constraint, that adjacent regions have different colors, can be expressed by weighting the qubits of each region and the couplers between regions to minimize an objective function when different colors are selected for adjacent regions. That is, if \(q_B=1\) (blue is selected) on one side of a shared border, for example, the objective has lower energy if \(q_B=0\) (blue is not selected) on the other side. In this way, a state of \(q_B,q_G,q_R,q_Y = 1,0,0,0\) (blue selected) in one region and, for example, \(q_B,q_G,q_R,q_Y = 0,1,0,0\) (green selected) in an adjacent region has lower energy than the same state (the same color selected) in both.

By configuring both types of constraint together, as shown in the following sections, the combined objective has lowest energy states when simultaneously each region is assigned a single color and adjacent regions do not select the same colors.

Minor-Embedding the Problem

The D-Wave QPU minimizes the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a \(M,N,L\) Chimera graph. To solve a given Ising spin problem with arbitrary pairwise interaction structure, you minor embed its graph into a Chimera graph by using qubits to represent missing edges. Figure 20 depicts the map-coloring problem as a graph, where each region is a node (vertex) and adjacent borders are edges.

image

Fig. 20 Map of Canada represented graphically with regions as connected nodes.

The Minor-Embedding a Problem chapter describes various methods for embedding a given problem. This example illustrates an embedding for the simple four-color map problem.

Minor-Embed a Region

Similar to the simplified approach to constraints in the previous section, consider first embedding in the context of a single region with a unary encoding scheme for color. Figure 21 shows the constraints of the previous C=2, 3, 4 map-coloring problems as graphs.

image

Fig. 21 Color constraints represented graphically for two, three, and four colors with unary encoding.

The constraints of a four-color map problem require full connectivity between the four qubits encoding the color for each region. This example accomplishes that by embedding each region in a unit cell (8 qubits and 16 couplers on the D-Wave 2000Q QPU), shown in Figure 22.

image

Fig. 22 Unit cell on the D-Wave 2000Q QPU.

Logical and Physical Qubits

To map a complete four-vertex graph to a Chimera unit cell, it helps to introduce a distinction between the logical qubits (\(q_B,q_G,q_R,q_Y\)) and couplers of the previous sections and the QPU’s physical qubits (\(q_0, q_1\),...) and couplers: minor-embedding maps each logical qubit to one or more connected physical qubits in a chain. To embed a graph into the Chimera topology (i.e., to implement a coupler between logical qubits with a shared edge), find a physical coupler between any physical qubits in the two chains representing the logical qubits.

This example embeds the four logical qubits \(q_B,q_G,q_R,q_Y\) representing four colors for a region in four chains of two physical qubits each: the blue logical qubit is a coupling of the top two physical qubits in the D-Wave unit cell; green, red, and yellow are rows 2, 3, and 4 respectively. As shown in Figure 23, representing each logical qubit as a chain of two physical qubits enables full connectivity between the four.

image

Fig. 23 Embedding a four-color unary-encoded region in a unit cell on the D-Wave 2000Q QPU. On the left, each of the logical qubits \(q_B,q_G,q_R,q_Y\) is represented by a colored dot and the logical couplers between them by arrows. On the right, the 8 physical qubits of a single unit cell are represented by dots and the 16 couplers by lines. The 4 colored areas represent logical qubits, each representing a chain of two physical qubits.

Expressing a Chain

A chain is formulated as a constraint: all its member physical qubits represent a single logical qubit; i.e., all the qubits in a chain should have identical spins \(s_i\in\{-1,+1\}\), in an Ising formulation, or binary values \(x_i\in \{0,1\}\), in a QUBO formulation.

Similar to the single-color-per-region constraint formulated above for a two-color problem, the constraint that a two-qubit chain represents a logical qubit for a color (e.g., \(q_B\), the logical qubit representing blue shown in Figure 23) has an objective of the form:

\[\text{E}(a_i, b_{i,j}; q_{Bi}) = a_1 q_{B1} + a_2q_{B2} + b_{1,2} q_{B1} q_{B2},\]

where \(q_{Bi}\) are the two physical qubits of the logical qubit for blue. For example, in a region embedded in the topmost left unit cell, these are physical qubits \(q_{0}\) and \(q_{4}\) shown in Figure 24.

image

Fig. 24 Top-left part of the Chimera graph.

Table 8 enumerates the possible states of the objective for a constraint that formulates a logical qubit for blue. The meanings of the columns in this table are identical to those for Table 6 above.

Table 8 States for a Two-Qubit Chain.
\(\mathbf{q_{B1}}\) \(\mathbf{q_{B2}}\) Constraint \(\mathbf{\text{E}(a_i, b_{i,j}; q_{Bi})}\)
0 0 Meets \(0\)
0 1 Violates \(a_2\)
1 0 Violates \(a_1\)
1 1 Meets \(a_1+a_2+b_{1,2}\)

Coefficients that minimize the objective for this constraint are guessed from looking at Table 8 and the following considerations:

  • The valid state \(q_{B1}, q_{B2}=0,0\) (blue is not selected) has energy \(0\), so to ensure that the violating states have higher energy, set \(a_1, a_2 > 0\).
  • The chain’s constraint should not bias whether the color blue is selected or not—its task is solely that the two physical qubits represent a single logical qubit—so in the context of this constraint, both valid states are equally preferred. Setting \(a_1+a_2+b_{1,2}=0\) for valid state \(q_{B1}, q_{B2}=1,1\) (blue is selected) ensures that state has the same energy as \(q_{B1}, q_{B2}=0,0\) (blue is not selected). This requires that \(b_{1,2} = -|a_1 + a_2|\).

Again one solution is to set \(a_1=a_2=1\) and \(b_{1,2}=-2\). Configuring these values for the qubit biases and coupler strength sets the minimum energy for this objective to \(0\) for both valid states and \(1\) for the states that violate the constraint; that is, this objective has lowest energy if the two qubits in the chain are aligned.

Similar constraints create chains for logical qubits \(q_{G}\) (green), \(q_{R}\) (red), and \(q_{Y}\) (yellow).

Having aligned the two physical qubits of a chain (e.g., \(q_{0}, q_{4}\)) of a logical qubit for each color (e.g., \(q_{B}\)), the four logical qubits (\(q_{B},q_{G},q_{R},q_{Y}\)) in each region must be assigned their individual biases and coupling strengths. For the four-color map problem, the constraint on one color per region was formulated in the previous section with an objective having the following coefficients:

  • Equal biases of \(a=-1\) for the logical qubits.

    Mapping logical to physical qubits with a chain of length two, divide the logical qubit’s weight of \(a=-1\) in half, applying a weight of \(a=-1/2\) to each of the two physical qubits in the chain.

  • Coupler strengths of \(b=2\).

    Mapping logical to physical couplers with two physical couplers connecting each pair of logical qubits (see Figure 23), divide the logical coupler’s strength of \(b=2\) between two physical couplers, applying strength of \(b=1\) to each physical coupler in the unit cell.

Coupling Two Regions

In this simple example, the structures of the problem and the Chimera topology align well, and it’s easy to couple the logical qubits of two adjacent regions to embed the constraint that adjacent regions select different colors. For example, to find a physical coupler connecting British Columbia’s red qubit to Alberta’s red qubit, look at a slightly larger portion of the Chimera graph shown in Figure 25: black arcs highlight the physical couplers connecting two adjacent unit cells. Clearly these couplers are ideally positioned to penalize the state where the chains representing the same color are turned on in both unit cells, thereby implementing the constraint that adjacent regions select different colors.

image

Fig. 25 Coupling two four-color, unary-encoded regions, British Columbia and Alberta, each represented by a unit cell on the D-Wave 2000Q QPU. On the right, the black lines represent physical couplers between logical qubits, represented as colored areas containing two physical qubits in a chain.

Denoting British Columbia’s red qubit as \(q_{R}^{BC}\) and Alberta’s red qubit as \(q_{R}^{AB}\), the constraint that adjacent regions have different colors can be formulated similarly to the objective previously constructed to ensure two coupled qubits have different values:

\[ \text{E}(a_i, b_{i,j}; q_i) = a^{BC}_{R} q_{R}^{BC} + a^{AB}_{R} q_R^{AB} + b_{R}^{BC,AB} q_{R}^{BC} q_R^{AB}\]

Configuring \(a^{BC}_{R} = a^{AB}_{R} = 0\) and \(b_{R}^{BC,AB} = 1\) sets a higher energy for the state \(q_{R}^{BC} = q_R^{AB}\) (red selected in both British Columbia and Alberta), penalizing that invalid state, while leaving the valid three states with an energy of \(0\).

Coupling Several Regions

The structural alignment between the Chimera graph and the four-color problem is ideal for British Columbia and Alberta but does not extend to the three-way neighbor relation of British Columbia, Alberta, and the Northwest Territories (shown on the Canadian map of Figure 19). Because unit cells are configured in a two-dimensional checkerboard array, these three regions cannot be mapped to unit cells while preserving the three-way neighbor relation. For example, assigning British Columbia and Alberta to unit cells that neighbor each other horizontally, as in Figure 25, leaves the Northwest Territories unit cells to the left of British Columbia, to the right of Alberta, or below either, but never as a direct neighbor of both. In such a configuration, no physical couplers are available to ensure that the same color qubits in these three regions are not simultaneously activated.

Introducing clones—in this case, multiple unit cells represent a region—overcomes this in a way analogous to the chaining of physical qubits to represent a logical qubit. Just as chains extend the footprint of a logical qubit in the graph of physical qubits, clones, by extending the footprint of a single region in the array of unit cells, add neighbors to the cloned region. This enables the enforcement of constraints to cases where neighbors on the map do not transfer directly to adjacent unit cells.

Figure 26 shows the use of cloned regions to enable coupling of all neighboring regions in Canada’s map.

image

Fig. 26 Mapping of Canada’s 13 regions to unit cells in the Chimera graph of a D-Wave 2000Q; regions and clones are labeled with standard two-letter postal codes, shown in Figure 20.

Set the strengths of intercell couplers so the same color is selected for all clones of a region, in the same way as for chains of physical qubits representing a logical qubit. For example, for the physical coupler connecting the red qubits of the top and bottom clones of Alberta, set a strength of \(-2\) and add a weight of \(1\) to the two physical qubits connected via that coupler. Repeat for each of the other three colors, and do the same for the cloned British Columbia and Northwest Territories.

Decomposing

The previous sections of this example explain the steps of solving a small problem: coloring a map of Canada’s 13 regions using four colors, as shown in Figure 19. This section briefly looks at how this solution can scale to larger problems, for example to maps with more regions, more colors, or both.

The Decomposing a Large Problem chapter describes some techniques for decomposing large problems into smaller ones that can be solved on the QPU. To solve the map-coloring problem on a map of the United States, use a divide-and-conquer technique: divide the US map into chunks; process the first chunk (find valid colorings for the first set of states); use these colorings to bias the second chunk; repeat until the solution is completed.

Figure 27 shows a solution to coloring a map of the United States, which ran on the D-Wave 2000Q in two manageable chunks.

image

Fig. 27 A map of the US colored through division into two smaller parts. The larger of the two, on the left, is just small enough to fit on the D-Wave 2000Q QPU.

Direct Formulations

The previous sections formulated the map-coloring problem in several easily grasped steps. Experienced users might formulate a more direct approach as follows.

For graph \(G(V,E)\) of the map problem—no two vertices, \(V\), connected by an edge, \(E\), should select the same color from set \(C\)—construct a cost function with binary variables, \(x_{v,c}=1\) when \(v \in {V}\) selects color \(c \in C\), by implementing two constraints:

\[(\sum_c x_{v,c} -1)^2,\]

which has minimum energy (zero) when vertices select one color only, and

\[\sum_c \sum_{v_a,v_b \in E} x_{v_a,c} x_{v_b,c},\]

which adds a penalty if the vertices of an edge select the same color.

These constraints give a QUBO,

\[E(x_v,x_{v_a,v_b}) = \sum_v (\sum_c x_{v,c} -1)^2 + \sum_c \sum_{v_a,v_b \in E} x_{v_a,c} x_{v_b,c}.\]

The minima (ground states) of this QUBO have zero energy for viable solutions. This formulation of the generic problem must still be applied to the map and color set and then embedded.

This section solved the map-coloring problem using a technique of formulating a problem as a constraint satisfaction problem (CSP) using penalty functions. The CSP Reformulation with Penalty Functions section describes this technique and demonstrates it in detail on a simple two-color, two-region part of this map-coloring problem in the Example of CSP reformulation with penalty functions section.

Further Information

  • [Dwave4] is a whitepaper on the map coloring problem.
  • [Rie2014] describes mappings of planning problems to QUBOs, including map coloring.
  • [Bis2017] describes a formulation of this problem.

Simple Circuit Fault Diagnosis Problem

Fault diagnosis is the combinational problem of quickly localizing failures as soon as they are detected in systems. Circuit fault diagnosis (CFD) is the problem of identifying a minimum-sized set of gates that, if faulty, explains an observation of incorrect outputs given a set of inputs.

image

Fig. 28 A simple circuit is shown in Figure 28.

The following example demonstrates some of the techniques available to formulate a given problem so it can be solved on the D-Wave system.

Formulating the Problem

As in the Simple Map Coloring Problem section above, this example solves the CFD problem by configuring the objective function expressed as a scalar QUBO,

\[\text{E}(a_i, b_{i,j}; q_i) = \sum_{i} a_i q_i + \sum_{i<j} b_{i,j} q_i q_j,\]

where \(a_i\) are the biases or weights for each qubit, \(q_i\), and \(b_{i,j}\) the coupler strength between qubits \(i\) and \(j\). The problem is configured by setting biases \(a_i\) and coupler strengths \(b_{i,j}\) such that the qubits \(q_i\) of the minimized objective function represent the minimum number of faults given the input and output values of the circuit. CFD solutions are those configurations that have the lowest energy levels.

A Short Digression: An Intuitive Explanation of the CFD Solution

To understand the relationship between the CFD solutions and low-energy configurations, it’s helpful to look at an even smaller example.

image

Fig. 29 The circuit in Figure 29 has three NOT gates in series, with an input \(q_0\), an output \(q_3\), and intermediate input/outputs \(q_1\) and \(q_2\).

The following sections of the CFD example configure an objective function that has a higher energy level when a gate is faulty. Assuming that this serial NOT circuit has such an objective function, where the energy level increases by a value of \(1\) for any malfunctioning gate in the circuit, energy levels for all possible circuit states with an incorrect output are shown in Table 9.

In this table, the first column, Circuit Input (\(\mathbf{q_0}\)), is the binary input value applied to the circuit in testing, and the second column, Incorrect Output (\(\mathbf{q_3}\)), is the measured output of the circuit with an error detected. Columns \(\mathbf{q_1}\) and \(\mathbf{q_2}\) are all possible intermediate input/outputs of the circuit’s gates. Column Faulty Gate shows which gates are malfunctioning given the input and output states. Column Energy is the energy level of the objective function.

Table 9 Serial NOT Energy Levels
Circuit Input (\(\mathbf{q_0}\)) Incorrect Output (\(\mathbf{q_3}\)) \(\mathbf{q_1}\) \(\mathbf{q_2}\) Faulty Gate Energy
\(0\) \(0\) \(0\) \(0\) 1,2,3 \(3\)
\(0\) \(1\) 1 \(1\)
\(1\) \(0\) 3 \(1\)
\(1\) \(1\) 2 \(1\)
\(1\) \(1\) \(0\) \(0\) 2 \(1\)
\(0\) \(1\) 3 \(1\)
\(1\) \(0\) 1 \(1\)
\(1\) \(1\) 1,2,3 \(3\)

In Table 9, for the first and last rows, all three gates are malfunctioning, each increasing the energy level by \(1\) for a total energy level of \(3\):

\[ \begin{align}\begin{aligned}\text{First Row:} \qquad (q_1=0) \ne \neg (q_0 = 0) \quad (q_2=0) \ne \neg (q_1 = 0) \quad (q_3=0) \ne \neg (q_2 = 0)\\\text{Last Row:} \qquad (q_1=1) \ne \neg (q_0 = 1) \quad (q_2=1) \ne \neg (q_1 = 1) \quad (q_3=1) \ne \neg (q_2 = 1)\end{aligned}\end{align} \]

For the second to seventh rows, the circuit has a single malfunctioning gate, increasing the energy level by \(1\); for example, in the second row, the gate 1 is the only malfunctioning gate:

\[\text{Second Row:} \qquad (q_1=0) \ne \neg (q_0 = 0) \quad (q_2=1) = \neg (q_1 = 0) \quad (q_3=0) = \neg (q_2 = 1)\]

The minimum-sized set of gates that, if faulty, explains the observation of incorrect outputs given a set of inputs, are the single malfunctioning gates of rows 2–7. These have the lowest non-zero energy for the serial NOT circuit.

Intuitively, imagine that an objective function has been minor embedded on the QPU such that \(q_i\) are physical qubits representing the inputs and outputs of the circuit and its NOT gates. To mimic the behavior of a NOT operation, the relationship between each sequential pair of qubits should resemble anti-ferromagnetic coupling: the likely opposite binary states (0/1) of a NOT operation, such as that of gate 1, is represented on the QPU by positively coupling physical qubits \(q_0\) and \(q_1\), meaning the lowest energy states have opposite spins (-1/1 or 1/-1). For a functioning circuit, the four qubits line up “head-to-tail”; but when the circuit’s output, represented by \(q_3\), is clamped in a faulty state, at least one sequential pair of qubits must have their spins aligned despite the anti-ferromagnetic coupling, raising the energy level.

Return to the CFD Example

The Simple Map Coloring Problem section above followed an intuitive approach to finding an objective function. This example exploits the methods of the Reformulating a Problem and Minor-Embedding a Problem chapters to formulate and embed the objective function as follows:

  1. Using the techniques of CSP Reformulation with Penalty Functions and Elementary Boolean Operations to QUBO, the Boolean operation of each gate is reformulated as a penalty function that penalizes its incorrect operation; that is, configurations that represent a gate producing incorrect output for its given inputs have higher energy levels than valid configurations. The greater the number of malfunctioning gates, the higher the energy level of the objective function, which sums all the penalty functions. By finding configurations with the lowest energies, the D-Wave system can discover the configurations with minimum faults that produce incorrect outputs.
  2. Penalty functions are normalized so any single fault results in the same penalty value. (If faulty states have different penalties, the combined penalty on two faults might produce a lower energy level than a single fault, in which case the set of minimum-fault configurations is not the set of configurations with lowest energies.)
  3. The penalty functions are embedded on the QPU. The embedding demonstrated in this example exploits the method of Pre-embedding Local Constraint Structures for locally-structured embeddings described in the Minor-Embedding a Problem chapter. These embeddings are chosen for their explanatory advantages, not their efficiency; see the General Considerations for considerations used to select embeddings in actual problems.
  4. The use of software tools to automate the previous steps is discussed.

Representing Boolean Gates as Penalty Functions

This example maps the circuit’s gates to penalty functions using the formulations of the Elementary Boolean Operations to QUBO section. These penalty functions increase the energy level of the problem’s objective function by penalizing non-valid states of the Boolean operations, which represent malfunctioning gates.

  1. The NOT gate

    NOT can be represented as penalty function

    \[z \Leftrightarrow \neg x: \qquad 2xz-x-z+1.\]

    Table 10 shows that this function penalizes states that represent a malfunctioning gate while no penalty is applied to a functioning gate. In this table, column in is all possible states of the gate’s inputs; column \(\mathbf{out_{valid}}\) is the corresponding output values of a functioning gate while \(\mathbf{out_{fault}}\) is the corresponding output values of a malfunctioning gate, which are simply \(out_{fault} = \neg out_{valid}\); column \(\mathbf{P_{valid}}\) is the value the penalty function adds to the energy of the objective function when the gate is functioning (zero, a functioning gate must not be penalized) while column \(\mathbf{P_{fault}}\) is the value the penalty function adds when the gate is malfunctioning (nonzero, the objective function must be penalized with a higher energy).

    Table 10 Boolean NOT Operation as a Penalty.
    in \(\mathbf{out_{valid}}\) \(\mathbf{out_{fault}}\) \(\mathbf{P_{valid}}\) \(\mathbf{P_{fault}}\)
    \(0\) \(1\) \(0\) \(0\) \(1\)
    \(1\) \(0\) \(1\) \(0\) \(1\)

    For example, the state \(in, out_{valid}=0,1\) of the first row is represented by the penalty function with \(x=0\) and \(z = 1 = \neg x\). For this functioning gate, the value of \(P_{valid}\) is

    \[2xz-x-z+1 = 2 \times 0 \times 1 - 0 - 1 + 1 = -1+1=0,\]

    not penalizing the valid configuration. In contrast, the state \(in, out_{fault}=0,0\) of the first row is represented by the penalty function with \(x=0\) and \(z = 0 \ne \neg x\). For this malfunctioning gate, the value of \(P_{fault}\) is

    \[2xz-x-z+1 = 2 \times 0 \times 0 -0 -0 +1 =1,\]

    adding an energy cost of \(1\) to the incorrect configuration.

  2. The AND gate

    AND can be represented as penalty function

    \[z \Leftrightarrow x_1 \wedge x_2: \qquad x_1 x_2 - 2(x_1+x_2)z +3z.\]

    Table 11 shows that this function penalizes states that represent a malfunctioning gate while no penalty is applied to a functioning gate. The meanings of the columns in this table are identical to those for the NOT gate above.

    Table 11 Boolean AND Operation as a Penalty.
    in \(\mathbf{out_{valid}}\) \(\mathbf{out_{fault}}\) \(\mathbf{P_{valid}}\) \(\mathbf{P_{fault}}\)
    \(0,0\) \(0\) \(1\) \(0\) \(3\)
    \(0,1\) \(0\) \(1\) \(0\) \(1\)
    \(1,0\) \(0\) \(1\) \(0\) \(1\)
    \(1,1\) \(1\) \(0\) \(0\) \(1\)

    For example, the state \(in=0,0; out_{valid}=0\) of the first row is represented by the penalty function with \(x_1=x_2=0\) and \(z = 0 = x_1 \wedge x_2\). For this functioning gate, the value of \(P_{valid}\) is

    \[ \begin{align}\begin{aligned}x_1 x_2 - 2(x_1+x_2)z +3z &= 0 \times 0 -2 \times (0+0) \times 0 + 3 \times 0\\&= 0,\end{aligned}\end{align} \]

    not penalizing the valid configuration. In contrast, the state \(in=0,0; out_{fault}=1\) of the same row is represented by the penalty function with \(x_1=x_2=0\) and \(z = 1 \ne x_1 \wedge x_2\). For this malfunctioning gate, the value of \(P_{fault}\) is

    \[ \begin{align}\begin{aligned}x_1 x_2 - 2(x_1+x_2)z +3z &= 0 \times 0 -2 \times (0+0) \times 1 + 3 \times 1\\&= 3,\end{aligned}\end{align} \]

    adding an energy cost of \(3\) to the incorrect configuration.

  3. The XOR gate

    XOR can be represented as penalty function

    \[z \Leftrightarrow x_1 \oplus x_2: \qquad 2x_1x_2 -2(x_1+x_2)z - 4(x_1+x_2)a +4az +x_1+x_2+z + 4a,\]

    where \(a\) is an ancillary variable as described in the Non-Quadratic (Higher-Degree) Polynomials to Ising/QUBO section of chapter Reformulating a Problem (and shown below).

    Table 12 shows that no penalty is applied to a functioning gate when this penalty function is minimized (when this function is part of an objective function being minimized, its value is zero for at least one of the possible values of ancillary variable \(a\)). In this table, column in is all possible states of the gate’s inputs \(x_1,x_2\); column \(\mathbf{out}\) is the corresponding output values of a functioning gate \(x_1 \oplus x_2\); columns \(\mathbf{P_{a=0}}\) and \(\mathbf{P_{a=1}}\) are the values of the penalty function if the ancillary variable \(a=0\) or \(a=1\) respectively; and the final column, \(\mathbf{\min_{a}P}\), is the value the penalty function adds to the minimized objective function (the minimum penalty of \(\mathbf{P_{a=0}}\) or \(\mathbf{P_{a=1}}\)).

    Table 12 Boolean XOR Operation as a Penalty: Functioning Gate.
    in \(\mathbf{out}\) \(\mathbf{P_{a=0}}\) \(\mathbf{P_{a=1}}\) \(\mathbf{\min_{a}P}\)
    \(0,0\) \(0\) \(0\) \(4\) \(0\)
    \(0,1\) \(1\) \(0\) \(4\) \(0\)
    \(1,0\) \(1\) \(0\) \(4\) \(0\)
    \(1,1\) \(0\) \(4\) \(0\) \(0\)

    For example, the state \(in=0,0\) of the first row is represented by the penalty function with \(z=0 \Leftrightarrow x_1 \oplus x_2 = 0 \oplus 0 =0\). For this functioning gate, the value of \(P\) for each possible value of ancillary variable \(a\) is

    \[ \begin{align}\begin{aligned}a=0: &\quad 2x_1x_2 -2(x_1+x_2)z - 4(x_1+x_2)a +4az +x_1+x_2+z + 4a\\ &= 2 \times 0 \times 0 -2 \times (0+0) \times 0 -4 \times (0+0) \times 0 +4 \times 0 +0+0+0+ 4\times 0\\ &= 0\\a=1: &\quad 2x_1x_2 -2(x_1+x_2)z - 4(x_1+x_2)a +4az +x_1+x_2+z + 4a\\ &= 2 \times 0 \times 0 -2 \times (0+0) \times 0 -4 \times (0+0) \times 1 +4 \times 1 \times 0 +0+0+0+ 4\times 1\\ &= 4.\end{aligned}\end{align} \]

    When this penalty function is part of an objective function being minimized, the solution with \(a=0\), which contributes less to the total energy level, is preferred, giving a penalty of zero for the functioning gate.

    Table 13 shows that a non-zero penalty is applied to a malfunctioning gate. In this table, column \(\mathbf{out}\) is the output values of a malfunctioning gate \(out = \neg (x_1 \oplus x_2)\); the other columns are identical to those for Table 12 above.

    Table 13 Boolean XOR Operation as a Penalty: Malfunctioning Gate.
    in \(\mathbf{out}\) \(\mathbf{P_{a=0}}\) \(\mathbf{P_{a=1}}\) \(\mathbf{\min_{a}P}\)
    \(0,0\) \(1\) \(1\) \(9\) \(1\)
    \(0,1\) \(0\) \(1\) \(1\) \(1\)
    \(1,0\) \(0\) \(1\) \(1\) \(1\)
    \(1,1\) \(1\) \(1\) \(1\) \(1\)

    For example, the state \(in=0,0\) of the first row is represented by the penalty function with \(z=1 \Leftrightarrow x_1 \oplus x_2 = 0 \oplus 0 = 0\). For this malfunctioning gate, the value of \(P\) for each possible value of ancillary variable \(a\) is

    \[ \begin{align}\begin{aligned}a=0: &\quad 2x_1x_2 -2(x_1+x_2)z - 4(x_1+x_2)a +4az +x_1+x_2+z + 4a\\ &= 2 \times 0 \times 0 -2 \times (0+0) \times 1 -4 \times (0+0) \times 0 +4 \times 0 \times 1 +0+0+1+ 4\times 0\\ &= 1\\a=1: &\quad 2x_1x_2 -2(x_1+x_2)z - 4(x_1+x_2)a +4az +x_1+x_2+z + 4a\\ &= 2 \times 0 \times 0 -2 \times (0+0) \times 1 -4 \times (0+0) \times 1 +4 \times 1 \times 1 +0+0+1+ 4\times 1\\ &= 9.\end{aligned}\end{align} \]

    When this penalty function is part of an objective function being minimized, the solution with \(a=0\), which contributes less to the total energy level, is preferred, giving a penalty of \(1\) for the malfunctioning gate.

Normalizing the Penalty Functions

To solve the CFD problem by finding a minimum-sized set of faulty gates, a search for lowest energy levels of the objective function should identify all single faults. However, if functions impose different penalties for faulty states—if some faults are penalized to a higher value than others—two faults with low penalties might produce a lower energy level than a strongly penalized single fault.

The penalty functions of the previous section impose a penalty of \(1\) on all gate faults with one exception: Table 11 shows that when the state \(in=0,0\) of the AND gate incorrectly outputs \(out=1\), the penalty imposed is \(P_{fault}=3\). This section aims to normalize the penalty functions; that is, to adjust the penalty functions so any single fault has an identical penalty, contributing equally to the objective function of the CFD problem.

One approach to normalizing the penalty function of the AND gate is to add a penalty function that imposes a reward on (a negative penalty to compensate for) the state \(in=0,0; out=1\) with its higher penalty value. The additional penalty function, \(P^*\), rewards this state with a negative penalty of value,

\[ \begin{align}\begin{aligned}P_{fault}(0,0;1)+ P^*(0,0;1) &= 1\\3+P^*(0,0;1) &= 1\\P^*(0,0;1) &= -2\end{aligned}\end{align} \]

Because both penalties are activated together in state \(in=0,0; out=1\), the total penalty they impose is \(1\), identical to the penalties of other single faults for the circuit’s gates.

The binary equivalence,

\[in_1,in_2,out=0,0,1 \longleftrightarrow \overline{in}_1,\overline{in}_2,out=1,1,1,\]

makes it straightforward to guess a penalty function, \(P^*\), that activates a reward of \(-2\) for the AND gate state of \(\overline{in}_1,\overline{in}_2,out=1,1,1\):

\[P^*= -2\overline{in}_1\overline{in}_2out.\]

Clearly this penalty function is non-zero only for faulty state \(in_1,in_2,out=0,0,1\), in which case it is equal to \(-2\). Adding this penalty to the problem’s objective function normalizes the penalty function for the AND operation.

For example, recalculating the penalty given as an example in the previous section, the state \(in=0,0; out_{valid}=0\) of the first row of Table 11 is represented by the penalty function with \(x_1=x_2=0\) and \(z = 0 = x_1 \wedge x_2\). For this functioning gate, the value of \(P_{valid}+P^*\) is

\[ \begin{align}\begin{aligned}&\overbrace{x_1 x_2 - 2(x_1+x_2)z +3z}^{P_{valid}} + \overbrace{-2\overline{x}_1\overline{x}_2z}^{P^*}\\&= \overbrace{0}^{P_{valid}} + \overbrace{-2 \times 1 \times 1 \times 0}^{P^*}\\&= 0,\end{aligned}\end{align} \]

not penalizing the valid solution. In contrast, the state \(in=0,0; out_{fault}=1\) of the same table row is represented by the penalty function with \(x_1=x_2=0\) and \(z = 1 \ne x_1 \wedge x_2\). For this malfunctioning gate, the value of \(P_{fault}+P^*\) is

\[ \begin{align}\begin{aligned}&\overbrace{x_1 x_2 - 2(x_1+x_2)z +3z}^{P_{fault}} + \overbrace{-2\overline{x}_1\overline{x}_2z}^{P^*}\\&= \overbrace{3}^{P_{fault}} + \overbrace{-2 \times 1 \times 1 \times 1}^{P^*}\\&= 3-2\\&= 1,\end{aligned}\end{align} \]

reducing the energy cost of the original AND gate from \(3\) to \(1\) for the incorrect configuration. For all other states, both valid and faulty, the normalizing penalty, \(P^*\), is zero and has no other affect on the penalty function for AND.

Reformulating Non-Quadratic Penalties as Quadratic

The normalizing penalty introduced in the previous section, \(P^* = -2\overline{in}_1\overline{in}_2out\), is cubic and must be reformulated as quadratic to be mapped onto the native (Ising or QUBO) quadratic formulations used by the D-Wave system.

This example reformulates the normalizing penalty function using the technique of reduction by minimum selection, as described in section Non-Quadratic (Higher-Degree) Polynomials to Ising/QUBO, with the substitution,

\[axyz = aw ( x+y+z -2) \quad a<0,\]

where \(a\) is just a constant that must be negative (and for \(P^*\) equals \(-2\)), \(x,y,z\) are the relevant variables (here \(\overline{in}_1, \overline{in}_2, out\)), and \(w\) an ancillary variable[4] used by this technique to reduce the cubic term, \(xyz\), to a summation of quadratic terms (e.g., \(awx\)).

[4]Similar to ancillary variable \(a\) used in the previous section for the penalty function of the AND gate.

Applying that to \(P^*\), with ancillary variable \(w\) of the general formula renamed to \(b\), gives \(P^q\), a quadratic formulation of the cubic normalizing penalty function:

\[P^*= -2\overline{in}_1\overline{in}_2out \quad \rightarrow P^q = -2b ( \overline{in}_1+\overline{in}_2+out -2)\]

Table 14 shows that the cubic and quadratic formulations of the normalizing penalty function produce identical results. In this table, column \(\mathbf{in_1,in_2,out}\) is all possible states of the gate’s inputs and output; column \(\mathbf{P^*}\) is the corresponding values of the cubic normalizing penalty function, \(P^*= -2\overline{in}_1\overline{in}_2out\); column \(\mathbf{P^q|_{b=0}}\) the values of the quadratic substitute if the ancillary variable \(b=0\) and column \(\mathbf{P^q|_{b=1}}\) the values if \(b=1\); column \(\mathbf{\min_{b}P^q}\) is the value the penalty function adds to the minimized objective function (the minimum penalty of \(\mathbf{P^q|_{b=0}}\) or \(\mathbf{P^q|_{b=1}}\)).

Table 14 Quadratic Normalizing Penalty Function.
\(\mathbf{in_1,in_2,out}\) \(\mathbf{P^*}\) \(\mathbf{P^q|_{b=0}}\) \(\mathbf{P^q|_{b=1}}\) \(\mathbf{\min_{b}P^q}\)
\(0,0,0\) \(0\) \(0\) \(0\) \(0\)
\(0,0,1\) \(-2\) \(0\) \(-2\) \(-2\)
\(0,1,0\) \(0\) \(0\) \(2\) \(0\)
\(0,1,1\) \(0\) \(0\) \(0\) \(0\)
\(1,0,0\) \(0\) \(0\) \(2\) \(0\)
\(1,0,1\) \(0\) \(0\) \(0\) \(0\)
\(1,1,0\) \(0\) \(0\) \(4\) \(0\)
\(1,1,1\) \(0\) \(0\) \(2\) \(0\)

For example, in the table’s first row the AND gate’s inputs are \(in_1,in_2=0,0\), its output is \(out=0\), and the cubic penalty function has a value of zero (as it does for all states except \(in_1,in_2,out=0,0,1\))

\[ \begin{align}\begin{aligned}P^* &= -2\overline{in}_1\overline{in}_2out\\&=-2 \times 1 \times 1 \times 0\\&= 0\end{aligned}\end{align} \]

The quadratic substitute has a value of zero regardless of the value of \(b\)

\[ \begin{align}\begin{aligned}P^q &= -2 \times b \times ( \overline{in}_1+\overline{in}_2+out -2)\\&= -2 \times b \times (1+1+0-2)\\&= 0\end{aligned}\end{align} \]

In the second row, the AND gate’s inputs are \(in_1,in_2=0,0\), its output is \(out=1\), and the cubic penalty function’s value of \(-2\) is activated:

\[ \begin{align}\begin{aligned}P^* &= -2\overline{in}_1\overline{in}_2out\\&=-2 \times 1 \times 1 \times 1\\&= -2\end{aligned}\end{align} \]

The value of the quadratic reformulation depends on the value of \(b\):

\[ \begin{align}\begin{aligned}P^q &= -2b ( \overline{in}_1+\overline{in}_2+out -2)\\P^q|_{b=0} &= -2 \times 0 \times ( 1+1+1 -2) = 0\\P^q|_{b=1} &= -2 \times 1 \times ( 1+1+1 -2) = -2 \times (3-2) = -2\end{aligned}\end{align} \]

When the objective function is minimized, \(b\) is set to \(b=1\) to minimize this term in the objective, resulting in a value of \(\min_{b}P^q=-2\).

Constructing an Objective Function

The (normalized) penalty functions, described in the previous sections, for the three types of gates in the example circuit are:

\[ \begin{align}\begin{aligned}P_{\text{AND}} &= \overbrace{x_1 x_2 - 2(x_1+x_2)z +3z}^{\text{Generic AND}} \overbrace{-2b (\overline{x}_1+\overline{x}_2+y_1 -2)}^{P^q}\\P_{\text{NOT}} &= 2xz-x-z+1\\P_{\text{XOR}} &= 2x_1x_2 -2(x_1+x_2)z - 4(x_1+x_2)a +4az +x_1+x_2+z + 4a\end{aligned}\end{align} \]
image

Fig. 30 The circuit for this example is shown again in Figure 30 with the output formulas of all gates also shown.

The CFD objective function is built by summing the penalty functions of all gates in the circuit:

\[ \begin{align}\begin{aligned}P_1 &= x_1 x_2 - 2(x_1+x_2)y_1 +3y_1 -2b_1 (\overline{x}_1+\overline{x}_2+y_1 -2)\\P_2 &= y_1 x_3 - 2(y_1+x_3)y_2 +3y_2 -2b_2 (\overline{y}_1+\overline{x}_3+y_2 -2)\\P_3 &= y_1 x_3 - 2(y_1+x_3)y_3 +3y_3 -2b_3 (\overline{y}_1+\overline{x}_3+y_3 -2)\\P_4 &= 2y_2x_3 -2(y_2+x_3)z_1 - 4(y_2+x_3)a +4az_1 +y_2+x_3+z_1 + 4a\\P_5 &= 2y_3z_2-y_3-z_2+1\end{aligned}\end{align} \]

where \(P_i\) is the penalty function for gate \(i\) and ancillary variables are as follows:

  • \(y_i\) is the output of AND gate \(i\).
  • \(a\) is the ancillary variable of the generic penalty function for XOR, used here by the penalty function for XOR gate 4.
  • \(b_i\) is the ancillary variable of the generic cubic-to-quartic reduction formula, \(b\), used here by the normalized penalty functions for AND gates 1 to 3.

A few minor adjustments can order these penalty functions in exactly the QUBO form used throughout this guide, \(\text{E}(a_i, b_{i,j}; q_i) = \sum_{i} a_i q_i + \sum_{i<j} b_{i,j} q_i q_j\).

  1. Drop any freestanding constants. These do not affect the energy gap between valid and invalid configurations. In \(P_5\), for example, the \(+1\) term can be removed,
\[P_5 = 2y_3z_2-y_3-z_2\]
  1. Substitute \(\neg x \Leftrightarrow (1-x)\). In \(P_1^N\), for example, use this equivalence to reformulate \(\overline{x_1}\) and \(\overline{x_2}\) introduced by \(P^*\),
\[ \begin{align}\begin{aligned}-2b_1 (\overline{x_1}+\overline{x_2}+y_1 -2) &= -2b_1 [(1-x_1) + (1-x_2) +y_1 - 2]\\&= -2b_1 (-x_1 -x_2 + y_1)\\&= 2b_1x_1 + 2b_1x_2 -2b_1y_1\end{aligned}\end{align} \]
  1. Map the complete set of variables to logical qubits[5]. This section, for example, orders the variables as \(q_i = \{x_1, x_2, x_3, z_1, z_2, y_1, y_2, y_3, a, b_1, b_2, b_3\}_ {i=1}^{12}\).

The reordered penalty functions now have the familiar QUBO form:

\[ \begin{align}\begin{aligned}P_1 &= 3y_1 + x_1 x_2 - 2x_1y_1 +2x_1b_1 -2x_2y_1 + 2x_2b_1 -2y_1b_1\\P_2 &= 3y_2 + x_3y_1 -2x_3y_2 + 2x_3b_2 - 2y_1y_2 +2y_1b_2 -2y_2b_2\\P_3 &= 3y_3 +x_3y_1 - 2x_3y_3 + 2x_3b_3 -2y_1y_3 +2y_1b_3 -2y_3b_3\\P_4 &= x_3 + z_1 + y_2 + 4a - 2x_3z_1 + 2x_3y_2 - 4x_3a - 2z_1y_2 +4z_1a - 4y_2a\\P_5 &= -z_2 -y_3 + 2z_2y_3\end{aligned}\end{align} \]
[5]This is similar to the logical qubits that represented colors (e.g., \(q_B\), the blue qubit) or regions (e.g., \(q_R^{BC}\), the red qubit for British Columbia) in the Simple Map Coloring Problem section. For CFD, these logical qubits represent the values of inputs and outputs to the circuit’s gates. As before, a logical qubit, \(q_i\), might be minor embedded to a single physical qubit \(q_j\) on the QPU or to a chain of qubits.

where, for example, the linear coefficients of \(P_1\) are \(a_6=3\) (and \(a_i=0\) for \(i \not= 6\) because \(3y_1\) is the only non-zero term of \(\sum_{i} a_i q_i\) and \(y_1\) is 6’th[6] in the mapping order used here for \(q_i\)) and the quadratic coefficients are \(b_{1,2}=1, b_{1,6}=-2,\) ... and so on.

[6]This ordering of \(q_i\) is arbitrary; for a different ordering, a different \(a_i\) would be \(3\).

The objective function for this CFD problem is given by,

\[\text{E}(a_i, b_{i,j}; q_i) = P_1 + P_2 + P_3 + P_4 + P_5.\]

To solve the circuit of this example, that is, to find a minimum-sized set of gates that, if faulty, explains the observation of incorrect outputs, this objective function must be minimized while holding constant the input values \(x_1,x_2,x_3=1,1,1\) and incorrect output values \(z_1,z_2=1,0\).

Minor-Embedding the Problem

The Simple Map Coloring Problem example took advantage of the perfect alignment between the structures of problem and Chimera graph in the case of a four-color map problem. Typically these structures do not fortuitously align to such a degree but may do so to a lesser degree for problems with repetitive elements. For CFD problems, as it happens, graph minors of elementary binary operations are embeddable in single Chimera unit cells.

The constituents of the objective function created in the previous sections of this example derived from discrete binary operations plus, for the ANDs, a simple normalizing penalty function. These are all embeddable in single unit cells.

For example, the penalty function for NOT gate 5, \(P_5\), can be represented as a fully connected \(K_2\) graph that can be can be minor embedded onto two logical qubits \(z_2 \rightarrow q_1\) and \(y_3 \rightarrow q2\) of a unit cell,[7]

[7]Note the similarity to the objective function developed in the Simple Map Coloring Problem example, in the two-color case, for a constraint that a region be assigned a single color only. There, the two logical qubits representing colors needed to have different values, which for binary variables means opposite \(0/1\) states. In other words, that constraint enforced a NOT relationship between the qubits.
\[ \begin{align}\begin{aligned}P_5 &= -z_2 -y_3 + 2z_2y_3\\\text{E}_{NOT}(a_i, b_{i,j}; q_i) & = -q_1 - q_2 + 2q_1q_2\end{aligned}\end{align} \]

Represented graphically, this function has two variables, \(q_i\), that correspond to two vertices, \(V_i\), each with a bias, \(a_i\), corresponding to the linear coefficient, \(-1\), and between them an edge, \(E_{12}\), with a coupling strength, \(b_{1,2}\), that corresponds to the quadratic coefficient, \(+2\).

To minor embed the NOT operation onto a QPU, configure two connected qubits with biases \(a_1,a_2=-1,-1\) and a coupling strength \(b_{1,2}=2\).[8]

[8]As described in the Getting Started with the D-Wave System guide, the QPU has an allowed range of values for its biases and strengths. When configuring these values, the values calculated for the problem are scaled to fit those restrictions and other considerations (e.g., the values for variables of the objective function might also be scaled to accommodate the chaining of physical qubits as logical qubits). Consequently, the qubits for a NOT operation might be configured with values \(a_1=a_2=-0.5; b_{1,2}=1\) for example.

Figure 31 shows a minor embedding of a NOT gate into a unit cell of a D-Wave 2000Q QPU, in this case, the topmost left cell of the Chimera graph.

image

Fig. 31 A NOT gate minor embedded into the topmost left unit cell of a D-Wave 2000Q QPU. Logical qubits \(q_1,q_2\), noted in bold, are minor embedded as physical qubits \(q_0,q_4\), represented as a 0 and 4 inside a blue circle, respectively. Biases \(a_1,a_2=-1,-1\) and coupling strength \(b_{1,2}=2\) are also shown.

Similarly the normalized penalty function for AND gates can be minor embedded in different ways. Considering the usefulness of the generic AND gate, one approach might separate the generic AND functionality (one of the formulations provided in the Elementary Boolean Operations to QUBO section of the Reformulating a Problem chapter) from the normalizing penalty, \(P^q\), used for this CFD problem. The generic penalty function for the AND operation can be represented as a fully connected \(K_3\) graph; \(P^q\) can be represented as a sparsely connected \(K_4\) graph.

For example, returning to the penalty functions before they were reordered in the familiar QUBO form, and mapping variables to qubits, \(x_3 \rightarrow q_1, y_1 \rightarrow q_2, y_2 \rightarrow q_3, b_2 \rightarrow q_4\), the penalty function for AND gate 2 is given by,

\[ \begin{align}\begin{aligned}P_2 &= \overbrace{y_1 x_3 - 2(y_1+x_3)y_2 +3y_2}^{\text{Generic AND}} \overbrace{-2b_2 (\overline{y}_1+\overline{x}_3+ y_2 -2)}^{P^q}\\\text{E}(a_i, b_{i,j}; q_i)&= \overbrace{q_2q_1 - 2q_2q_3 -2q_1q_3 +3q_3}^{\text{Generic AND}} + \overbrace{-2q_4[(1-q_2)+(1-q_1)+q_3-2]}^{P^q}\\&= 3q_3 + q_1q_2 -2q_2q_3 - 2q_1 q_3 +2q_1q_4 + 2q_2q_4 -2q_3q_4\end{aligned}\end{align} \]

The biases and coupling strengths are \(a_3,b_{1,2},b_{2,3},b_{1,3}=3,1,-2,-2\) for the generic AND part and \(b_{1,4},b_{2,4},b_{3,4}=2,2,-2\) for the normalizing part.

Figure 32 shows one option for minor embedding the penalty function representing an AND gate and its normalizing penalty function into a Chimera unit cell.

image

Fig. 32 A normalized AND gate represented as a \(K_3\) graph for the generic AND part and its embedding into a Chimera unit cell, on the left, and the normalizing penalty function part and its minor embedding into a Chimera unit cell, on the right. The thick blue line represents a chain of qubits with the biases of the logical qubit divided among the physical qubits as described in the Simple Map Coloring Problem example (that example also explains how to formulate a constraint to create a qubit chain). The common qubits \(q_1,q_2,q_3\) must also be chained across the two unit cells. For readability, the black dots representing logical qubits are labeled with only the bias, \(a_i\), without the matching \(q_i\).

To embed the normalized AND functionality one must chain[9] shared qubits \(q_1, q_2, q_3\) between the two unit cells to ensure identical values.

[9]The Simple Map Coloring Problem example explains chaining for the similar case of cloned regions.

An alternative way to embed the AND gate is to represent the entire normalized penalty as a fully connected \(K_4\) graph, which can be minor embedded onto a single Chimera unit cell, as shown in Figure 33. Similar to the previous embedding of the two parts into two unit cells, the variables are mapped to four logical qubits, \(x_3 \rightarrow q_1, y_1 \rightarrow q_2, y_2 \rightarrow q_3, b_2 \rightarrow q_4\). The objective function is merely a rearranged formulation of the previous one,

\[ \begin{align}\begin{aligned}P_2 &= 3y_2 + x_3y_1 -2x_3y_2 + 2x_3b_2 - 2y_1y_2 +2y_1b_2 -2y_2b_2\\\text{E}_{AND}(a_i, b_{i,j}; q_i) & = 3q_3 + q_1q_2 -2q_1q_3 +2q_1q_4 -2q_2q_3 + 2q_2q_4 -2q_3q_4\end{aligned}\end{align} \]
image

Fig. 33 A normalized AND gate represented as a \(K_4\) graph, on the left, and its minor embedding into a Chimera unit cell, on the right. The thick blue line represents a chain of qubits. For readability, these graphics are only partly labeled.

Analogously to these two ways of minor embedding AND gate 2, minor embedding a CFD problem can differently group the parts of its objective function.

The intuitively simplest way might be to minor embed each gate in a unit cell and then chain shared variables. For example, the output of AND gate 2 feeds into the input of NOT gate 5 as \(y_2\). Mapping variables to logical qubits,

\[ \begin{align}\begin{aligned}NOT: & \qquad z_2 \rightarrow q^N_1 & \qquad y_3 \rightarrow q^N_2\\AND: & \qquad x_3 \rightarrow q^A_1 & \qquad y_1 \rightarrow q^A_2 & \qquad y_3 \rightarrow q^A_3 & \qquad b_2 \rightarrow q^A_4\end{aligned}\end{align} \]

where superscripts \(A\) and \(N\) denote the AND and NOT parts, respectively (this is the only change to the following objective functions from their previous appearances in this section). The objective functions for the combined AND gate 2 and NOT gate 5 is given by,

\[ \begin{align}\begin{aligned}P_2 &= 3y_2 + x_3y_1 -2x_3y_2 + 2x_3b_2 - 2y_1y_2 +2y_1b_2 -2y_2b_2\\\text{E}_{AND}(a^A_i, b^A_{i,j}; q^A_i) & = 3q^A_3 + q^A_1q^A_2 -2q^A_1q^A_3 +2q^A_1q^A_4 -2q^A_2q^A_3 + 2q^A_2q^A_4 -2q^A_3q^A_4\\P_5 &= -z_2 -y_3 + 2z_2y3\\\text{E}_{NOT}(a^N_i, b^N_{i,j}; q^N_i) & = -q^N_1 - q^N_2 + 2q^N_1q^N_2\end{aligned}\end{align} \]

The embedding needs to ensure that \(y_3=q^N_2=q^A_3\).

Figure 34 shows a possible minor embedding of AND gate 3 and NOT gate 5 with each in its own Chimera unit cell.

image

Fig. 34 A minor embedding of AND gate 3 and NOT gate 5 with each in its own Chimera unit cell. AND gate 3 is minor embedded in the top leftmost unit cell of a D-Wave 2000Q QPU; NOT gate 5 is minor embedded in the neighboring unit cell. Qubits \(q^N_2\) and \(q^A_3\) are chained into a single logical qubit.

However, a less wasteful way to minor embed these gates is to combine them in a single unit cell, as shown in Figure 35.

image

Fig. 35 A minor embedding of AND gate 3 and NOT gate 5 in a single Chimera unit cell, the top leftmost unit cell of a D-Wave 2000Q QPU. AND gate 3 is minor embedded in the lower 6 qubits; NOT gate 5 is minor embedded in the top two qubits. Qubits \(q^N_2\) and \(q^A_3\) are chained into a single logical qubit.

Scalable, Tool-Assisted Formulation and Minor-Embedding

The manual formulations and minor embeddings of the preceding sections can be effective but also time-consuming for large problems. As described in the Software Environment and Tools chapter, D-Wave offers tools that can automate some of the solution steps to speed and scale up the process.

For example, penalty functions can be created using an SMT solver. Depending on the software used, deriving a penalty function for NOT gate 5 in this example may include commands like the following:

import penaltymodel as pm
import penaltymodel_maxgap as maxgap
import networkx as nx
import dwave_networkx as dnx

FAULT_GAP = .5

NOT_5 = fault_gate({(-1, +1): 0, (+1, -1): 0}, FAULT_GAP)

G5 = dnx.chimera_graph(1)
G5 = nx.relabel_nodes(G5, {4: 'z2', 5: 'a3', 0: 'f5'})

spec = pm.Specification(G5, ['a3', 'z2', 'f5'], NOT_5, pm.SPIN)
pmodel = maxgap.get_penalty_model(spec)

print('h:', pmodel.model.linear)
print('J:', pmodel.model.quadratic)
print('classical_gap:', pmodel.classical_gap)

In this particular code snippet, Ising is the chosen native formulation, the output of NOT gate 5, \(z2\), is assigned to node 4 of the graph minor to be embedded, and an ancillary variable representing the gate’s input (equivalent to \(y_3\) in the previous sections), \(a3\), to node 5. Variable \(f5\), assigned to node 0, indicates whether the gate is faulty or functioning. The model is configured with valid states representing a NOT operation in spins: Boolean \(in=0 \rightarrow out=1\) is \((-1, +1)\) and Boolean \(in=1 \rightarrow out=0\) is \((+1, -1)\). Any other state is therefore a fault.

The output from this particular tool may look like the following:

h: {1: -0.265625, 2: -1.0, 3: -0.9, 6: -0.1875, 7: 0.903125,
'z2': -0.865625, 'f5': -0.740625, 'a3': -0.13125}
J: {(2, 7): -1.0, (2, 6): -0.0125, (3, 7): 0.103125, (2, 'z2'): 0.990625,
(2, 'a3'): -0.996875, (7, 'f5'): -1.0, (3, 'a3'): 1.0, ('f5', 'a3'): 0.128125,
(3, 'z2'): 1.0, (1, 6): -0.003125, (1, 'z2'): -0.2625, (3, 6): -0.996875,
(1, 7): -1.0, (6, 'f5'): 1.0, ('z2', 'f5'): 0.1375, (1, 'a3'): 1.0}
classical_gap: 2.5

In the Ising model, \(h_i\) is a linear coefficient representing the bias of a qubit and \(J_{i,j}\) is a quadratic coefficient representing a coupling between two qubits. The output \(h: \{1: -0.265625, 2: -1.0,\) means that qubit 1 has a bias of about \(-0.265\), qubit 2 a bias of \(-1\) and so on; the output \(J: \{(2, 7): -1.0, (2, 6): -0.0125,\) means the coupler between qubits 2 and 7 has a strength of \(-1\), the coupler between qubits 2 and 6 a strength of \(-0.0125\) and so on.

The software tool used for this CFD example created for each gate an Ising penalty function suited for minor embedding in a single Chimera unit cell and optimized for a large energy gap. The tool then used chains of qubits to interconnect qubits representing the problem’s variables across unit cells. Figure 36 shows this minor embedding in the Chimera of a D-Wave 2000Q QPU.

image

Fig. 36 A minor embedding of this example’s CFD problem derived from a software tool. Each Boolean gate is minor embedded into a unit cell; the interconnecting qubit chains are highlighted in blue.