# Using QUBOs to Represent Constraints¶

We can use QUBOs to define simple constraints that are important building blocks for larger, more complex problems. The exactly-one-true constraint is a Boolean satisfiability problem in which we want to know, given a set of variables, when exactly one variable equals 1 (is TRUE).

For example, when optimizing a traveling salesperson’s route through a series of cities, we need a constraint forcing the salesperson to be in exactly one city at each stage of the trip: a solution that puts the salesperson in two or more places at once is invalid. Fig. 23 The traveling salesperson problem is an optimization problem that can be solved using exactly-one-true constraints. Map data © 2017 GeoBasis-DE/BKG (© 2009), Google.

This chapter describes how to construct a simple exactly-one-true constraint in a form that the D-Wave system can solve. It covers the following steps:

1. Start with the objective: in this case, start with an exactly-one-true constraint with 3 variables and build a truth table that satisfies this objective.
2. Develop a QUBO that favors the desired states and penalizes other states.
3. Convert the QUBO into a graph.

## Build a Truth Table for the Objective Function¶

Consider a simple example: Given three variables $a$, $b$, and $c$, we want to know when exactly one variable is 1. (That is, when only one of $a$, $b$, and $c$ equals 1; the other two are 0.) This translates into the following truth table:

$a$ $b$ $c$ Exactly 1
0 0 0 FALSE
1 0 0 TRUE
0 1 0 TRUE
1 1 0 FALSE
0 0 1 TRUE
1 0 1 FALSE
0 1 1 FALSE
1 1 1 FALSE

## Develop a QUBO Favoring States with One True¶

We want to find a function $E(a,b,c)$ that is at a minimum when this objective is true. We can express this as

\begin{equation} a + b + c = 1 \end{equation}

or as

\begin{equation} a + b + c -1 = 0. \end{equation}

The problem with the second expression above is that when $a$, $b$, and $c$ are all 0, we get a result of $-1$, which is a lower energy than the TRUE states. The solution is to square the original equation:

\begin{equation} (a + b + c - 1)^2. \end{equation}

Taking a closer look at the squared expression,

\begin{equation} E(a,b,c)=(a+b+c-1)^2 \end{equation}

we can see that because the variables are binary (0 or 1),

\begin{equation} a^2 = a \end{equation}

our objective function becomes the quadratic equation

\begin{equation} E(a,b,c) = 2ab + 2ac + 2bc - a - b - c + 1 \end{equation}

where the energy of the function $E(a,b,c)$ is the value of the objective function.

Let’s look at the truth table again, this time adding a column to show the energy. Note that the lowest energy states are those that match our exactly-one-true constraint. Remember that the better the solution, the lower the energy.

$a$ $b$ $c$ Exactly 1 Energy
0 0 0 FALSE 1
1 0 0 TRUE 0
0 1 0 TRUE 0
1 1 0 FALSE 1
0 0 1 TRUE 0
1 0 1 FALSE 1
0 1 1 FALSE 1
1 1 1 FALSE 4

When expressed as a QUBO, we obtain

\begin{equation} E(x_0, x_1, x_2) = 2 x_0 x_1 + 2 x_0 x_2 + 2 x_1 x_2 - x_0 - x_1 - x_2 + 1. \end{equation}

## Convert the QUBO into a Graph¶

The QUBO energy function can be represented by the triangular graph shown in Figure 24. Each binary variable becomes a node biased with its linear coefficient. Each quadratic term becomes an edge between the nodes. Fig. 24 Triangular graph showing biased nodes and edges.