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(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.}$$

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.

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

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

Q — Quadratic term for the objective function

real matrix

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

$$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.}$$

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

c — Linear term for objective function

real vector

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

$$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.}$$

d — Constant term for objective function

real scalar

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

$$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.}$$

Properties

QuadraticTerm — Quadratic term for objective function

real symmetric matrix

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)={\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.}$$

This property is set by the Q input argument.

LinearTerm — Linear term for objective function

real vector

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

$$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.}$$

This property is set by the c input argument.

ConstantTerm — Constant term for objective function

real scalar

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

$$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.}$$

This property is set by the d input argument.

NumOfVariables — Number of problem variables

positive integer

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

Create and Solve QUBO Problem

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

$\begin{array}{l}\mathit{Q}=\left[\begin{array}{ccc}0& -1& 2\\ -1& 0& 4\\ 2& 4& 0\end{array}\right]\\ \mathit{c}=\left[\begin{array}{ccc}-5& 6& -4\end{array}\right]\\ \mathit{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: [3×1 double]
     ConstantTerm: 12
     NumVariables: 3

Solve the problem using the default 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 [2]. 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.

• QAOA is a quantum-classical hybrid approach to solving optimization problems. In general, a quantum circuit represents possible solutions to the problem and a classical optimizer iteratively adjusts the angles in the circuit to improve the quality of the solution. The quantum circuit uses alternating layers of cost and mixer gates to approximately solve the provided problem. For details, see Solve Max-Cut Problem Using QAOA.

References

[1] Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann. “A Quantum Approximate Optimization Algorithm.” arXiv, November 14, 2014. https://doi.org/10.48550/arXiv.1411.4028.

[2] 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