前言

本文还是大部分截图来自于：《最適化問題とWildqatを用いた量子アニーリング計算入門》 https://booth.pm/ja/items/1415833

终于有人问到怎么将QUBO中的三次多项式转换为二次多项式了。直接以一个例题开始讲解。中间会用到之前文章里的知识，大家最好读了该系列前两篇之后，再阅读此文。

一、三次多项式的例题

问题：通过量子退火算法求解令下面$H$最小化的x1,x2,x3x_1,x_2,x_3x1​,x2​,x3​值。

下面讲解如何导出对应的QUBO矩阵。

Step1. 变量替换。

首先，把两个变量的乘积用一个变量替代，这里用x4x_4x4​替代x2x3x_2x_3x2​x3​。

因为我们使用了上面的变量替换，所以我们要满足以下约束：

Step2. 加入约束项。

上面的约束对应的约束项H′H'H′如下👇，由x2,x3,x4x_2,x_3,x_4x2​,x3​,x4​能构成的二次多项式构成。

这里补充一句，在本系列第二篇中，直接给大家列出了常见约束的H表达式，这次我们需要手动推导。大家从头到尾，要谨记一句话：

【我们最终的目标是令目标$H$最小化的同时，满足约束。所以，约束H′H'H′代入令目标$H$最小化的变量x2,x3,x4x_2,x_3,x_4x2​,x3​,x4​具体值时，也是最小化的。】

于是，接下来所有的变换都是为了寻找H′H'H′的适当的系数（a, b, c, d, e, f）。本系列第二篇中每个常见约束的求解，都经历了寻找对应系数的过程。

Step3. 寻找合适的约束项系数。

我们可以这么想，通过合适的系数（a, b, c, d, e, f），使得x2,x3,x4x_2,x_3,x_4x2​,x3​,x4​满足式(2)时，令H′=0H'=0H′=0；不满足式(2)时，H′>0H'>0H′>0。那就这么约定了。

1. x2x3=x4x_2x_3=x_4x2​x3​=x4​时，如我们约定好的，令H′=0H'=0H′=0，整理如下表：
   
   这时，上表中的x2,x3,x4x_2,x_3,x_4x2​,x3​,x4​按行代入式(4)后，对应的只包含系数（a, b, c, d, e, f）的等式如下：

2. x2x3≠x4x_2x_3≠x_4x2​x3​=x4​时，如我们约定好的，令H′>0H'>0H′>0，整理入下表：
   
   这个时候，（k1,k2,k3,k4）（k_1,k_2,k_3,k_4）（k1​,k2​,k3​,k4​）都是比0大的常量。在a=b=0的前提下，把上表中的所有指按行代入式(4)后，得到等式如下：

接下来，我们要寻找合适的（k1,k2,k3,k4）（k_1,k_2,k_3,k_4）（k1​,k2​,k3​,k4​），比如下面的两组赋值都不行❌。

于是我们找了很久，终于发现（k1,k2,k3,k4）（k_1,k_2,k_3,k_4）（k1​,k2​,k3​,k4​）如下👇取值时，满足约束。

Step4. 获得确定系数的约束项H′H'H′。

把已经确定的（a, b, c, d, e, f）和（k1,k2,k3,k4）（k_1,k_2,k_3,k_4）（k1​,k2​,k3​,k4​）代入式(4)就行了。得到最终的H′H'H′如下：

Step5. 获得最终的二次多项式$H$。

这里就不必多说了，别忘了还有个 $\lambda$ 系数，需要手动指定。

我们把 $\lambda$ =1，代入上式，得到下面最终的QUBO矩阵。

二、Python实现

1.引入库

import wildqat as wq
import numpy as npH_A = np.array([[1,0,0,-1],[0,0,0,0],[0,0,0,0],[0,0,0,0]])
H_A = np.array([[0,0,0,0],[0,0,1,-2],[0,0,0,-2],[0,0,0,3]])
k, l = 1, 1a = wq.opt()
a.qubo = k * H_A + l * H_Bfor i in range(5):print("x = {}".format(a.sa()))print("H = {}".format(a.E(-1)))

结果打印如下，有兴趣的可以看看，取值是否满足约束。

总结

提示：写的比较匆忙，可能有很多错误，大家发现了留言告诉我：

还是挺麻烦的，不过不难理解，是可以写程序自动化的，这也是为什么我们需要pyqubo这中自动化转换QUBO的程序。