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

406 软件学报 2026 年第 37 卷第 1 期

存储资源过大, 因此需要考虑具体求解的问题规模和掌握的计算资源选取转化至 k 列表问题的量子筛法或直接使
用 Grover 搜索的量子筛法.
2.2.3 基于碰撞搜索的量子启发式筛法
以上介绍的多种量子筛法, 虽然结构不同, 但其基本的设计思路都是将经典搜索转化至量子 Grover 搜索. 事
实上, 该方法应用至元组筛法等算法结构仍有一些不足: (1) 对于元组筛法中的 k 列表问题, 需要求出 k 个系数
(u 1 ,u 2 ,...,u k ), 而 Grover 搜索每次运行只能取得一个系数 u i , 降低了问题求解的效率; (2) 筛法中的某些步骤要求
得到满足相同条件的大量短向量, 而 Grover 搜索在列表中只能搜索得到一个满足条件的元素. 为解决这些问题,
应考虑采用新的量子加速技术应用至量子筛法.
m
n
2021 年, Chailloux 等人 [54] 在筛法中使用量子碰撞问题替代 Grover 搜索. 令 f : {0,1} → {0,1} , n ⩽ m ⩽ 2n 是
随机映射, 量子碰撞问题要求找到此函数的一个碰撞. 该问题的构造相比穷举搜索文献可以将搜索位数折半, 更适
合在元组筛法等筛法版本中应用. 文献 [54] 通过量子漫步构造了量子碰撞求解算法, 复杂度约为 2 m/3 . 2023 年,
Bonnetain 等人 [55] 改进了量子漫步流程, 通过链式漫步算法使量子元组筛法能在同一次漫步过程中求多组碰撞而
不需要反复进行碰撞搜索, 该算法的性质结合元组筛法的结构, 降低了筛法时间复杂度. 除了以上介绍的 2 筛法和
元组筛法, 一系列启发式筛法均可利用 Grover 量子搜索算法进行加速. 由于量子筛法的主要结构与经典算法一致,
故主要的经典筛法都有对应的量子版本. 一些量子启发式筛法的复杂度如表 1 所示.

表 1 部分量子启发式筛法的复杂度指数

筛法类型 空间 经典时间 量子时间
高斯筛法 [35] 0.208 0.415 0.311
哈希筛法 [48] 0.208 0.337 0.286
球筛法 [49] 0.208 0.292 0.268
正轴体筛法 [50] 0.208 0.292 0.268
LD筛法 [51,54] 0.208 0.292 0.257
元组3筛法 [52,56] 0.189 0.566 0.311
NV筛法 [71] 0.208 0.415 0.311
两层筛法 [73] 0.208 0.415 0.311
三层筛法 [74] 0.208 0.415 0.311
元组2筛法 [75] 0.208 0.415 0.311

总结以上量子筛法研究成果, 可将其基本思路和设计模型分为 3 类. (1) 在经典筛法的算法结构基础上, 直接
将向量搜索环节替换为 Grover 量子搜索, 这也是最初始的量子筛法设计方法; (2) 为了针对性加速 k 元组筛法, 将
其中 k 个向量组合得短向量的环节转化为 k 结构问题, 进而得到新的时间存储折中; (3) 将向量组合转化为函数碰
撞的搜索, 以此将搜索空间维数折半, 更进一步使用量子多碰撞算法快速得到一系列碰撞. 上述设计模型的分析比
较见表 2. 量子筛法的下一步发展方向, 一是继续针对算法特殊结构采用创新的量子加速技术; 二是将已构造的量
子加速技术应用至更多的筛法结构或其他算法结构中.

表 2 量子筛法设计模型

应用的量子
文献 算法设计类型 加速环节 加速效果 模型优势 模型劣势
加速技术
[48,49] 直接替换经典穷 每步单次运行Grover 单 个 短 向 量 相比经典搜索 通用性较强, 可适用 加速效果不
Laarhoven等人
搜索构造筛法 量子搜索算法 搜索 平方级加速 于各种筛法类型 充分
Kirshanova等人 [52] 转化至k结构问题 反复运行Grover量 元组筛法中k 调整k改变时间/ 结合筛法特殊结构,
Albrecht等人 [53] 构造筛法 子搜索算法 列表问题 空间折中 针对性加速 需要特殊的
筛 法 结 构 ,
Chailloux等人 [54] 基于量子碰撞构 元组筛法中k 相比经典搜索 采用新的量子加速技 通用性不强
Bonnetain等人 [55] 造筛法 量子漫步算法 列表问题 立方级加速 术, 降低搜索复杂度