⚛️ quantum physics

On the practicality of quantum sieving algorithms for the shortest vector problem

本文通过详尽的资源估算分析指出，在当前的量子硬件与理论协议条件下，利用格罗弗搜索辅助的量子筛法在密码学相关维度（如400维）求解最短向量问题时，其所需资源（约 $10^{13}$ 个物理量子比特）和时间（约 $10^{31}$ 年）甚至不如单核经典计算机，表明目前量子筛法在密码学安全维度上几乎无法提供实质性的量子加速。

原作者： Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

发布于 2026-04-13

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文就像是一份**“量子计算机破解密码的可行性体检报告”**。

为了让你轻松理解，我们可以把整个故事想象成一场**“寻找宇宙中最短的一根针”**的竞赛。

1. 背景：我们要找什么？（最短向量问题）

想象一下，你有一大堆杂乱无章的长棍子（这些是数学上的“格”），它们交织在一起。你的任务是在这堆棍子里，找出最短的那一根（这就是“最短向量问题”，SVP）。

为什么这很重要？ 现在的很多未来密码（后量子密码）就是基于“找这根最短棍子太难了”这个假设来设计的。如果谁能快速找到它，就能破解这些密码。
现状： 经典计算机（现在的电脑）找这根棍子非常慢，需要几亿年。

2. 大家的期望：量子计算机是“超级侦探”

人们一直认为，量子计算机（Quantum Computer）拥有某种“魔法”，比如格罗弗搜索算法（Grover's Search）。

比喻： 如果经典计算机是在一个巨大的图书馆里，一本一本地翻书找线索，那量子计算机就像是一个拥有“透视眼”的侦探，能同时看所有书，速度理论上快得多（平方级加速）。
之前的理论： 以前的数学理论告诉我们要用这种“透视眼”去破解密码，似乎只需要把时间从“几亿年”缩短到“几千年”，听起来很有希望。

3. 这篇论文做了什么？（算一笔细账）

作者们（Joao, George, Alessandro, Aditya）觉得：“等等，理论归理论，实际上真的行得通吗？”
他们决定不再只看“理论速度”，而是像工程师一样，拿着计算器算一笔极其详细的“资源账单”。他们考虑了所有现实中的麻烦事：

噪音： 量子比特很脆弱，像玻璃做的，稍微有点震动（噪音）就碎了。
纠错： 为了不让玻璃碎，我们需要用很多玻璃片去修补它（量子纠错），这会让资源需求暴增。
内存（QRAM）： 量子计算机需要一种特殊的“超级内存”来读取数据，这种内存非常昂贵且难以制造。
算术： 做数学运算（加减乘除）在量子计算机上比在经典计算机上难得多。

4. 惊人的发现：量子计算机“翻车”了

当他们把所有这些现实成本（特别是纠错和内存）加进去后，结果令人震惊：

场景设定： 假设我们要破解一个目前被认为“最小安全”的密码（维度 D=400）。
量子计算机的需求：
- 物理量子比特数量： 需要大约 10 万亿亿（ $10^{13}$ ） 个物理量子比特。
  - 比喻： 这比地球上所有沙子的数量还要多，或者相当于把整个互联网的所有晶体管都堆在一起，还不够用。
- 所需时间： 即使有了这么多量子比特，算完也需要 $10^{31}$ 年。
  - 比喻： 宇宙的年龄才只有 138 亿年（ $10^{10}$ 年）。这个时间比宇宙存在的时间还要长20 个数量级！
经典计算机的表现： 令人意外的是，一台普通的、单核的、6GHz 的经典电脑，算完同样的任务也只需要 $10^{31}$ 年。

结论： 在目前的硬件水平下，用这种“量子侦探”去破解密码，并没有比用“老式侦探”快多少。甚至可以说，在密码学关心的维度上，量子加速几乎为零。

5. 为什么差距这么大？（罪魁祸首是谁？）

论文指出，最大的瓶颈不是“搜索”本身，而是**“搬运数据”和“保持清醒”**：

