Workflow for QUBO Problems

Note

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

A Quadratic Unconstrained Binary Optimization (QUBO) problem is a quadratic optimization problem in binary variables. For background information, see What Is a QUBO Problem?

To solve a QUBO problem, you first need to convert your problem to QUBO, and then solve it using the tabu search algorithm.

Convert Problem to QUBO

The solve function solves problems represented in QUBO form. For x(i), a binary variable with N components, a QUBO objective function has the form

$f (x) = \sum_{i = 1}^{N} \sum_{j = 1}^{N} Q_{i, j} x_{i} x_{j} + \sum_{i = 1}^{N} c_{i} x_{i} + d .$

To express your problem as a QUBO, create a real N-by-N matrix Q, an optional N vector c, and an optional scalar d. Then create the QUBO problem as follows:

qprob = qubo(Q,c,d); % Or qprob = qubo(Q) or qprob = qubo(Q,c)

For more information, including how to convert between QUBO form and Ising form, see What Is a QUBO Problem?

Some problems have constraints that you express as a penalty term in the QUBO objective function. See Constraints in QUBO Problems.

Solve Problem Using Tabu Search

Call solve on the QUBO to find a solution using the tabu search algorithm. The solve syntax is:

result = solve(qprob)

Tabu search is a stochastic algorithm, so each time you run the algorithm, you might get a different result. If you add constraints to a problem by using a penalty term, and the first solution you get is infeasible, you can try to find a feasible solution by rerunning solve.

You can control some aspects of solve by creating a tabu search algorithm object, which contains properties for the tabu search. Pass the tabu search object with specified properties to solve. For example, to have solve use more time and iterations than the defaults, enter

ts = tabuSearch(MaxTime=60,MaxIterations=1e7);
result = solve(qprob,Algorithm=ts)

For details about the properties and their default values, see tabuSearch.

When your problem has constraints expressed as a penalty term, some results might violate the constraints. See Examine Solutions for Feasibility.

Alternative Solution for Simple Problems Using Optimization Toolbox

If your QUBO problem has only a few variables (up to perhaps 100 or 200), and you have an Optimization Toolbox™ license, convert the QUBO to a mixed-integer linear problem and solve it using intlinprog. The advantage of using intlinprog is that the resulting solution is guaranteed to be optimal. The disadvantages are that the size of the problem is limited, and the solver can take a long time to finish. For details, see Verify Optimality by Solving QUBO as MILP.