Quadratic Unconstrained Binary Optimization (QUBO)

Quadratic Unconstrained Binary Optimization (QUBO) for combinatorial optimization problems
Since R2023a

Many combinatorial optimization problems can be formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. These problems include the Traveling Salesperson Problem with QUBO, Capacitated Vehicle Routing Problem, and Feature Selection QUBO (Quadratic Unconstrained Binary Optimization). For background information, see What Is a QUBO Problem?

Also, many current and proposed quantum computers use QUBO (or equivalent Ising) as the problem type. To attempt a quantum solution to a combinatorial optimization problem, you formulate a QUBO problem and then pass the problem to quantum hardware for the solution. Currently, the MATLAB^® Support Package for Quantum Computing does not directly support any quantum hardware for solving QUBO problems.

Objects

`qubo`	Quadratic Unconstrained Binary Optimization
`quboResult`	Result of solving QUBO problem
`tabuSearch`	Tabu search algorithm for `QUBO` `solve`
`tabuSearchResult`	Result of `solve` for Tabu search algorithm
`qaoa`	Quantum approximate optimization algorithm (QAOA) for solving QUBO problem (Since R2024b)
`qaoaResult`	Result of solving QUBO problem using QAOA (Since R2024b)

Functions

`evaluateObjective`	Evaluate QUBO (Quadratic Unconstrained Binary Optimization) objective
`solve`	Solve QUBO (Quadratic Unconstrained Binary Optimization) problem
`maxcut2qubo`	Convert max-cut problem to QUBO (Quadratic Unconstrained Binary Optimization) (Since R2024b)

Topics

What Is a QUBO Problem?
This topic introduces the basics of Quadratic Unconstrained Binary Optimization (QUBO) problems.
Workflow for QUBO Problems
Learn the steps for formulating and solving a QUBO problem.
Constraints in QUBO Problems
Include constraints in a QUBO problem by adding penalty terms.
Tabu Search Algorithm
Learn about the tabu search heuristic algorithm used to solve QUBO problems.
Verify Optimality by Solving QUBO as MILP
Convert a QUBO problem to a mixed-integer linear programming (MILP) problem, and solve the problem using intlinprog.
Traveling Salesperson Problem with QUBO
Convert a Traveling Salesperson Problem (TSP) to a QUBO problem and solve the problem.
Capacitated Vehicle Routing Problem
Express and solve a capacitated vehicle routing problem using QUBO.
Feature Selection QUBO (Quadratic Unconstrained Binary Optimization)
Find the most relevant predictors in a data set using a QUBO problem formulation.

Featured Examples

Solve Max-Cut Problem Using QAOA

Use the Quantum Approximate Optimization Algorithm (QAOA) to solve max-cut problems.

Open Live Script