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.
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:
- 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.
- Develop a QUBO that favors the desired states and penalizes other states.
- 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:
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
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:
Taking a closer look at the squared expression,
we can see that because the variables are binary (0 or 1),
our objective function becomes the quadratic 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.
When expressed as a QUBO, we obtain