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

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

总体而言, 量子可证明筛法作为量子加速算法在格上困难问题求解中的典型应用, 是最早被关注和研究的格
上困难问题量子求解算法的类别. 在该类算法提出之后, 其设计思路可以广泛地启发其他类别的格算法. 在此基础
上, 研究者设计了量子启发式筛法等结构类似的量子筛法.
2.2 量子启发式筛法
AKS 筛法、列表筛法等可证明筛法使用了随机扰动技术, 增大了算法的实现难度. 实际的格问题求解中常使
用由可证明筛法发展而来的各种启发式筛法, 如 NV 筛法 (NV sieve)、高斯筛法 (Gauss sieve)、元组筛法 (tuple
sieve) 等. 启发式筛法在可证明筛法的基础上取消扰动向量并引入启发式假设, 虽然正确性的理论证明弱于可证明
筛法, 但是时间复杂度显著降低. 在多种量子启发式筛法中, 元组筛法应用了多种量子加速技术, 产生了较多研究
成果. 本节主要以元组筛法为例介绍量子启发式筛法的设计思路与发展过程.
2.2.1 基于 Grover 搜索的量子启发式筛法
元组筛法的核心思想是将 k 个向量进行组合, 得到一个新的短向量, 其特殊形式是 2 筛法, 即组合两个向量得
到新的短向量. 假设 2 筛法过程中 S 集合储存了足够多长度不超过 R 的格向量, 并要求查找符合条件 ||u−v|| ⩽ γR
的 u,v 向量, 这可以通过量子搜索算法实现. 首先计算列表中所有向量对的叠加:

1 ∑ 1 ∑ 1 ∑
√ |u⟩⊗ √ |v⟩ = |u,v⟩.
N N N
u∈S,||u||⩽R v∈S,||v||⩽R u,v∈S
对应经典算法中遍历所有向量对的操作. 接下来计算 ||u−v||:

1 ∑ 1 ∑
|u,v⟩|0⟩ aux 7→ |u,v,||u−v||⟩.
N N
u,v∈S u,v∈S
之后, 使用 γR 的向量对:
Grover 量子搜索, 可获得一个满足向量差长度小于
1 ∑ 1 ∑ ⟩
|u,v,||u−v||⟩ 7→ |u,v,||u 1 −v||⟩+ ϕ junk .
N N
u,v∈S u,v∈S,||u−v||⩽γR
⟩
u−v 并存储在第
通过测量可以去除 ϕ junk , 下一步使用酉变换 U diff 计算 1 个寄存器中, 将新向量命名为 v 1 :

1 ∑ 1 ∑ 1 ∑
U diff |u,v⟩ 7→ |u−v,v⟩ = U diff |v 1 ,v⟩.
N N N
u,v∈S,||u−v||⩽γR u,v∈S,||u−v||⩽γR v 1 =u−v
此时, 量子 2 筛法已经将向量的长度上界由 R 降至 γR. 递归运行量子 2 筛法可以进一步缩短向量, 形成一个
二叉树结构. 完整的量子 2 筛法运行 t = poly(n) 次迭代需要使用 2 个叠加态. 该方法的设计思路与量子可证明筛
t
法类似, 都是将经典算法中的搜索步骤替换为 Grover 搜索. 这种设计思路的优点是算法原理较为直观, 也可以充
分利用量子搜索的平方加速性质.
2.2.2 基于 k 结构问题的量子启发式筛法
2 筛法要求找到满足 ||u±v|| ⩽ γR 的向量对 u,v, 而一般形式的元组筛法需要对确定的整数 k ⩾ 2 找到满足
u 1 ,u 2 ,...,u k . 除了直接利用 Grover 搜索算法设计量子元组筛法, Kirshanova 等人 [52]
||u 1 ±u 2 ±...±u k || ⩽ γR 的向量组
提出了另一种量子元组筛法的设计思路, 将 k 个向量的组合抽象为近似 k 列表问题, 即给定目标长度 t 和相同指数
级别大小的 k 个列表 L 1 ,L 2 ,...,L k , 找到 k 元组 (u 1 ,u 2 ,...,u k ) ∈ L 1 ×L 2 ×...×L k 满足 ||u 1 +u 2 + ...+u k || ⩽ t. Kirshanova

等人进一步将近似 k 列表问题转化为 k 结构问题: 给定 k 个列表 L 1 ,L 2 ,...,L k , Gram 矩阵 C (称为结构) 和 ϵ > 0, 求
(u 1 ,u 2 ,...,u k ) ∈ L 1 ×L 2 ×...×L k 满足 < u i ,u j −C i,j >⩽ ϵ. 量子元组筛法使用以下方法求解 k 结构问题. 首先, 抽取一个

u 1 ∈ L 1 , 并使用 Grover 量子搜索在剩余 k −1 个列表中找到满足 < u 1 ,u i −C 1,i >⩽ ϵ, i ∈ [2,k] 的元素 . 其次, 抽取
u i
u 2 , 用类似方法搜索得到满足 < u 2 ,u i −C 1,i >⩽ ϵ, i ∈ [3,k] 的元素 . 最后, 迭代以上步骤, 直至 i=k. 2023 年, Chailloux
u i
等人 [56] 在文献 [52] 基础上结合编码技术的改进, 简化了归约所得的 k 结构问题, 进一步提高了量子元组筛法效率.
上述基于直接使用 Grover 搜索的方法和转化至 k 列表问题的方法, 区别在于: (1) 设计产生的算法结构不同;
(2) 解决的优化方向不同: 基于 Grover 搜索的方法通过直接替换穷搜索步骤, 意图达到最快的速度, 而基于 k 列表
问题的方法通过调整归约过程的参数, 可以实现算法时间与存储的折中. 考虑到影响筛法效率的一大因素是消耗