HAWI是一种适用于噪声中等规模量子设备（NISQ）的量子-经典混合算法，用于求解容错学习问题（LWE）。它将LWE转化为“找最短路径”问题（SVP），再编码为量子计算可处理的伊辛能量模型。在经典计算协同下，该方法能够利用量子优化算法搜索低能态，从而实现LWE问题求解。LWE是后量子密码的重要基础之一，该研究推导了所需量子比特数的理论上限，并结合数值模拟与真实量子设备实验，验证了算法在小规模实例中的可行性，展示了其在量子密码分析中的潜力。

“容错学习”（Learning-With-Errors,LWE）问题是后量子密码学的核心难题之一，其安全性基于SVP的计算困难，已被广泛应用于抗量子攻击的加密协议中。由于其理论坚固性与构建灵活性，容错学习问题（LWE）被认为是设计未来加密系统的理想基础。然而，随着量子计算的发展，评估量子算法对LWE安全性的影响变得尤为关键，HAWI算法在应对LWE问题上带来了创新突破，可以帮助我们更准确地分析量子计算机的影响，设置密码的安全参数，为后量子密码学和 NISQ 设备的实际应用开辟了新的前景。

 

5 月 20 日，由北京量子院、清华大学、数学工程与先进计算国家重点实验室、南洋理工大学、量子信息前沿科学中心以及北京国家信息科学与技术研究中心共同组成的研究团队，在知名学术期刊《Communications Physics》上发表了一篇题为《Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices》（用于解决 NISQ 设备上容错学习问题的量子经典混合算法）的重要研究论文。该论文由 Muxi Zheng 担任第一作者，魏世杰和龙桂鲁教授为通讯作者。

1. 什么是容错学习问题？

容错学习（LWE）问题，是一种在后量子密码学和计算学习理论中都非常重要的基础计算难题。

虽然大家不一定熟悉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》这篇论文，看看该研究是如何应对 LWE 这一问题的。

2. HAWI创新算法

论文创新性地提出了一种 HAWI 算法，采用一套“组合拳”来应对容错学习（LWE）问题，概括来说就是：

 

将 LWE 问题“转化”成为“找最短路径”问题（SVP），再将转化出的 SVP 问题“编码”成量子计算机能理解的能量模型（伊辛模型）。接下来，利用 NISQ 设备擅长的量子优化算法（如 QAOA），在经典计算机的配合下，寻找能量模型（伊辛模型）的最低点，从而揭示出 LWE 问题的秘密。

2.1 把“找秘密”变成“找最短路径”

LWE 问题本质是“在有噪音的线索中找秘密数字”，论文首先把这个问题巧妙地“转化”或者说“翻译”成了另一个经典的数学难题：最短向量问题（Shortest Vector Problem, SVP）。

 

你可以把 SVP 问题想象成是在一个由很多点组成的“网格”里，我们要找到从原点出发，连接到其他点的“最短的路线”。而这条“最短的路线”，恰好可以对应 LWE 问题中的秘密数字。

 

这种转化很重要，因为 SVP 问题虽然也难，但它有成熟的数学框架和算法研究基础，还更适合量子计算机来处理。

2.2 量子-经典混合：聪明地分配任务

当前的量子计算机还处于“噪音多、规模小”的阶段（NISQ），所以我们不能指望它一口气解决所有问题。论文提出的 HAWI 算法，采用了量子+经典混合的这样一种合理搭配，就像团队协作。

a）经典计算机：负责把 LWE 问题“转化”成 SVP 问题，并进一步把 SVP 问题“编码”成一种量子计算机能理解的语言——伊辛模型（Ising Hamiltonian）。这是一种描述粒子之间相互作用的能量函数，它的最低能量状态往往对应着问题的解。

b）量子计算机：负责寻找伊辛模型的“最低能量状态”。找到这个最低能量状态，就意味着找到了 SVP 问题中的“最短路线”，从而也就找到了 LWE 问题中的“秘密数字”。

c）经典计算机：再把量子计算机找到的这个最低能量状态“解码”回 LWE 问题的“秘密数字”。

上述的这种分工合作，就充分利用了经典计算机的逻辑处理能力和量子计算机在处理特定优化问题上的巨大优势，同时还避开了 NISQ 设备现在还无法处理大规模复杂计算的限制。

2.3 适应 NISQ 设备

