2023 mindspore量子计算黑客马拉松初赛——量子组合优化赛道代码

环境配置

conda create -n env_name python=3.9
pip install mindspore==1.10.1 mindquantum networkx

缺少包qupack,未公开，只能在华为云平台上使用。

utils.py

read_graph(filename)

返回图g，以及QUBO问题对应的矩阵

  • g是nx中的图格式，G是csr格式的稀疏矩阵
\[G_{ij}=\begin{cases} -\frac{1}{2} &if \ x_i与x_j相邻\\ 0 & if \ x_i与x_j不相邻 \end{cases}\]

calc_subqubo(sub_index, x, J, h=None,C=0.0 )

sub_index是QAOA算法的15量子比特。 fix_index是不在QAOA算法的15量子比特的所有其他比特。 h_sub是一个有sub_index的解向量，目的是使得在仅修改15个节点的位置的情况下，记录该15个节点分到第二组比分到第一组的cut的变化，在哈密顿量中作为Z门的参数，参与QAOA算法优化，使得该哈密顿量为全局最优解。

check_degenerate(J_dict, h)

检查 Qbuild_ham(J_dict,h)UBO 问题是否存在退化情况，并对节点偏置进行修正。

build_ham(J_dict,h)

计算哈密顿量

QAOAsolver(J, h, C, depth = 2, tol=1e-4,info=True)

该函数使用 QAOA 方法求解 QUBO 问题的最优解，通过优化参数使得目标哈密顿量的期望值最小化，从而得到问题的解。

solve_QAOA(J_sub,h_sub,C_sub,sub_index,x,depth=2,tol=1e-4)

该函数通过调用 QAOAsolver 函数对子问题进行 QAOA 求解，利用优化得到的解向量更新原解向量，从而逐步求解整个问题。

calc_qubo_x(J,x,h=None,C=0)

计算QUBO问题的能量值，用于评估解的优劣程度

calc_cut_x(G, x)

计算解向量对应图的割大小

init_solution(n)

生成一个随机解向量作为初始解，作为算法起点。

solve_max_cut.py

  1. 随机初始化解向量（节点的分配方案）
  2. 利用QupackQAOA求解子问题，将解向量中的其中15个影响力最大的结点进行更新
  3. 更新后重新循环4次（循环次数由题目运行时间决定）

关键因素

  1. 一次QAOA的时间大概在1.25s，一张图需要跑20次结果。
    • 如果分数一样依据总运行时间进行排名
    • 程序总运行时间在1h内。（需调用qupack中的QAOA模拟器进行子问题求解） image.png|525
  2. 选取子问题求解的方式：在样例代码中，通过计算改变某节点分组后cut的delta值度量影响力，
  3. 如何在QAOA算法中修改$H_p$

解决方案：

给出较为优秀的初始解+更新影响力较大的15个点

修改

  1. 将影响力由一个点修改后的能量变化改为两个点的。——测试后变化不大
  2. 选取15个点，使得选取的每个点与未选取的每个点的边的连线最少
  3. 增加电路循环p——测试后影响不大
  4. 固定套路选择初始解——未找到合适的解法

想法

  1. 示例代码：依次翻转80个节点中其中一个节点的解，并记录翻转后cut的变化，选出15个cut增加最多的点进行QAOA算法优化解。一共做5轮。
    • 350分
    • 改为挑选图中度比较高的节点 - [x] 初步优化思路：按照1的方法挑选15个节点使用QAOA算法，不同的是挑选过的节点不能再被挑选，直到所有节点被挑选完毕。
    • 360分
    • 364分——随机更多次（10000）解，选取cut最大的作为初始解 - [ ] 将80个节点每15个进行分组，使得组与组之间的连线最少。分别在每个组内使用QAOA算法。
score:54，108，238，406，226，231
size：[40,80,40,80,80,80]=400
[[ 50.  51.  52.  52.  50.  52.  50.  51.  49.  51.  53.  54.  52.  49.
   51.  50.  53.  54.  52.  51.]
 [ 93.  96.  96.  93.  94.  93.  98.  98. 101.  99.  94.  92. 101.  96.
   97.  94.  93. 101.  93.  97.]
 [226. 219. 229. 230. 229. 234. 230. 232. 215. 230. 231. 227. 238. 218.
  227. 219. 210. 214. 231. 223.]
 [370. 357. 337. 376. 373. 380. 371. 367. 363. 363. 364. 353. 368. 374.
  373. 375. 364. 375. 373. 358.]
 [212. 200. 203. 198. 198. 202. 212. 204. 190. 204. 203. 208. 202. 203.
  191. 202. 205. 194. 209. 201.]
 [215. 207. 207. 209. 203. 202. 216. 192. 215. 203. 220. 199. 210. 211.
  217. 211. 203. 208. 205. 211.]]
满分400分

第一题测试

满分400分

score(对graph80-604 cut406) 备注
360.5 一轮遍历更新 +初始化解优化
363.2 两轮遍历更新 +初始化解优化
372.3 一轮遍历更新，一轮影响力更新+初始化解优化
376.5 一轮遍历更新，两轮影响力更新 +初始化解优化
379.45 两轮遍历更新，一轮影响力更新 +初始化解优化
score(对所有图) 备注
374.085 两轮遍历更新，一轮影响力更新
370.7 一轮遍历更新，一轮影响力更新
364 一轮遍历更新
333 随机初始解，不进行QAOA

第二题测试

越大越好

score (对graph80-604 cut406) 荒废 备注
45.5 示例代码
47.4 随机初始解次数增多并挑选
46 一轮遍历更新，一轮影响力更新+传入矩阵由G改为G_min
   
score (对graph40-60 cut54) 备注
24.8 ❓ 取影响力最大的节点+一轮遍历更新，一轮影响力更新
23.8 ❓ 取影响力最小的节点+一轮遍历更新，一轮影响力更新
28.86/27.5 示例代码
28.43 /28.6 ✅ 随机初始解次数增多并挑选
23.9 两轮遍历更新
27.16 /28.9 遍历更新+影响力更新
  • 分子图（可能耗时）
  • 让遍历更新取满

This line appears after every note.

Notes mentioning this note

Projects
1.前后端 [[使用Flask快速构建浏览器实现图片交互]]

Here are all the notes in this garden, along with their links, visualized as a graph.