solve

求解 QUBO（二次无约束二元优化）问题

自 R2023a 起

全页折叠

安装要求：此功能需要 MATLAB Support Package for Quantum Computing。

语法

result = solve(qprob)
result = solve(qprob,Algorithm=algo)

说明

result = solve(qprob) 使用默认 tabuSearch 算法搜索 qprob（一个 QUBO 问题）的解 result。

示例

result = solve(qprob,Algorithm=algo) 使用指定的算法求解 QUBO 问题。algo 可以是 tabuSearch 对象或 qaoa 对象。

示例

示例

全部折叠

此示例使用:

打开实时脚本

为二次矩阵 Q、线性向量 c 和常数项 d 创建一个 QUBO 问题，其中

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

使用默认禁忌搜索算法求解问题。

result = solve(qprob)
result = 
  quboResult with properties:

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

此示例使用:

打开实时脚本

创建一个 QUBO 问题。

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

创建一个禁忌搜索对象，显示迭代次数，并将停止时间限制在 0.02 秒。

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

使用禁忌搜索对象求解 QUBO 问题。

result = solve(qprob,Algorithm=ts)
Tabu call    Best fval   Stall time   Tabu iterations
        0           11            0           0
        1            7     0.002028         307
        2            7     0.004494         301
        3            7     0.006852         301
        4            7     0.007939         301
        5            7     0.009099         301
        6            7      0.01007         301
        7            7      0.01109         301
        8            7       0.0126         301
        9            7      0.01359         301
       10            7      0.01457         301
       11            7      0.01554         301
       12            7      0.01652         301
       13            7      0.01775         301
       14            7      0.01991         301
       15            7       0.0209         301

TabuSearch stopped because MaxStallTime is exceeded.

result = 
  quboResult with properties:

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

禁忌搜索是一种随机算法，因此您的结果可能会有所不同。

此示例使用:

打开实时脚本

创建一个 QUBO 问题。

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

使用指定最多 1000 次迭代的 optimset 函数创建一个结构体。

opts = optimset(MaxIter=1e3);

创建一个 qaoa 对象，该对象将成本-混合器层对的数量设置为 3，将测量次数设置为 150。还通过将 OptimizationSolverOptions 设置为 opts 来指定其他优化求解器选项。

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

使用 qaoa 对象求解 QUBO 问题。

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]

输入参数

全部折叠

QUBO 问题，指定为 qubo 对象。使用 qubo 函数创建 qprob。

优化算法，指定为以下对象之一：

  • tabuSearch 对象 - 使用禁忌搜索算法。使用 tabuSearch 函数设置算法属性。

  • qaoa 对象 - 使用量子近似优化算法。使用 qaoa 函数设置算法属性。

此参量确定存储在生成的 quboResult 对象的 AlgorithmResult 属性中的对象类型。

示例: 要使禁忌搜索算法运行不超出 60 秒，请设置 ts = tabuSearch(MaxTime=60)，然后调用 solve(qprob,Algorithm=ts)。

输出参量

全部折叠

QUBO 问题的解，以 quboResult 对象形式返回。result 包含以下属性：

  • BestX - 对应于最小目标函数值的解点，以实数向量形式返回。

  • BestFunctionValue - 对应于 BestX 的目标函数值，以实数标量形式返回。通常，BestFunctionValue = evaluateObjective(qprob,BestX)。

  • AlgorithmResult - 结果详细信息，以 tabuSearchResult 对象或 qaoaResult 对象形式返回。

算法

  • 禁忌搜索算法基于 Palubeckis [2]。从一个随机二进制向量开始，软件通过将一些现有值从 1 切换到 0 或从 0 切换到 1，反复尝试寻找具有更低目标函数值的二进制向量。软件尝试通过使用禁忌列表来避免循环或重复计算同一点。有关详细信息，请参阅Tabu Search Algorithm。

  • QAOA 是求解优化问题的量子-经典混合方法。通常，量子电路表示问题的可能解，经典优化器以迭代方式调整电路中的角度以提高解的质量。量子电路使用交替的成本和混合器层对提供的问题进行逼近求解。有关详细信息，请参阅Solve Max-Cut Problem Using QAOA。

参考

[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.

版本历史记录

在 R2023a 中推出

全部展开

另请参阅

| | |

主题