3.4 Combinatorial optimization problems with the QUBO model
In this final section of the chapter, we are going to introduce some techniques that will allow us to write many important optimization problems as QUBO and Ising instances, so we can later solve them with different quantum algorithms. These examples will also help you understand how to formulate your own optimization problems under these models, which is the first step in order to be able to use quantum computers to solve them.
3.4.1 Binary linear programming
Binary linear programming problems involve optimizing a linear function on binary variables subject to linear constraints. Thus, the general form is
where are integer coefficients, is an integer matrix, is the transpose of , and is an integer column vector.
An example of this type of problem could be the following:
Binary linear programming (also known as zero-one linear programming) is -hard. In fact, the decision version in which the goal is to determine if there...