NISQ（噪声中等规模量子）设备是目前量子计算发展的关键阶段，指包含约50-500个量子比特、尚未实现纠错能力且易受噪声干扰的量子处理器。这类设备当然也光量子计算机，能在室温下运行并通过光子编码执行特定算法。尽管存在噪声限制，NISQ设备已应用于化学模拟、优化问题等领域，例如利用光量子处理器加速分子动力学计算或药物分子筛选，其混合量子-经典架构正推动实用化探索，为未来容错量子计算奠定基础。

 

寻找伊辛模型的最低能量状态，在量子计算中可以通过多种方法实现。本文通过构建伊辛模型形式的哈密顿量，将LWE问题映射为量子态能量最小化问题，并以紧凑的量子比特编码方式减少对硬件资源的需求，避免了深电路带来的噪声累积，从而使整体算法在当前噪声中等规模量子设备（NISQ）上具有良好的可实现性与稳定性。

2.4 实际验证

这篇论文的另一个突破是，他们选择了 2 维 LWE 问题作为测试对象，用一个 5 量子比特的设备验证了这种算法，成功解决了小规模的 LWE 问题。值得一提的是，验证算法所需要的量子比特数量为 m（m+1），其中 m 为样本数量，而在实际应用中，所需的量子比特数量远小于这一理论上限。

虽然是小规模的 LWE 问题，但这就像是成功地用真实量子设备“点亮了一盏灯”，足以验证该算法在基本逻辑和流程上的正确性与可行性，为未来解决更大规模的 LWE 问题打下了坚实基础。

 

总的来说，论文提出的这种方法结合了经典计算的灵活性和量子计算的特定优势，是在当前量子技术水平下，迈向解决重要密码学难题的务实一步。不可避免地，这种方法仍面临一些挑战，例如要将这一算法扩展到解决具有实际密码学意义的更大规模 LWE 问题，其表现仍需进一步验证。

 

未来，该研究团队还将采用其他方法求解哈密顿量基态，从而进一步研究 LWE 问题。此外，除了本文所述的短整数解（SIS）策略，LWE 问题还有其他解法路径，如有界距离解码（BDD）策略，这些方法同样与格问题密切相关。因此，研究在与量子优化算法结合时，哪些经典策略在求解格问题中更具效率，是一个值得深入探讨的方向。

---

本文改编转载自微信公众号：量子前哨

原论文链接：https://www.nature.com/articles/s42005-025-02126-w#:~:text=Firstly%2C%20we%20use%20classical%20techniques,is%20closer%20to%20the%20solution.

HAWI是一种适用于噪声中等规模量子设备（NISQ）的量子-经典混合算法，用于求解容错学习问题（LWE）。它将LWE转化为“找最短路径”问题（SVP），再编码为量子计算可处理的伊辛能量模型。在经典计算协同下，该方法能够利用量子优化算法搜索低能态，从而实现LWE问题求解。LWE是后量子密码的重要基础之一，该研究推导了所需量子比特数的理论上限，并结合数值模拟与真实量子设备实验，验证了算法在小规模实例中的可行性，展示了其在量子密码分析中的潜力。

“容错学习”（Learning-With-Errors,LWE）问题是后量子密码学的核心难题之一，其安全性基于SVP的计算困难，已被广泛应用于抗量子攻击的加密协议中。由于其理论坚固性与构建灵活性，容错学习问题（LWE）被认为是设计未来加密系统的理想基础。然而，随着量子计算的发展，评估量子算法对LWE安全性的影响变得尤为关键，HAWI算法在应对LWE问题上带来了创新突破，可以帮助我们更准确地分析量子计算机的影响，设置密码的安全参数，为后量子密码学和 NISQ 设备的实际应用开辟了新的前景。

 

5 月 20 日，由北京量子院、清华大学、数学工程与先进计算国家重点实验室、南洋理工大学、量子信息前沿科学中心以及北京国家信息科学与技术研究中心共同组成的研究团队，在知名学术期刊《Communications Physics》上发表了一篇题为《Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices》（用于解决 NISQ 设备上容错学习问题的量子经典混合算法）的重要研究论文。该论文由 Muxi Zheng 担任第一作者，魏世杰和龙桂鲁教授为通讯作者。

1. 什么是容错学习问题？

容错学习（LWE）问题，是一种在后量子密码学和计算学习理论中都非常重要的基础计算难题。

虽然大家不一定熟悉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》这篇论文，看看该研究是如何应对 LWE 这一问题的。

2. HAWI创新算法

论文创新性地提出了一种 HAWI 算法，采用一套“组合拳”来应对容错学习（LWE）问题，概括来说就是：

 

将 LWE 问题“转化”成为“找最短路径”问题（SVP），再将转化出的 SVP 问题“编码”成量子计算机能理解的能量模型（伊辛模型）。接下来，利用 NISQ 设备擅长的量子优化算法（如 QAOA），在经典计算机的配合下，寻找能量模型（伊辛模型）的最低点，从而揭示出 LWE 问题的秘密。

