昇思人工智能框架峰会 | MindSpore Quantum量子启发求解器，助力大规模组合优化问题求解效率倍增

在物流调度、金融投资等领域，随着数据规模的扩大，组合优化问题往往面临计算复杂度激增的难题，传统算法难以在有限算力与求解精度之间取得平衡。为此，MindSpore Quantum实现了量子启发式求解器。该方案基于经典硬件模拟量子演化特性，旨在优化大规模问题的寻优效率，为解决工业级复杂问题提供了一种高性能的技术新解。

# 01

量子启发式算法简介

量子启发式算法是一种新式的算法，它源于或直接受基于量子力学原理的计算方法的启发，旨在利用量子力学的独特性质（叠加态、量子纠缠和量子并行性）来改进传统算法的性能。

• 对于线性代数问题：受HHL（Harrow-Hassidim-Lloyd）算法的启发，Ewin Tang提出了量子启发算法，与已知的经典方法相比，这些算法具有指数级的性能加速。
• 对于组合优化问题：受量子退火或类似（量子）伊辛机启发的算法。

量子启发式算法的发展脉络

1、相干伊辛机 Coherent Ising Machine, CIM

• 模拟相干伊辛机 Simulated Coherent Ising Machine (SimCIM, 2019)
• 混沌振幅控制 Chaotic Amplitude Control (CAC, 2020)
• 混沌振幅反馈 Chaotic Feedback Control (CFC, 2021)
• 离散振幅反馈 Separated Feedback Control (SFC, 2021)

2、模拟分岔 Simulated Bifurcation

• 绝热模拟分岔 adiabatic Simulated Bifurcation (aSB, 2019)
• 弹道模拟分岔 ballistic Simulated Bifurcation (bSB, 2021)
• 离散模拟分岔 discrete Simulated Bifurcation (dSB, 2021)

3、平均场退火 Mean Field Annealing

• 局域量子退火 Local Quantum Annealing (LQA, 2022)
• 含噪平均场退火 Mean-Field Approximate Optimization Algorithm (MFAOA, 2023)

量子启发式算法中的模拟分岔算法 Simulated Bifurcation

模拟分岔算法其核心思想是通过模拟非线性哈密顿动力学的分岔现象来寻找伊辛模型（Ising problem）的基态，从而将组合优化问题映射为物理系统的优化问题。

基于模拟哈密顿方程中的分岔过程，系统通过动态调节控制参数，使系统经历一系列动力学分岔，最终收敛到由伊辛自旋变量稳定（+-1），并得到稳定解，这个解对应原始问题的局部最优解或近似解。

# 02

量子启发式算法应用场景

1、物流与生产调度

量子启发式算法擅长解决旅行商问题、0-1背包问题等NP困难问题，为物流路径规划、生产调度提供高效方案。

2、通信网络

量子启发式算法可应用于通信网络的优化设计，例如路由优化、资源分配等，提供网络的效率和可靠性。

3、蛋白质结构和药物研发

蛋白质分子的折叠对接是药物研发中的重要课题，量子启发式算法可预测多种蛋白质分子旋转角度，缩短求解时间，加速药物的筛选和研发。

MindSpore Quantum已经集成量子启发式算法模块，并提供CPU、NPU****版本，适配多种硬件设备，并提供极致性能。

• mindquantum.algorithm.qaia.QAIA 量子退火启发式算法基类
• mindquantum.algorithm.qaia.CAC 混沌振幅控制算法
• mindquantum.algorithm.qaia.CFC 混沌振幅反馈算法
• mindquantum.algorithm.qaia.LQA 局域量子退火算法
• mindquantum.algorithm.qaia.NMFA 含噪平均场退火算法
• mindquantum.algorithm.qaia.ASB 绝热模拟分叉算法
• mindquantum.algorithm.qaia.BSB 弹道模拟分叉算法
• mindquantum.algorithm.qaia.DSB 离散模拟分叉算法
• mindquantum.algorithm.qaia.TSB 三元量化模拟分岔算法
• mindquantum.algorithm.qaia.USB 均匀量化模拟分岔算法
• mindquantum.algorithm.qaia.LSB 对数量化模拟分岔算法
• mindquantum.algorithm.qaia.SFC 离散振幅反馈算法
• mindquantum.algorithm.qaia.SimCIM 模拟相干伊辛机算法

# 03

实战案例-使用量子启发式算法求解最大割问题

组合优化问题是一类在有限的选项集合中找到最优解的数学问题，它有着广泛的应用，像投资组合，旅行商问题等。它的求解难度随着问题规模的增加指数增长。因此，目前还不存在高效的经典算法来求解组合优化问题。

Max-Cut问题是其中一种组合优化问题，该问题需要将一个图中的顶点分成两部分，并使得两部分被切割的边最多。如下图：

下面演示使用MindSpore Quantum中的量子启发式算法求解最大割问题，数据集来源于经典的GSet问题，选取G22图，其规模是2000节点，19990条边。

