Main Content

qubo

Quadratic Unconstrained Binary Optimization

Since R2023a

expand all in page

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(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+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

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 = [].

example

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(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+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(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+d.

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

f(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+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(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+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(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+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(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+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

evaluateObjectiveEvaluate QUBO (Quadratic Unconstrained Binary Optimization) objective
solveSolve 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

Q=[0−12−104240]c=[−56−4]d=12.

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

See Also

| |

Topics