What Is a QUBO Problem?

Note

Installation Required: This functionality requires MATLAB Support Package for Quantum Computing.

QUBO and Ising Problem Definitions

A Quadratic Unconstrained Binary Optimization (QUBO) problem is a quadratic optimization problem in binary variables. For x(i), a binary variable with N components, the objective function to minimize has the form

$f (x) = \sum_{i = 1}^{N} \sum_{j = 1}^{N} Q_{i, j} x_{i} x_{j} + \sum_{i = 1}^{N} c_{i} x_{i} + d .$

Q can be a real symmetric matrix. If Q is not symmetric, the software internally replaces Q with the equivalent symmetric matrix
$\hat{Q} = \frac{Q + Q^{'}}{2}$
for the expression
$x' \overset{⌢}{Q} x = x' Q x .$
c is a numeric vector with N components.
d is a scalar.

Convert your problem to a QUBO problem by using the qubo function.

qprob = qubo(Q)
% or
qprob = qubo(Q,c)
% or
qprob = qubo(Q,c,d)

An Ising problem has the same formulation as a QUBO problem, except the Ising variables y(i) are ±1 instead of the QUBO x variables 0 or 1. You can convert between the two formulations using a linear mapping. For a QUBO problem represented with variable x and an Ising problem with variable y, the mapping is

$\begin{array}{l} y = 2 x - 1 \\ x = \frac{y + 1}{2} . \end{array}$

The objective function values in the two formulations differ by an easily calculated amount.

$\begin{matrix} x' Q x + c' x + d = \frac{(y + 1)' Q (y + 1)}{4} + c' (\frac{y + 1}{2}) + d \\ = \frac{y' Q y}{4} + (\frac{1' Q + c'}{2}) y + d + \frac{1' Q 1}{4} + \frac{c' 1}{2}, \end{matrix}$

where 1 represents the column vector of ones having the same length as y.

QUBO Problem Application

As explained in Glover, Kochenberger, and Du [1], many combinatorial optimization problems, such as the Traveling Salesperson Problem and quadratic assignment problems, can be formulated as QUBO problems. For a set of techniques to formulate common combinatorial optimization problems into this framework, see Lucas [2].

Also, many current and proposed quantum computers use QUBO or Ising as the problem type. To try to find a quantum solution to a combinatorial optimization problem, you formulate a QUBO problem and then pass the problem to quantum hardware for the solution.

Solution Methods

To solve a QUBO problem, perform these two steps.

Place your problem into a QUBO object by calling qubo.
Solve the QUBO by calling solve, which uses the tabu search algorithm.

For example, create a QUBO problem for the quadratic matrix Q, linear vector c, and constant term d.

Q = [0 -1 2;...
    -1 0 4;...
    2 4 0];
c = [-5 6 -4];
d = 12;
qprob = qubo(Q,c,d)

qprob = 

  qubo with properties:

    QuadraticTerm: [3×3 double]
       LinearTerm: [-5 6 -4]
     ConstantTerm: 12
     NumVariables: 3

Solve the problem using the tabu search algorithm.

result = solve(qprob)

result = 

  quboResult with properties:

                BestX: [3×1 double]
    BestFunctionValue: 7
      AlgorithmResult: [1×1 tabuSearchResult]

Alternatively, if you have an Optimization Toolbox™ license and your problem has up to 100 or 200 variables, convert the QUBO problem to a mixed-integer linear programming (MILP) problem and solve it using intlinprog, as shown in Verify Optimality by Solving QUBO as MILP.

References

[1] Glover, Fred, Gary Kochenberger, and Yu Du. Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models. Available at https://arxiv.org/abs/1811.11538.

[2] Lucas, Andrew. Ising formulations of many NP problems. Available at https://arxiv.org/pdf/1302.5843.

[3] Kochenberger, G. A., and F. Glover. A Unified Framework for Modeling and Solving Combinatorial Optimization Problems: A Tutorial. In: Hager, W. W., Huang, S. J., Pardalos, P. M., Prokopyev, O. A. (eds) Multiscale Optimization Methods and Applications. Nonconvex Optimization and Its Applications, vol 82. Springer, Boston, MA. https://doi.org/10.1007/0-387-29550-X_4. Available at https://www.researchgate.net/publication/226808473_A_Unified_Framework_for_Modeling_and_Solving_Combinatorial_Optimization_Problems_A_Tutorial.