本帖最后由 薛定谔了么 于 2024-11-14 10:28 编辑
前言
本文还是大部分截图来自于：《最適化問題とWildqatを用いた量子アニーリング計算入門》 https://booth.pm/ja/items/1415833
终于有人问到怎么将QUBO中的三次多项式转换为二次多项式了。直接以一个例题开始讲解。中间会用到之前文章里的知识，大家最好读了该系列前两篇之后，再阅读此文。
一、三次多项式的例题
下面讲解如何导出对应的QUBO矩阵。
Step1. 变量替换。
首先，把两个变量的乘积用一个变量替代，这里用x 4 替代x 2 x 3
因为我们使用了上面的变量替换，所以我们要满足以下约束：
Step2. 加入约束项。
上面的约束对应的约束项H ′
如下👇，由x 2 , x 3 , x 4能构成的二次多项式构成。
这里补充一句，在本系列第二篇中，直接给大家列出了常见约束的H表达式，这次我们需要手动推导。大家从头到尾，要谨记一句话：
【我们最终的目标是令目标H 最小化的同时，满足约束。所以，约束H ′ 代入令目标H HH最小化的变量x 2 , x 3 , x 4 具体值时，也是最小化的。】
于是，接下来所有的变换都是为了寻找H ′的适当的系数（a, b, c, d, e, f）。本系列第二篇中每个常见约束的求解，都经历了寻找对应系数的过程。
Step3. 寻找合适的约束项系数。
我们可以这么想，通过合适的系数（a, b, c, d, e, f），使得x 2 , x 3 , x 4 满足式(2)时，令H ′ = 0 ；不满足式(2)时，H ′ > 0 。那就这么约定了。
这时，上表中的x 2 , x 3 , x 4 按行代入式(4)后，对应的只包含系数（a, b, c, d, e, f）的等式如下：
当x 2 x 3 ≠ x 4 时，如我们约定好的，令H ′ > 0，整理入下表：
Step4. 获得确定系数的约束项H ′
把已经确定的（a, b, c, d, e, f）和（ k 1 , k 2 , k 3 , k 4 ） 代入式(4)就行了。得到最终的H ′如下：
Step5. 获得最终的二次多项式H 。
这里就不必多说了，别忘了还有个 λ 系数，需要手动指定。
我们把 λ =1，代入上式，得到下面最终的QUBO矩阵。
二、Python实现
1.引入库
import wildqat as wq
import numpy as np
H_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, 1
a = wq.opt()
a.qubo = k * H_A + l * H_B
for i in range(5):
print("x = {}".format(a.sa()))
print("H = {}".format(a.E(-1)))
结果打印如下，有兴趣的可以看看，取值是否满足约束。
总结
还是挺麻烦的，不过不难理解，是可以写程序自动化的，这也是为什么我们需要pyqubo这中自动化转换QUBO的程序。
————————————————
本文转载自CSDN博主：gang_unerry
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/gangshen1993/article/details/130137241 | 
