Main Content

solve

Solve QUBO (Quadratic Unconstrained Binary Optimization) problem

Since R2023a

collapse all in page

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.

example

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

example

Examples

collapse all

This example uses:

Open Live Script

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

This example uses:

Open Live Script

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

TabuSearch stopped because MaxStallTime is exceeded.

result = 
  quboResult with properties:

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

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

This example uses:

Open Live Script

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

collapse all

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

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

collapse all

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

expand all

See Also

| | |

Topics