Main Content

qaoa

Quantum approximate optimization algorithm (QAOA) for solving QUBO problem

Since R2024b

expand all in page

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

    Description

    You can use the quantum approximate optimization algorithm (QAOA) to solve a Quadratic Unconstrained Binary Optimization (QUBO) problem. To solve a QUBO problem using QAOA, use the solve function with Algorithm set to a qaoa object.

    For example, create a qaoa object with the number of shots set to 150. Create a QUBO problem and then solve it using that qaoa object.

    qa = qaoa(NumShots=150);
qprob = qubo(Q,c,d);
result = solve(qprob,Algorithm=qa);

    Creation

    Syntax

    qa = qaoa
    qa = qaoa(PropertyName=Value)

    Description

    qa = qaoa creates a default qaoa object.

    qa = qaoa(PropertyName=Value) sets properties using one or more name-value arguments. For example, to change the QAOA optimization solver to fmincon, use qa = qaoa(OptimizationSolver="fmincon").

    example

    Properties

    expand all

    Optimization Properties

    Initial angles (in radians) passed to the optimization solver, specified as a 2-by-NumLayers matrix. The first row corresponds to the cost gate angles, and the second row corresponds to the mixer gate angles. For more information on the QAOA optimization process, see Algorithms.

    Optimization solver, specified as one of these values:

    • "fminsearch" — Search for a local minimum of an unconstrained multivariable function using a derivative-free method. For more information, see fminsearch.

    • "fmincon" — Search for the minimum of a constrained nonlinear multivariable function. This option requires Optimization Toolbox™. For more information, see fmincon (Optimization Toolbox).

    • "surrogateopt" — Search for the global minimum of a real-valued, time-consuming objective function using surrogate optimization. This option requires Global Optimization Toolbox™. For more information, see surrogateopt (Global Optimization Toolbox).

    Optimization solver options, specified as one of these values:

    • struct created using optimset, when the optimization solver is fminsearch

    • optim.options.Fmincon object created using optimoptions (Optimization Toolbox), when the optimization solver is fmincon (Optimization Toolbox)

    • optim.options.Surrogateopt object created using optimoptions (Optimization Toolbox), when the optimization solver is surrogateopt (Global Optimization Toolbox)

    Example: qa.OptimizationSolverOptions = optimset(maxFunEvals=200) sets the maximum number of function evaluations to 200.

    Circuit Properties

    Number of cost-mixer layer pairs, specified as a positive integer.

    Number of shots to estimate the objective function, specified as a positive integer. The number of shots is how many times the circuit is measured on each iteration of the solver.

    Examples

    collapse all

    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]

    Algorithms

    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.

    Version History

    Introduced in R2024b

    See Also

    Functions

    Objects

    Topics