处理降次问题

背景介绍

前文有提到，QUBO问题的目的是求得一组变量的值$(x_0,x_1\dots x_n)$使得二阶多项式$x^{T}Qx$的值最小。

然而，实际应用中，经常会遇到三次或更高次数的多项式问题，这些高阶项不能直接用QUBO求解。为了解决这个问题，我们引入了HOBO（Higher Order Binary Optimization）模型，通过引入辅助变量和额外的约束，将高阶项转换为低阶二次项来实现优化。

高阶问题降阶的流程如下图所示，后文将具体介绍高阶降次的具体方法与相应的Kaiwu SDK的用法。

高阶降次方法

HOBO模型

一般的HOBO问题可以定义为：

$$f(x)=\sum _{i_1,i_2,\dots ,i_k}{a}_{i_1{i}_2,\dots ,i_k}{x}_{i_1}{x}_{i_2},\dots x_{ik}$$

其中$x=(x_1,x_2,\dots ,x_n)$的每个$x_i$都是一个可以取值为$0$或$1$的变量，$k$表示多项式的阶数，且$k>2$。

HOBO问题可以有约束项，带约束的问题同样可以通过添加惩罚项的方式转换为无约束问题。

将HOBO问题转化为QUBO问题

HOBO问题的目标也是最小化目标函数$f(x)$，然而专用量子计算机被设计用于处理二次模型，因此HOBO模型通常通过引入辅助变量和额外的约束来将其转换为QUBO模型，以将高阶项分解为二次项。

首先，把两个变量的乘积用一个变量替代，例如令$y=x_0{x}_1$并代入原式，将原式中的单项式阶数降低，并且添加$y=x_0{x}_1$的约束。

而要使得约束成立的方式是在原式中添加惩罚项，即Rosenberg二次惩罚项：

$$p(x_0,x_1,y)=x_0{x}_1-2x_{0}y-2x_{1}y+3y$$

该惩罚项呈此形式是为了满足如下要求：

