量子-经典协同计算新路径：NISQ 时代混合算法对后量子密码学的适应性探索
内容来源：量子前哨（ID：Qforepost）
文丨浪味仙 排版丨浪味仙
行业动向：3700字丨10分钟阅读
5 月 20 日，由北京量子院、清华大学、数学工程与先进计算国家重点实验室、南洋理工大学、量子信息前沿科学中心以及北京国家信息科学与技术研究中心共同组成的研究团队，在知名学术期刊《Communications Physics》上发表了一篇重要研究论文。该论文题为《Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices》（用于解决 NISQ 设备上容错学习问题的量子经典混合算法），由 Muxi Zheng 担任第一作者，魏世杰和龙桂鲁教授为通讯作者。
该研究提出了一种名为 HAWI（使用伊辛模型的量子+经典混合算法）的新型算法，在应对“容错学习”（Learning-With-Errors,LWE）问题上带来了创新突破，可以帮助我们更准确地分析量子计算机的影响，设置密码的安全参数，为后量子密码学和 NISQ 设备的实际应用开辟了新的前景。
何为
容错学习问题？
容错学习（LWE）问题，是一种在后量子密码学和计算学习理论中都非常重要的基础计算难题。
想象你是一名电报员，为了国家安全，你需要通过破译数字加密电报，找出一串隐藏在某个远程秘密基地中的“秘钥”。（责任感和压迫感是不是齐了~
下面是一些更详细的信息：
1、在那个远程的秘密基地中，藏着一串非常重要的“秘钥”（假设是 996）。你需要找出它，因为它被秘密地存储在基地中，当然你并不知道。
2、秘密基地中有一个“电报生成器”，它知道“秘钥”是 996。
3、电报生成器的工作流程是：
a）它会随机选择一串数字（比如 123），作为电报的“头部信息”。
b）它将这串“头部信息”（123）和“秘密密钥”（996）进行一番复杂的内部运算，假定二者相减得到结果 873。
c）这时，生成器会在 873 这个结果上故意加一点随机的“误差”，但这个误差很小，比如使 873 变成 874。
d）最后，电报生成器会将“头部信息”（123）和带有干扰的运算结果（874）一起发送出去，成为一份“模糊电报”。
身为一名电报员，你会收到很多份这样的“模糊电报”，每份都带有正常的随机干扰，也就是同时包含“头部信息”和“包含误差的结果”，你的任务就是利用所有这些真的“模糊电报”（划重点：真的），通过复杂的分析和计算，最终找出隐藏在秘密基地里的那串“秘钥”（996）。（对应 LWE-搜索问题）
为什么要划重点呢？因为如果没有这个限定词，你的任务就会发生变化。
倘若你收到的“模糊电报”中，只有一部分是那台使用“秘钥”的电报生成器发出的，而另一部分则是完全随机生成、没有任何规律可循的乱码。
此刻，这个任务类似“真假美猴王”：针对每一份收到的电报，判断它是“使用秘钥并带有正常干扰的·真·模糊电报”，还是一份“毫无规律、完全随机的乱码”。这种情况下，你不需要找出秘钥具体是什么，只需要分辨它是否“符合模式”即可。（对应 LWE-决策问题，本篇论文主要关注的是这一种。）
破译“模糊电报”的任务，难就难在“误差”上，它令你无法规避大量尝试和巧妙推理，容错学习（LWE）问题就是这样一个从“有噪声的线性信息”中“学习”出“秘密信息”的问题，正因为有噪声的存在，才使得该问题的直接求解变得极为困难。
容错学习（LWE）问题是后量子密码学的核心计算难题之一，由于其被认为对经典计算机和量子计算机都具有计算难度，因此解决 LWE 问题对于构建未来安全的加密系统至关重要。
基于此，我们走近看看《Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices》（用于解决 NISQ 设备上容错学习问题的量子经典混合算法）这篇论文是如何应对 LWE 这一问题的。
HAWI 创新算法
论文创新性地提出了一种 HAWI 算法，采用一套“组合拳”来应对容错学习（LWE）问题，概括来说就是：
将 LWE 问题“转化”成为“找最短路径”问题（SVP），再将转化出的 SVP 问题“编码”成量子计算机能理解的能量模型（伊辛模型）。接下来，利用 NISQ 设备擅长的量子优化算法（如 QAOA），在经典计算机的配合下，寻找能量模型（伊辛模型）的最低点，从而揭示出 LWE 问题的秘密。
1、把“找秘密”变成“找最短路径”
LWE 问题本质是“在有噪音的线索中找秘密数字”，论文首先把这个问题巧妙地“转化”或者说“翻译”成了另一个经典的数学难题：最短向量问题（Shortest Vector Problem, SVP）。
你可以把 SVP 问题想象成是在一个由很多点组成的“网格”里，我们要找到从原点出发，连接到其他点的“最短的路线”。而这条“最短的路线”，恰好可以对应 LWE 问题中的秘密数字。
这种转化很重要，因为 SVP 问题虽然也难，但它有成熟的数学框架和算法研究基础，还更适合量子计算机来处理。
2、量子-经典混合：聪明地分配任务
当前的量子计算机还处于“噪音多、规模小”的阶段（NISQ），所以我们不能指望它一口气解决所有问题。论文提出的 HAWI 算法，采用了量子+经典混合的这样一种合理搭配，就像团队协作。
图源论文：量子+经典混合算法的工作流程
a）经典计算机：负责把 LWE 问题“转化”成 SVP 问题，并进一步把 SVP 问题“编码”成一种量子计算机能理解的语言——伊辛模型（Ising Hamiltonian）。这是一种描述粒子之间相互作用的能量函数，它的最低能量状态往往对应着问题的解。
b）量子计算机：负责寻找伊辛模型的“最低能量状态”。找到这个最低能量状态，就意味着找到了 SVP 问题中的“最短路线”，从而也就找到了 LWE 问题中的“秘密数字”。
c）经典计算机：再把量子计算机找到的这个最低能量状态“解码”回 LWE 问题的“秘密数字”。
这种分工合作，充分利用了经典计算机的逻辑处理能力和量子计算机在处理特定优化问题上的巨大优势，同时还避开了 NISQ 设备现在还无法处理大规模复杂计算的限制。
3、适应 NISQ 设备：利用量子近似优化算法（QAOA）
寻找伊辛模型的最低能量状态，在量子计算中可以通过多种方法实现，其中一种重要方法就是量子近似优化算法（QAOA）。
QAOA 是专门为 NISQ 设备设计的，它是一种迭代算法，通过不断调整参数，逐步逼近最优解，能够在当前的硬件限制下，通过近似和迭代尽可能发挥量子优势。
本篇论文还特别研究了如何为 QAOA 设计合适的参数，来提高它在解决 LWE 问题上的成功率，就像给 QAOA 做了一本“学习秘籍”，让它能更有效地找到“最短路线”，以及“秘密数字”。
4、实际验证：小步快跑
这篇论文的另一个突破是，他们在 IBM 量子平台上，选择了 2 维 LWE 问题作为测试对象，用一个 5 量子比特的设备验证了这种算法，成功解决了小规模的 LWE 问题。值得一提的是，验证算法所需要的量子比特数量为 m（m+1），其中 m 为样本数量，而在实际应用中，所需的量子比特数量远小于这一理论上限。
图源论文：结果验证了方法的有效性
虽然是小规模的 LWE 问题，但这就像是成功地用真实量子设备“点亮了一盏灯”，足以验证该算法在基本逻辑和流程上的正确性与可行性，为未来解决更大规模的 LWE 问题打下了坚实基础。
总的来说，论文提出的这种方法结合了经典计算的灵活性和量子计算的特定优势，是在当前量子技术水平下，迈向解决重要密码学难题的务实一步。不可避免地，这种方法仍面临一些挑战，例如要将这一算法扩展到解决具有实际密码学意义的更大规模 LWE 问题，其表现仍需进一步验证。
未来，该研究团队还将采用其他方法求解哈密顿量基态，如量子虚时间演化、量子蒙特卡洛（QMC）、量子退火、量子行走等，从而进一步研究 LWE 问题。此外，除了本文所述的短整数解（SIS）策略，LWE 问题还有其他解法路径，如有界距离解码（BDD）策略，这些方法同样与格问题密切相关。因此，研究在与量子优化算法结合时，哪些经典策略在求解格问题中更具效率，是一个值得深入探讨的方向。
Reference：
https://www.nature.com/articles/s42005-025-02126-w#:~:text=Firstly%2C%20we%20use%20classical%20techniques,is%20closer%20to%20the%20solution.