量子内存（QRAM）： 为了在量子世界里快速查找数据，我们需要一种极其庞大的内存结构。这就像是为了让侦探看一眼书，我们需要先建造一个比图书馆还大的“书架搬运系统”。这个系统消耗了绝大多数的量子比特。
纠错成本： 量子比特太容易出错，为了维持一个“逻辑上正确”的比特，我们需要成千上万个“物理比特”来当保镖。

6. 总结与启示

这篇论文给狂热的“量子霸权”论泼了一盆冷水，但也指明了方向：

好消息： 目前基于格（Lattice）的密码系统（如 NIST 正在标准化的那些）是非常安全的。即使有了量子计算机，在可预见的未来，它们也不会被攻破。
坏消息： 我们之前对量子计算机破解密码的能力可能过于乐观了。
未来展望： 如果未来真的想实现量子加速，我们不能只靠改进算法，必须要在硬件上有巨大的突破：
- 要么造出极其廉价、高效的量子内存（QRAM）。
- 要么让量子比特变得极其稳定，不需要那么多“保镖”（纠错）。
- 要么发明全新的、不需要这么多资源的量子算法。

一句话总结：
这就好比你听说有一种“光速飞船”能瞬间到达火星，但当你仔细计算燃料、引擎损耗和导航系统后，发现造这艘船需要的能量比整个太阳系的能量还多，而且飞过去的时间比坐蜗牛爬还要慢。所以，别急着担心密码被破，量子计算机离真正破解它们还差着十万八千里呢。

这篇论文《量子筛法算法求解最短向量问题的实用性研究》（On the practicality of quantum sieving algorithms for the shortest vector problem）对基于格的后量子密码学（PQC）的安全性进行了深入的资源评估。作者通过结合格筛法（Sieving Algorithms）与格罗弗搜索（Grover's Search），并考虑了量子纠错、量子随机存取存储器（QRAM）以及具体的物理架构限制，得出了关于量子计算在解决最短向量问题（SVP）上实际优势的结论。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

背景：基于格的密码学是后量子密码学的主要候选方案，其安全性依赖于格问题的最坏情况困难性，特别是最短向量问题（SVP）。
现状：已知量子算法（如格罗弗搜索）可以为解决 SVP 提供渐近加速（指数级指数的降低）。然而，现有的研究大多仅关注渐近复杂度，忽略了实现这些算法所需的实际物理资源（如量子比特数量、时间、纠错开销等）。
核心问题：在密码学感兴趣的维度（例如 NIST 标准中建议的维度 $D \approx 400$ ）下，利用格罗弗搜索加速的量子筛法算法是否真的比经典算法具有显著优势？考虑到实际的硬件限制（噪声、QRAM 成本、纠错），这种加速是否可行？

2. 方法论 (Methodology)

作者对多种经典的筛法算法进行了详细的资源估算，并模拟了它们在容错量子计算机上的实现。主要方法包括：

算法选择：
- NVSieve (Nguyen-Vidick Sieve) 和 GaussSieve。
- 结合局部敏感哈希（LSH）和局部敏感过滤（LSF）的增强版本（如 Angular LSH, Spherical LSH, Spherical LSF）。
- 总共分析了 8 种不同的筛法变体。
量子加速机制：
- 在筛法的搜索步骤中使用格罗弗搜索（Grover's Search）来寻找能缩短向量的向量对。
- 使用了非渐近的格罗弗搜索分析（即不知道解的数量 $M$ 的情况），采用了指数搜索变体。
关键资源考量（这是本文区别于以往工作的核心）：
1. 固定点量子算术：详细计算了加法、比较和乘法电路的开销（使用 Gidney 的加法器和基于教科书乘法的多项式乘法器），假设 32 位精度。
2. 量子随机存取存储器 (QRAM)：采用了**桶式接力（bucket-brigade）**架构的 QRAM 模型。这是资源消耗的主要来源，因为格罗弗搜索需要以叠加态访问经典数据库。
3. 量子纠错 (QEC)：
  - 假设物理比特错误率为 $10^{-5}$ 。
  - 使用**表面码（Surface Codes）**进行逻辑比特编码。
  - 考虑了**魔态蒸馏（Magic State Distillation）**的开销，特别是为了执行非 Clifford 门（如 Toffoli 门），需要多层蒸馏协议以达到极低的逻辑错误率（ $< 10^{-40}$ ）。
