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

Both are implemented as examples under Getting Started with Ocean software.

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

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

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

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.

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, and Ocean software provides tools such as D-Wave Binary CSP. 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

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.

\(\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

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

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.

\(\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\),

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 22
depicts the map-coloring problem as a graph, where each
region is a node (vertex) and adjacent borders are edges.

The Minor-Embedding a Problem chapter describes various methods for embedding a given problem, and Ocean software provides tools for automatic embedding such as those in dwave-system and minorminer. 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 23 shows the constraints of the previous C=2, 3, 4 map-coloring problems as graphs.

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

#### 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 25, representing each logical qubit as a chain of two physical qubits enables full connectivity between the four.

#### 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 25) has an objective of the form:

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

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.

\(\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 25), 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 27: 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.

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:

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 21). 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 27, 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 28 shows the use of cloned regions to enable coupling of all neighboring regions in Canada’s map.

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 21. 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, and Ocean software provides tools such as D-Wave Hybrid . 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 29 shows a solution to coloring a map of the United States, which ran on the D-Wave 2000Q in two manageable chunks.

### 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:

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

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

These constraints give a QUBO,

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.
- Ocean software examples: Large Map Coloring and Map Coloring.

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

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,

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.

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.

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

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:

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:

- 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.
- 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.)
- 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.
- 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. Ocean software provides tools such as D-Wave Binary CSP that implement penalty models for standard Boolean gates.

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).¶ **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.

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.

¶ **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.

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}}\)).¶ **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.

¶ **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,

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,

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

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

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

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,

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\)). Ocean software provides tools such as dimod that implement polynomial reduction.

[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:

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

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

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

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:

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

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:

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

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

- 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,

- 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^*\),

- 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:

[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,

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

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

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,

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 34 shows one option for minor embedding the penalty function representing an AND gate and its normalizing penalty function into a Chimera unit cell.

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 35. 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,

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,

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,

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

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

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

### 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, several examples under Getting Started with Ocean software use Boolean gates provided as part of the Ocean SDK. Penalty functions can also 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 38 shows this minor embedding in the Chimera of a D-Wave 2000Q QPU.