solve

Solve QUBO (Quadratic Unconstrained Binary Optimization) problem

Since R2023a

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

Syntax

result = solve(qprob)

result = solve(qprob,Algorithm=algo)

Description

result = solve(qprob) searches for a solution result to qprob, a QUBO problem, using the default tabuSearch algorithm.

result = solve(qprob,Algorithm=algo) solves the QUBO problem using the specified algorithm. algo can be a tabuSearch object or a qaoa object.

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]

Modify Tabu Search

Create a QUBO problem.

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

Create a tabu search object that displays iterations and limits the stall time to 0.02s.

ts = tabuSearch(Display="iter",MaxStallTime=0.02);

Solve the QUBO problem using the tabu search object.

result = solve(qprob,Algorithm=ts)

Tabu call    Best fval   Stall time   Tabu iterations
        0           11            0           0
        1            7      0.00183         307
        2            7     0.003807         301
        3            7     0.005716         301
        4            7     0.006596         301
        5            7     0.007519         301
        6            7     0.008222         301
        7            7     0.009088         301
        8            7     0.009855         301
        9            7      0.01066         301
       10            7      0.01135         301
       11            7      0.01201         301
       12            7      0.01268         301
       13            7      0.01333         301
       14            7        0.014         301
       15            7      0.01469         301
       16            7      0.01537         301
       17            7      0.01603         301
       18            7      0.01669         301
       19            7      0.01977         301
       20            7       0.0205         301

TabuSearch stopped because MaxStallTime is exceeded.

result = 
  quboResult with properties:

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

Tabu search is a stochastic algorithm, so your results might vary.

Solve QUBO Using QAOA

Create a QUBO problem.

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

Create a structure using the optimset function that specifies a maximum of 1000 iterations.

opts = optimset(MaxIter=1e3);

Create a qaoa object that sets the number of cost-mixer layer pairs to 3 and the number of shots to 150. Also specify additional optimization solver options by setting OptimizationSolverOptions to opts.

qa = qaoa(NumLayers=3,NumShots=150,OptimizationSolverOptions=opts);

Solve the QUBO problem using the qaoa object.

result = solve(qprob,Algorithm=qa)

 
Exiting: Maximum number of function evaluations has been exceeded
         - increase MaxFunEvals option.
         Current function value: -2.573333 

result = 
  quboResult with properties:

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

Input Arguments

qprob — QUBO problem

qubo object

QUBO problem, specified as a qubo object. Create qprob using the qubo function.

algo — Optimization algorithm

tabuSearch object (default) | qaoa object

Optimization algorithm, specified as one of these objects:

• tabuSearch object — Use the tabu search algorithm. Set algorithm properties using the tabuSearch function.

• qaoa object — Use the quantum approximate optimization algorithm. Set algorithm properties using the qaoa function.

This argument determines the type of object stored in the AlgorithmResult property of the resulting quboResult object.

Example: To run the tabu search algorithm for no more than 60 seconds, set ts = tabuSearch(MaxTime=60) and then call solve(qprob,Algorithm=ts).

Output Arguments

result — Solution of QUBO problem

quboResult object

Solution of the QUBO problem, returned as a quboResult object. result contains the following properties:

• BestX — Solution point corresponding to the minimum objective function value, returned as a real vector.

• BestFunctionValue — Objective function value corresponding to BestX, returned as a real scalar. Generally, BestFunctionValue = evaluateObjective(qprob,BestX).

• AlgorithmResult — Result details, returned as a tabuSearchResult object or a qaoaResult object.

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, Gintaras. "Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem." Informatica 17, no. 2 (2006): 279–96. https://doi.org/10.15388/Informatica.2006.138.

Version History

Introduced in R2023a

R2024b: Specify algorithm as QAOA

When solving a QUBO problem using solve, you can specify the algorithm as QAOA (quantum approximate optimization algorithm). The AlgorithmResult property of the resulting quboResult object contains a qaoaResult object.