2.1 把“找秘密”变成“找最短路径”

LWE 问题本质是“在有噪音的线索中找秘密数字”，论文首先把这个问题巧妙地“转化”或者说“翻译”成了另一个经典的数学难题：最短向量问题（Shortest Vector Problem, SVP）。

 

你可以把 SVP 问题想象成是在一个由很多点组成的“网格”里，我们要找到从原点出发，连接到其他点的“最短的路线”。而这条“最短的路线”，恰好可以对应 LWE 问题中的秘密数字。

 

这种转化很重要，因为 SVP 问题虽然也难，但它有成熟的数学框架和算法研究基础，还更适合量子计算机来处理。

2.2 量子-经典混合：聪明地分配任务

当前的量子计算机还处于“噪音多、规模小”的阶段（NISQ），所以我们不能指望它一口气解决所有问题。论文提出的 HAWI 算法，采用了量子+经典混合的这样一种合理搭配，就像团队协作。

a）经典计算机：负责把 LWE 问题“转化”成 SVP 问题，并进一步把 SVP 问题“编码”成一种量子计算机能理解的语言——伊辛模型（Ising Hamiltonian）。这是一种描述粒子之间相互作用的能量函数，它的最低能量状态往往对应着问题的解。

b）量子计算机：负责寻找伊辛模型的“最低能量状态”。找到这个最低能量状态，就意味着找到了 SVP 问题中的“最短路线”，从而也就找到了 LWE 问题中的“秘密数字”。

c）经典计算机：再把量子计算机找到的这个最低能量状态“解码”回 LWE 问题的“秘密数字”。

上述的这种分工合作，就充分利用了经典计算机的逻辑处理能力和量子计算机在处理特定优化问题上的巨大优势，同时还避开了 NISQ 设备现在还无法处理大规模复杂计算的限制。

2.3 适应 NISQ 设备

NISQ（噪声中等规模量子）设备是目前量子计算发展的关键阶段，指包含约50-500个量子比特、尚未实现纠错能力且易受噪声干扰的量子处理器。这类设备当然也光量子计算机，能在室温下运行并通过光子编码执行特定算法。尽管存在噪声限制，NISQ设备已应用于化学模拟、优化问题等领域，例如利用光量子处理器加速分子动力学计算或药物分子筛选，其混合量子-经典架构正推动实用化探索，为未来容错量子计算奠定基础。

 

寻找伊辛模型的最低能量状态，在量子计算中可以通过多种方法实现。本文通过构建伊辛模型形式的哈密顿量，将LWE问题映射为量子态能量最小化问题，并以紧凑的量子比特编码方式减少对硬件资源的需求，避免了深电路带来的噪声累积，从而使整体算法在当前噪声中等规模量子设备（NISQ）上具有良好的可实现性与稳定性。

2.4 实际验证

这篇论文的另一个突破是，他们选择了 2 维 LWE 问题作为测试对象，用一个 5 量子比特的设备验证了这种算法，成功解决了小规模的 LWE 问题。值得一提的是，验证算法所需要的量子比特数量为 m（m+1），其中 m 为样本数量，而在实际应用中，所需的量子比特数量远小于这一理论上限。

虽然是小规模的 LWE 问题，但这就像是成功地用真实量子设备“点亮了一盏灯”，足以验证该算法在基本逻辑和流程上的正确性与可行性，为未来解决更大规模的 LWE 问题打下了坚实基础。

 

总的来说，论文提出的这种方法结合了经典计算的灵活性和量子计算的特定优势，是在当前量子技术水平下，迈向解决重要密码学难题的务实一步。不可避免地，这种方法仍面临一些挑战，例如要将这一算法扩展到解决具有实际密码学意义的更大规模 LWE 问题，其表现仍需进一步验证。

 

未来，该研究团队还将采用其他方法求解哈密顿量基态，从而进一步研究 LWE 问题。此外，除了本文所述的短整数解（SIS）策略，LWE 问题还有其他解法路径，如有界距离解码（BDD）策略，这些方法同样与格问题密切相关。因此，研究在与量子优化算法结合时，哪些经典策略在求解格问题中更具效率，是一个值得深入探讨的方向。

---

本文改编转载自微信公众号：量子前哨

原论文链接：https://www.nature.com/articles/s42005-025-02126-w#:~:text=Firstly%2C%20we%20use%20classical%20techniques,is%20closer%20to%20the%20solution.