Page 404 - 《软件学报》2026年第1期

曹金政 等: 格上困难问题量子求解算法综述 401

并讨论格上困难问题量子求解算法的复杂度. 最后, 展望未来可以继续探索的问题. 本文第 1 节介绍格上困难问题
量子求解算法相关的基础知识, 包括格理论和格问题相关定义、量子计算相关背景知识等. 第 2–4 节介绍量子筛
法、量子枚举、量子格基约化这 3 类 SVP 的量子求解算法, 基于算法实例梳理了格上困难问题求解算法由经典
计算模型向量子计算模型迁移的基本设计思想, 并对其设计方法、复杂度估计进行讨论. 其中, 第 2 节介绍量子筛
法, 包括量子可证明筛法和量子启发式筛法. 第 3 节介绍量子枚举算法, 包括基于回溯的枚举和基于变分量子算法
的枚举. 第 4 节介绍量子格基约化. 第 5–8 节介绍针对特殊格上困难问题的量子求解算法, 通过考察特定格问题的
结构, 结合量子计算特性进行加速的算法设计方法, 探讨了多种量子计算技术对问题复杂度的影响. 其中, 第 5 节
介绍 LWE 问题的量子求解算法. 第 6 节介绍对 NTRU 公钥加密体制的量子攻击方法. 第 7 节介绍最近向量问题
的量子求解算法发展现状. 第 8 节介绍特殊结构格上困难问题量子求解算法. 第 9 节对全文进行总结, 并对未来可
以继续探索的问题进行展望.
1 预备知识

本节介绍本文中用到的基础知识, 首先说明格的基本定义与主要的格上困难问题, 如 SVP、 CVP 等, 随后简
介量子计算与量子算法的基本知识.
1.1 格和格上困难问题
本节介绍格的基本知识, 包括格的定义、主要性质和格上困难问题. 更多关于格的知识可参考文献 [6].
定义 1. 格. R 上 m n m m L, 表示为:
个线性无关向量 b 1 , b 2 ,..., b n ∈ R 的整数组合得到的集合, 称为 R 上的格
 
 n ∑ 
 
 
x i b i : x i ∈ Z ,
L(b 1 , b 2 ,..., b n ) = 
 
 
i=1
m
其中, 向量 b 1 , b 2 ,..., b n ∈ R 为一组格基, n 为格的秩, m 为格的维度. 当 m=n, 称格为满秩的. 将基向量为行向量排
{∑ n }
列为格基矩阵 B. 对给定的 B, 定义 P(B) = λ i b i , 0 ⩽ λ i < 1 .
i=1
定义 2. 长度. 令向量 b = [b 1 ,b 2 ,...,b n ] ∈ L, 称 ||b|| = (b +b +...+b ) 为向量 b 的欧几里得范数, 又称为向量
2
2
2 1/2
1 2 n
b 的长度. 在求解格上困难问题时通常考虑向量的长度.
定义 3. 行列式. 设 b 1 , b 2 ,..., b n ∈ R 为格 L 的一组基, b , b ,..., b 为 b 1 , b 2 ,..., b n 进行施密特正交化后所得的
m
∗
∗
∗
1 2 n
n ∗ L 的行列式或体积. 格的行列式仅与格本身有关, 与格中基的选取无关.
向量, 则称 det(L) = Π ||b || 为格
i=1
i
定义 4. 最短向量问题. 给定格 L, 最短向量问题要求寻找最短的非零格向量, 即满足 ||v|| = min{||b|| : b ∈ L\{0}}
的向量 v. 最短向量长度表示为 λ 1 (L).
定义 5. 最近向量问题. 给定格 L 和目标向量 , 最近向量问题要求寻找格向量 v, 满足 ∀b ∈ L, ||v− t|| ⩽ ||b− t||.
t

定义 6. 错误学习问题. 假设 n, q 是正整数, χ 是整数上的一个概率分布. s 是 Z n×1 上的一个秘密向量. 已知给定
q
n
矩阵 A ∈ Z m×n 和根据 χ 采样得到的噪音向量 e ∈ Z m×1 . 给定 (A, b) = (A,< A, s > +e) ∈ Z ×Z q , LWE 问题需要求出 s,
q q q
b i =< A i , s > +e i , i = 1,...,m.
满足
定义 7. NTRU 问题. 假设 n 是正整数, q 是素数, p 是一个小整数. 私钥多项式 f(x) 和生成多项式 g(x) 是未知
−1
量, f, g 的系数为 0 或±1, 公钥多项式 h(x) = p f (x)·g(x) mod q 是已知量. NTRU 问题要求由给定的 h 恢复 f 和 g.
q
1.2 量子计算的基本知识
本节介绍量子算法的基本概念, 主要参考文献 [69]. 量子计算的基本单元是量子比特, 与经典计算的二进制比
特对应, 表示为 |0⟩ 和 |1⟩, 其向量形式为:

[ ] [ ]
0 1
|0⟩ = , |1⟩ = .
1 0
|ψ⟩ = α|0⟩+β |1⟩, 其中复数
两个基态 |0⟩ 和 |1⟩ 构成二维希尔伯特复空间的基, 其线性组合称为叠加态, 表示为
α、 β 满足 |α| +|β| = 1. 使用量子系统的张量积 |ψ 1 ⟩⊗|ψ 2 ⟩ 作为其复合系统 |ψ 1 ψ 2 ⟩. 量子计算通过各种量子门电路
2
2
构造各种功能. 一个量子门对应一个酉矩阵 U, 实现特定的计算功能. 常见的单量子比特门包括 Hadamard 门、