$$p(x_0,x_1,y)\{\begin{array}{c}=0，y=x_0{x}_1\\ >0，y\ne x_0{x}_1\end{array}$$

对所有的高阶项都进行如上处理后，就得到最终新的多项式为

$$f(x,y)+k\sum p(x_i,x_j,y_{ij})$$

其中$k$是惩罚项系数。

举例说明

此处举一个例子来展示这种降次方式。

例如有

$$\begin{array}{}\text{(1)}& H=x_1-x_1{x}_2{x}_3\end{array}$$

然后按下述方式转化为无约束二次型。

步骤1 变量替换

首先把两个变量的乘积用一个变量替换，这里我们用$y$替换$x\ast 2x\ast 3$，于是有：

$$\begin{array}{}\text{(2)}& H=x_1-x_{1}y\end{array}$$

于是变量替换也成为一个要满足的约束条件，即有新的约束条件：

$$\begin{array}{}\text{(3)}& y=x_2{x}_3\end{array}$$

步骤2 加入惩罚项

现在目标函数的阶数下降了，但是新增了约束项，这就回到了处理约束问题学习的内容范畴了。前面我们学习过，目的是计算目标函数的最小值，那么可以在目标函数上增加一个非负的惩罚函数，使其满足新的约束条件。下面展示如何构造惩罚项。

设上面的约束对应的惩罚项为$H^{\prime }$，则$x_2$、$x_3$和$y$可以构成的二次多项式可以设为如下的形式：

$$\begin{array}{}\text{(4)}& H^{\prime }=a{x}_2+b{x}_3+cy+d{x}_2{x}_3+e{x}_{3}y+f{x}_{2}y\end{array}$$

步骤3 寻找合适的多项式系数（参考）

因为$H^{\prime }$是一个非负的惩罚项，所以只要它在满足$y=x_2{x}_3$时有$H^{\prime }=0$，在不满足条件时有$H^{\prime }>0$，就能起到惩罚函数的作用。

即令

$$\begin{array}{}\text{(5)}& H^{\prime }(x_2,x_3,y)\{\begin{array}{c}=0，y=x_2{x}_3\\ >0，y\ne x_2{x}_3\end{array}\end{array}$$

显然，$(0,0,0),(0,1,0),(1,0,0),(1,1,1)$都是满足公式（3）的$(x_2,x_3,y)$的组合。将这些组合代入，则有：

$$\begin{array}{}\text{(6)}& \{\begin{array}{rl}b& =0\\ a& =0\\ a+b+c+d+e+f& =0\end{array}\end{array}$$

而在不满足（3）时，我们把$(x_2,x_3,y)$的组合$(0,0,1),(0,1,1),(1,0,1),(1,1,0)$代入（4）和（5）可以得到：

$$\begin{array}{}\text{(7)}& \{\begin{array}{rl}c& =k_1\\ c+e& =k_2\\ c+f& =k_3\\ d& =k_4\end{array}\end{array}$$

其中，$k_1,k_2,k_3,k_4>0$。

接下来就是给$(k_1,k_2,k_3,k_4)$寻找合适的赋值。经过尝试发现如下的取值可以满足约束：

$$\begin{array}{}\text{(8)}& (k_1,k_2,k_3,k_4)=(3,1,1,1)\end{array}$$

对应的$(a,b,c,d,e,f)$为：

$$\begin{array}{}\text{(9)}& (a,b,c,d,e,f)=(0,0,3,1,-2,-2)\end{array}$$

最终得到惩罚项

$$\begin{array}{}\text{(10)}& H^{\prime }=3y+x_2{x}_3-2x_{3}y-2x_{2}y\end{array}$$

这种惩罚项也被称为Rosenberg二次惩罚项。

步骤4 获得最终的无约束二次多项式模型（参考）

于是最终新的多项式为

$$\begin{gathered} \begin{array}{}\text{(11)}& H+k{H}^{\prime } \\ =x_1-x_{1}y+k(3y+x_2{x}_3-2x_{3}y-2x_{2}y)\end{array} \end{gathered}$$

其中$k$为惩罚系数。在确定惩罚系数后，就能得到如下的QUBO矩阵：

$$\begin{array}{}\text{(12)}& QUBO=\left(\begin{array}{cccc}1& 0& 0& -1\\ 0& 0& k& -2k\\ 0& 0& 0& -2k\\ 0& 0& 0& 3k\end{array}\right)\end{array}$$

于是就实现了多项式的降阶并得到了对应的QUBO模型。

（重点）使用Kaiwu SDK进行高阶多项式的降次

在Kaiwu SDK v1.4.0版本中，统一采用HoboModel进行高阶问题建模与降阶处理。

用户可以直接构建包含高阶项的目标函数和约束，在完成建模后，通过reduce()方法即可将高阶表达式自动降阶为QUBO模型。

下面进行函数的详细说明与应用实例。

（1）注意事项

新变量为原变量名字用下划线相连，如 x0 和 x1 被替换为 _x0_x1，_x0_x1 和 _x0_y1 被替换为 _x0_x1_y1

_ 是内部保留符号，不对用户开放用于命名变量。

（2）函数说明

• kw.hobo.HoboModel

  该函数用于构建包含高阶目标函数和高阶约束的优化模型。

• reduce()

  对HOBO高阶表达式进行降阶处理，简化为QUBO表达式。

• verify_hobo_constraint()

  验证求得的解是否满足HOBO降阶的约束条件。

（3）使用举例

使用 HoboModel 和reduce()来完成降阶。

如下是一个将 y1 和 y2 相乘生成的高阶表达式 y3降阶高阶项，生成QUBO表达式的例子。

import kaiwu as kw

x = kw.core.ndarray(10, "x", kw.core.Binary)
y1 = x[0] * x[1] + x[2] * x[3] + x[8]
y2 = x[3] * x[4] + x[5]
y3 = y1 * y2
print(y3, "\n")
hobo_model = kw.hobo.HoboModel(y3)
qubo_model = hobo_model.reduce()
print(hobo_model, "\n")
print(qubo_model)

执行以上代码后结果为

Minimize x[2]*x[3]*x[5]+x[2]*x[3]*x[4]+x[0]*x[1]*x[5]+x[0]*x[1]*x[3]*x[4]+x[5]*x[8]+x[3]*x[4]*x[8]
Subject to (hobo constraints):
_x[2]_x[3] := x[2] * x[3]
_x[0]_x[1] := x[0] * x[1]
_x[3]_x[4] := x[3] * x[4]

Minimize _x[2]_x[3]*x[5]+_x[2]_x[3]*x[4]+_x[0]_x[1]*x[5]+_x[0]_x[1]*_x[3]_x[4]+x[5]*x[8]+_x[3]_x[4]*x[8]
Subject to (hard constraints):
x[2]*x[3]-2*_x[2]_x[3]*x[2]-2*_x[2]_x[3]*x[3]+3*_x[2]_x[3]
x[0]*x[1]-2*_x[0]_x[1]*x[0]-2*_x[0]_x[1]*x[1]+3*_x[0]_x[1]
x[3]*x[4]-2*_x[3]_x[4]*x[3]-2*_x[3]_x[4]*x[4]+3*_x[3]_x[4]

在上面的结果中，

x[2]*x[3]*x[5]+x[2]*x[3]*x[4]+x[0]*x[1]*x[5]+x[0]*x[1]*x[3]*x[4]+x[5]*x[8]+x[3]*x[4]*x[8]

是原始的 HOBO 表达式。形式如_x[i]_x[j] 的元素为 _x[i] 和 _x[j] 变量合并后的新变量。

最终的降阶 QUBO 表达式被表示为：

_x[2]_x[3]*x[5]+_x[2]_x[3]*x[4]+_x[0]_x[1]*x[5]+_x[0]_x[1]*_x[3]_x[4]+x[5]*x[8]+_x[3]_x[4]*x[8]

这些系数表示了经过降阶后的 QUBO 表达式的各项。

*检验：求得的结果是否满足降阶约束条件

下面使用 verify_hobo_constraint 函数验证降阶后的QUBO解是否满足HOBO降阶约束。其中，p 是包含高阶项的 QUBO 表达式，{"x1": 1, "x2": 1, "x3": 0, "_x1_x2": 1} 是解的赋值，表示给定二进制变量的值。

verify_hobo_constraint 会检查解是否符合降阶后的约束条件，返回 err_cnt，如果 err_cnt 为 0，表示满足约束。

x1, x2, x3 = kw.core.Binary("x1"), kw.core.Binary("x2"), kw.core.Binary("x3")
p = x1*x2*x3
hobo_model = kw.hobo.HoboModel(p)
qubo_model = hobo_model.reduce()
solution = {"x1": 1, "x2": 1, "x3": 0, "b_x1_x2": 1}
err_cnt, _ = hobo_model.verify_hobo_ constraint(solution)
print(err_cnt)

得到结果为0，证明解满足降阶的约束。