## 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)={\displaystyle \sum _{i=1}^{N}{\displaystyle \sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}}+{\displaystyle \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$$\widehat{Q}=\frac{Q+{Q}^{\prime}}{2}$$

for the expression

$$x\text{'}\stackrel{\u2322}{Q}x=x\text{'}Qx.$$

*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=2x-1\\ x=\frac{y+1}{2}.\end{array}$$

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

$$\begin{array}{c}x\text{'}Qx+c\text{'}x+d=\frac{(y+1)\text{'}Q(y+1)}{4}+c\text{'}\left(\frac{y+1}{2}\right)+d\\ =\frac{y\text{'}Qy}{4}+\left(\frac{1\text{'}Q+c\text{'}}{2}\right)y+d+\frac{1\text{'}Q1}{4}+\frac{c\text{'}1}{2},\end{array}$$

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.