静5青年讲座回顾 | 卢丽强博士谈量子计算软件优化方法

关键词：静5青年讲座

编者按

2023年9月14日，浙江大学的卢丽强博士访问北京大学前沿计算研究中心，在静园五院做了题为“量子计算软件优化方法”的报告。报告由中心助理教授李彤阳老师主持。

卢丽强博士报告现场

卢老师的报告主要围绕在量子计算系统软件层面的两项工作展开。第一项工作是量子经典混合的 3-SAT 算法求解器，通过算法软件的协同设计实现对 SAT 问题求解的加速。第二项工作是考虑电路拓扑特征的量子电路分析，通过对量子电路基于向量化的特征提取，提高在量子电路保真度预测与酉矩阵分解等下游任务的性能表现。

报告的第一部分从 SAT 问题展开。SAT 问题，即命题逻辑公式的可满足性问题，是第一个被证明的 NP 完全（NP-complete）问题，在计算机科学、工业生产等各领域都具有重要价值和广泛应用。一个 SAT 问题由多个子句构成，每个子句表示为多个变量的析取式，如果存在一组变量值使得所有子句都被满足，则这个 SAT 问题被满足。SAT 问题可能具有多组可行解。经典算法中目前求解 SAT 问题最优的是 CDCL 算法，即冲突驱动子句学习，算法通过赋值进行决策-推理，若有冲突则修改赋值消解冲突，直至求解问题。SAT 问题的量子算法主要有两类，基于门电路的搜索算法和基于量子隧穿的退火算法，这项工作中采取后者。

使用量子退火算法解 3-SAT 问题，首先需要将问题转化为二次多项式的最小化（QUBO）问题，将该优化函数对应的带权重变量图嵌入芯片执行量子退火，若系统最低能级可达到0，则可得到对应问题 SAT 问题的解。这种方法面临多种挑战，一是高编译延迟，将原问题嵌入量子退火芯片的经典步骤需要相当的处理时间；二是噪声影响，需重复执行量子退火以减少噪声影响从而获得合理结果，导致较高时间消耗；三是规模有限，受制于芯片规模和噪声影响，量子退火算法能求解的 SAT 问题规模较小。为解决这三项挑战，卢老师课题组提出 HyQSAT 方法，完成大规模端到端加速求解 SAT 问题的实现。

经典 CDCL 算法优势是可解决的问题规模大，劣势在于显著依赖于问题的难易程度，求解困难子句比较耗时。量子退火算法求解速度与问题难易程度无关，缺点是求解规模小。因此卢老师课题组提出经典量子混合算法：定位 CDCL 难以解决的子问题，用量子退火机加速求解。在具体实现上，主要通过访问频率定义子句的困难度，并结合变量复用进行排序，从而定位困难子句。在前端利用 D-Wave 芯片的拓扑结构，采取贪心的编译策略进行变量在硬件的嵌入。在后端通过预先创造实例的运行结果获得可满足性概率分布估计，用于判断量子退火求解子问题的可满足性。根据子问题的求解结果，缩小 CDCL 的搜索空间，从而实现加速。实验结果显示，在7个领域的11个 benchmark 问题上，在 D-Wave 2000Q 上端到端取得了相比于 KisSAT 平均4.92X 的加速；在模拟量子计算机上取得迭代次数平均14.11X 减少；加速比随硬件规模增大迅速增长，可扩展性好。

在报告的第二部分，卢老师指出量子电路分析方法是量子计算的重要环节，常见任务例如酉矩阵分解和噪声源分析对于量子计算的实现具有重要意义。酉矩阵分解需将任意酉矩阵转化为芯片支持的特定量子门的电路近似，常见方法有 CCD、QSD 等基于模版的分解方法（分解速度快但门数量达到数千数量级），或 QFAST 等基于搜索的方法（门数量较少但搜索时间过长，实际应用困难）。噪声源分析任务是对电路级别保真度和门级别保真度进行预测与优化，现有方法如 RB、QuEST 等，在准确度和执行时间上都均不够理想。

针对以上问题，卢老师课题组希望找到一种电路的通用表示，能够又快又准地同时完成电路分析任务，据此他们提出了 QuCT 方法。QuCT 方法采用向量化的思想，将量子门电路转化为含有特征的向量表示，类似自然语言处理中的上下文分析。QuCT 的上游模型以量子电路为输入，以特征向量为输出。受传统稀疏图、推荐系统的向量化方法启发，从单个量子门出发采用随机游走的方法生成多条路径，与预先生成的静态路径表比对，按系数组合生成每一个门的对应向量。这样的构造方法也有利于从向量重建电路。

QuCT 的下游模型则统一以特征向量为输入，针对不同的下游任务定制不同模型和输出。在电路保真度预测任务中，门保真度由  确定，其中  为门向量，  是训练所得参数。据此可以计算电路保真度  ，其中  为电路中门的集合，  是量子比特的集合，  是比特  的读取保真度。在目标量子计算机上执行获得真实值  ，通过最小化  达到训练  的目的。实验结果显示 QuCT 较其他算法取得了显著更好的准确度。

在酉矩阵分解任务中，此前的 QFAST 算法以门作为作为 candidate 搜索，搜索空间大、距离计算时间长，且需要进一步迭代分解为基本门。而 QuCT 以向量作为 candidate 进行搜索，包含线路信息，搜索空间少、无需进一步分解。实验结果显示 QuCT 在5比特酉矩阵分解问题上取得了平均46.3X 的加速。

报告回放：

图文 | 杨睿

往期讲座

• 静5前沿讲座回顾 | 贝小辉教授谈广告拍卖中的实践与理论问题

• 静5前沿讲座回顾｜陆品燕教授介绍一价拍卖效率的确定

• 静5青年讲座回顾 | 冯逸丁博士谈自动报价市场中的策略性预算选择问题

• 静5杰出讲座回顾｜叶荫宇教授谈随机Fisher市场中的在线均衡标价问题

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转报告回放链接