# qubo

Quadratic Unconstrained Binary Optimization

Since R2023a

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

## Description

A Quadratic Unconstrained Binary Optimization (QUBO) problem for a binary vector x with N components is to minimize the objective function

`$f\left(x\right)=\sum _{i=1}^{N}\sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}+\sum _{i=1}^{N}{c}_{i}{x}_{i}+d.$`

Create a QUBO problem by specifying the Q matrix, c vector, and d scalar value.

## Creation

### Syntax

``qprob = qubo(Q)``
``qprob = qubo(Q,c)``
``qprob = qubo(Q,c,d)``

### Description

example

````qprob = qubo(Q)` returns a QUBO problem object with quadratic term `Q`, and sets the QuadraticTerm property.```

example

````qprob = qubo(Q,c)` returns a QUBO problem with quadratic term `Q` and linear term `c`, and sets the LinearTerm property.```

example

````qprob = qubo(Q,c,d)` returns a QUBO problem with quadratic term `Q`, linear term `c`, and constant term `d`, and sets the ConstantTerm property. If the problem has no linear term, set `c = []`.```

### Input Arguments

expand all

Quadratic term for the objective function, specified as a real matrix. The `Q` argument represents the Q matrix in the objective function

`$f\left(x\right)=\sum _{i=1}^{N}\sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}+\sum _{i=1}^{N}{c}_{i}{x}_{i}+d.$`

If Q is not symmetric, the software replaces Q with the equivalent symmetric matrix (Q + QT)/2.

Linear term for the objective function, specified as a real vector. The `c` argument represents the c vector in the objective function

`$f\left(x\right)=\sum _{i=1}^{N}\sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}+\sum _{i=1}^{N}{c}_{i}{x}_{i}+d.$`

Constant term for the objective function, specified as a real scalar. The `d` argument represents the d scalar in the objective function

`$f\left(x\right)=\sum _{i=1}^{N}\sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}+\sum _{i=1}^{N}{c}_{i}{x}_{i}+d.$`

## Properties

expand all

Quadratic term for the objective function, returned as a real symmetric matrix. The `QuadraticTerm` property represents the Q matrix in the objective function

`$f\left(x\right)=\sum _{i=1}^{N}\sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}+\sum _{i=1}^{N}{c}_{i}{x}_{i}+d.$`

This property is set by the `Q` input argument.

Linear term for the objective function, returned as a real vector. The `LinearTerm` property represents the c vector in the objective function

`$f\left(x\right)=\sum _{i=1}^{N}\sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}+\sum _{i=1}^{N}{c}_{i}{x}_{i}+d.$`

This property is set by the `c` input argument.

Constant term for the objective function, returned as a real scalar. The `ConstantTerm` property represents the d scalar in the objective function

`$f\left(x\right)=\sum _{i=1}^{N}\sum _{j=1}^{N}{Q}_{i,j}{x}_{i}{x}_{j}+\sum _{i=1}^{N}{c}_{i}{x}_{i}+d.$`

This property is set by the `d` input argument.

This property is read-only.

Number of problem variables, returned as a positive integer. `NumOfVariables` is equal to `size(Q,1)`.

Example: `3`

## Object Functions

 `evaluateObjective` Evaluate QUBO (Quadratic Unconstrained Binary Optimization) objective `solve` Solve QUBO (Quadratic Unconstrained Binary Optimization) problem

## Examples

collapse all

Create a QUBO problem for the quadratic matrix `Q`, linear vector `c`, and constant term `d`, where

`$\begin{array}{c}Q=\left[\begin{array}{ccc}0& -1& 2\\ -1& 0& 4\\ 2& 4& 0\end{array}\right]\\ c=\left[\begin{array}{ccc}-5& 6& -4\end{array}\right]\\ d=12.\end{array}$`

```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```

## Algorithms

The tabu search algorithm is based on Palubeckis [1]. Starting from a random binary vector, the software repeatedly attempts to find a binary vector with a lower objective function value by switching some existing values from 1 to 0 or from 0 to 1. The software tries to avoid cycling, or the repeated evaluation of the same point, by using a tabu list. For details, see Tabu Search Algorithm.

## References

[1] Palubeckis, G. Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem. Informatica (2006), 17(2), pp. 279–296. Available at https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3c323a1d41cd0e2ca1ddb27192e475ea73959e52.

## Version History

Introduced in R2023a