# 导入需要的Python模块  
from mindquantum.algorithm.qaia import DSB  
import numpy as np  
import pandas as pd  
from scipy.sparse import coo_matrix  
import time

# 数据准备# 下载数据，无向图数据集来源于GSetimport requests  
  
graph_file ="https://web.stanford.edu/~yyye/yyye/Gset/G22"  
  
# 使用requests库中的get方法发送HTTP请求，将url的响应结果存入变量，再以二进制写入模式打开文件写入本地response = requests.get(graph_file)  
open("G22", "wb").write(response.content)  
  
# 数据处理def read_gset(filename, negate=True):  
# 读取图表graph = pd.read_csv(filename, sep=" ")  
# 节点的数量n_v =int(graph.columns[0])  
# 边的数量n_e =int(graph.columns[1])  
  
# 如果节点和边不匹配，会抛出错误assert n_e == graph.shape[0], "The number of edges is not matched"  
  
# 将读取的数据转换为一个COO矩阵（Coordinate List Format），并返回一个稀疏矩阵  
G = coo_matrix(  
(  
np.concatenate([graph.iloc[:, -1], graph.iloc[:, -1]]),  
(  
np.concatenate([graph.iloc[:, 0] -1, graph.iloc[:, 1] -1]),  
np.concatenate([graph.iloc[:, 1] -1, graph.iloc[:, 0] -1]),  
),  
),  
shape=(n_v, n_v),  
)  
if negate:  
G =-G  
  
return G

  

G = read_gset("./G22")

start_time = time.time()  
solver = DSB(G, batch_size=100, n_iter=1000, backend="npu-float32")  
solver.update()  
cut = solver.calc_cut()  
end_time = time.time()

  

print(f"G22 MAXCut is : {max(cut)}\nuse time:{end_time-start_time}")

输出：

G22 MAXCut is : 13353.0
   use time:0.5273990631103516

可以看到，DSB算法仅用0.53秒就求解出了2000节点的GSet图，该图的最大切割数在13353附近。

使用NPU加速量子启发式算法

上述卓越的求解速度，归功于MindSpore Quantum中利用NPU对此类量子启发式算法的显著加速。我们分别在CPU和NPU后端上运行DSB算法，求解最大割问题：

import time  
  
start_time = time.time()  
solver = DSB(G, batch_size=100, n_iter=1000, backend="cpu-float32")  
solver.update()  
cut = solver.calc_cut()  
cpu_fp32_time = time.time() - start_time  
  
start_time = time.time()  
solver = DSB(G, batch_size=100, n_iter=1000, backend="npu-float32")  
solver.update()  
cut = solver.calc_cut()  
npu_fp32_time = time.time() - start_time

import matplotlib.pyplot as plt# 计算加速比cpu_speedup = cpu_fp32_time / cpu_fp32_time  
npu_speedup = cpu_fp32_time / npu_fp32_time  
  
  
devices = ["CPU-Float32", "NPU-Float32"]  
times = [cpu_fp32_time, npu_fp32_time]  
speedups = [cpu_speedup, npu_speedup]  
colors = ["#4C72B0", "#DD8452"]  
  
  
plt.figure(figsize=(10, 6), dpi=100)  
  
# 绘制横向条形图, 表示不同后端的计算时间bars = plt.barh(devices, times, color=colors, height=0.6)  
  
# 添加数据标签和加速比  
for i, (time, speedup) inenumerate(zip(times, speedups)):  
plt.text(  
time +0.05,  
i,  
f"{time:.2f}s ({speedup:.1f}x)",  
va="center",  
fontsize=12,  
)  
  
plt.title(  
"QAIA Performance Comparison On Different Hardware In G22", fontsize=14, pad=20  
)  
plt.xlabel("Time(seconds)", fontsize=12)  
plt.xlim(0, max(times) *1.3)  
plt.grid(axis="x", linestyle="--", alpha=0.7)  
plt.tight_layout()  
  
plt.show()

可以看到，对于同样的问题，如果使用CPU进行求解，需要14.2秒才能完成，而NPU仅需0.5秒，使求解速度提升了28倍。

MindSpore Quantum是基于昇思MindSpore开源深度学习平台开发的新一代通用量子计算框架，聚焦于NISQ阶段的算法实现与落地。结合HiQ高性能量子计算模拟器和昇思MindSpore并行自动微分能力，MindSpore Quantum有着极简的开发模式和极致的性能体验，能够高效处理量子机器学习、量子化学模拟和量子组合优化等问题，为广大科研人员、老师和学生提供快速设计和验证量子算法的高效平台，让量子计算触手可及。

MindSpore Quantum开源仓库：

https://atomgit.com/mindspore/mindquantum
MindSpore Quantum社区文档地址：

https://www.mindspore.cn/mindquantum/docs/zh-CN/r0.11/index.html