4. 物理架构：对比了两种架构：
  - 基线架构 (Baseline)：2D 网格上的最近邻相互作用。
  - 活动体积架构 (Active-Volume)：Litinski 提出的架构，利用非局部连接，仅计算活跃量子比特的时空体积。
5. 经典开销：计算了哈希操作（LSH/LSF）所需的经典计算时间，并将其与量子搜索时间结合。

3. 关键贡献 (Key Contributions)

最全面的资源估算：这是首次对格筛法算法进行包含 QRAM 成本、详细算术电路开销、多层魔态蒸馏以及具体物理架构限制的全面资源估算。
推翻“量子优势”的乐观预期：在密码学相关维度（ $D=400$ ）下，即使采用极其乐观的假设（如 $10^{-5}$ 的错误率、100ns 的码周期、1µs 的反应时间），量子算法并未展现出相对于经典算法的显著优势。
QRAM 的瓶颈作用：明确指出 QRAM 是资源消耗的最大瓶颈。在格罗弗搜索中，为了保持二次加速，必须访问指数级大小的数据库，导致所需的物理量子比特数量主要由 QRAM 决定。
深度限制分析：引入了 NIST 提出的最大电路深度（MAXDEPTH）限制，分析了在深度受限情况下，通过并行化搜索对资源需求的影响。

4. 主要结果 (Key Results)

针对维度 $D=400$ （这是打破 NIST 最低安全级别后量子标准所需的大致维度）：

物理量子比特需求：
- 最优的量子筛法算法（GaussSieve with Spherical LSF）需要约 $10^{13}$ 个物理量子比特。
- 这一数量级远超当前任何量子硬件的能力，甚至超过了现代晶体管的数量级。
- 大部分量子比特（约 90% 以上）用于构建 QRAM。
执行时间：
- 即使拥有上述庞大的量子资源，解决该问题仍需约 $10^{31}$ 年。
- 作为对比，一台 6-GHz 的单核经典计算机解决同样的问题也大约需要 $10^{31}$ 年。
- 结论：在 $D=400$ 时，量子算法相对于经典算法几乎没有加速优势。
维度依赖性：
- 只有在维度远大于 400（例如 $D > 1000$ ）时，量子算法才开始显示出相对于经典算法的加速（约 5 个数量级），但这对于当前的密码学标准来说是不相关的。
QRAM 移除的影响：
- 如果假设 QRAM 成本可以忽略不计（这在物理上极不可能），物理量子比特需求会降至 $10^9$ 左右，但这仍然是一个巨大的工程挑战，且执行时间依然极长。

5. 意义与结论 (Significance & Conclusion)

对后量子密码学的启示：目前的格基密码方案（如 NIST 标准化的 Kyber, Dilithium 等）在面对基于格罗弗搜索的量子攻击时，其安全性评估不需要过度担心“量子筛法”带来的威胁。现有的参数设置（如 $D=400$ ）在考虑了所有实际硬件开销后，对量子计算机依然是安全的。
技术瓶颈：要实现有意义的量子加速，不仅需要理论协议的突破，更需要硬件上的重大飞跃，特别是QRAM 的实现和量子纠错效率的提升。
未来方向：
- 需要更严谨地分析基于量子随机游走（Quantum Random Walks）的筛法算法。
- 需要探索更高效的哈希策略以减少 QRAM 的调用。
- 需要评估能量消耗等其他指标。

总结：这篇论文通过极其详尽和保守的资源估算，有力地证明了在当前的物理假设和理论框架下，利用格罗弗搜索加速的量子筛法算法在解决密码学相关维度的 SVP 问题时，并不具备实际的量子优势。这一结论为后量子密码标准的安全性提供了重要的信心支撑。