近日，北京量子信息科学研究院（以下简称“量子院”）量子算法应用软件团队与清华大学开展合作研究，在密码分析量子算法领域取得重要进展。双方联合提出一种基于量子-经典混合架构的 HAWI 算法，成功在含噪声中等规模量子（NISQ）设备上演示了“容错学习问题”（Learning with Errors，LWE）的求解。2025年5月20日，相关研究成果以 “Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices”为题在线发表于《Communications Physics》期刊。

LWE 问题作为后量子密码体系的基石，其安全性建立在格理论问题极高的计算复杂度上。传统经典算法求解 LWE 问题需要耗费指数级时间，而现有的基于搜索的量子算法，因电路深度过大，难以在当前的 NISQ 设备上实际应用。此次，研究团队运用格基约化理论，将 LWE 问题转化为最短向量问题，并融合伊辛模型与量子优化技术，首次在超导硬件环境下完成了小规模 LWE 问题求解的实验演示。

HAWI 算法主要通过三个步骤实现 LWE 问题的求解。第一步是经典预处理，将 LWE 样本转化为格基约化问题，借助经典 LLL（Lenstra-Lenstra-Lovász）算法生成短基向量；第二步进行量子编码，把格向量映射为伊辛模型哈密顿量，利用量子比特对向量的可能组合进行编码，其中低能态对应着最短向量；第三步实施量子优化，采用量子近似优化算法（QAOA）搜索哈密顿量的低能态，从而提取问题的解。该算法所需的量子比特数仅为 m(m+1) （m 为样本数），相比传统量子算法大幅减少。在特定条件下，其时间复杂度也优于经典的 BKZ（Block Korkin-Zolotarev）算法。通过改进参数初始化策略，QAOA 的成功率提升至随机初始化的 15 倍以上。在 IBM 量子平台上，研究团队利用 5 个量子比特完成了 2 维 LWE 问题的实验演示，单层 QAOA 电路使目标态出现概率从 3% 提升至 47%。数值模拟进一步显示，对于 15 维问题，该算法仅需少量量子比特，就能达到超越特定参数下经典 BKZ 算法的效果。该算法是启发式的，对于更大规模问题的性能需要在未来进一步研究。

值得关注的是，本次研究成果中基于格基约化理论构建伊辛模型的方法，在 2022 年曾应用于大数分解的量子算法，在超导量子计算硬件上完成了 48 位整数的实验分解。采用该方法，在过去两年间，俄罗斯团队在离子阱量子硬件中分解实现了 44 位整数的分解，意大利和德国的科学家借助张量网络完成了 100 位整数的分解^[4]，彰显了该方法的应用潜力。

该成果第一作者为量子院/清华大学博士生郑沐曦，共同通讯作者为量子院助理研究员魏世杰与量子院科研副院长/清华大学教授龙桂鲁。合作者还包括量子院助理研究员曾进峰、副研究员王敏等。该工作得到了国家自然科学基金和北京市科技新星计划的支持。