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

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

3 量子枚举算法

本节介绍量子枚举算法的设计思想、算法结构与复杂度估计. 量子枚举的发展脉络如图 5 所示. 枚举是与筛
法并列的 SVP 精确求解算法, 也是求解多种上困难格问题的重要方法. 经典模型下的枚举算法考虑以原点为中心
∑
的特定球中包含的向量. 由于任意的格中向量 u ∈ L 均可分解为格基向量 b 1 ,..., b n 的组合 u = u i b i , 故枚举算法
i
通过系数 (u 1 ,u 2 ,...,u n ) 表示格向量并构造枚举树.

Montanaro 等人 , 2018 Cerezo 等人 , 2021
[79]
[78]
量子回溯算法 经典模型枚举算法 变分量子算法
[80]
Aono 等人 , 2018 Albrecht 等人 , 2023 Joseph 等人 , 2020
[60]
[32]
量子回溯枚举 面向 NISQ 模型构造量子枚举 绝热量子计算构造枚举
Bindel 等人 , 2023 Bai 等人 , 2023 Joseph 等人 , 2021
[81]
[59]
[58]
有限深度下复杂度分析 量子枚举复杂度估计 量子 Ising 枚举
图 5 量子枚举算法发展概况

相比筛法多样化的量子版本设计模式, 枚举的算法结构决定了其与量子计算的结合更加困难. 枚举算法在球
′
′
中所有的 (u 1 ,u 2 ,...,u n ) 组合中从右至左进行深度优先搜索, 查找所有满足存在 (u ,u ,...,u ′ n−1 ,u n ) 的参数 . 找到所
u n
1
2
u n−1 . 可以发现枚举算法对系数进行顺序搜
有可能的 u n 之后, 再针对每个 u n 搜索对应的 u n−1 , 进而以此类推搜索至
索 [49] , 前一个 u i 的值引出多个可能的 u i−1 值, 搜索空间随算法运行不断变化; 然而 Grover 量子搜索要求搜索集合
是提前已知且可编号的, 故枚举算法中无法直接调用量子搜索进行优化. 虽然 Grover 量子搜索无法直接应用于枚
举算法, 但研究者通过考察枚举算法结构和量子物理和量子计算模型设计了多种量子枚举. 总体而言, 量子枚举的
设计思路有: (1) 沿用经典算法的枚举树结构, 利用树结构上量子回溯算法加速目标节点搜索; (2) 将短向量搜索过
程转化为量子物理模型中 Hamilton 算子求基态, 并利用对应量子算法进行模拟. 下面分别对两种量子枚举类型进
行介绍.
3.1 基于量子回溯的枚举算法
Aono 等人 [57] 提出了第 1 种设计量子枚举算法的新思路, 其主要应用的量子加速技术是量子回溯算法. 枚举算

法构造的枚举树 T 中上每个节点代表部分候选值 u i ,u i+1 ,...,u n , 其子节点代表扩展信息 u 1 ,u 2 ,...,u i−1 . 回溯算法可
#V(T ) 次, 即搜
以判定树 T 中是否包含目标向量即标记点, 并输出这样的目标点. 经典回溯算法需要访问预言机
索树上节点的个数, 而 Montanaro [78] 提出了量子版本的回溯算法: 给定 ϵ > 0, 度为 d(T ) = O(1) 的树 , 预言机 P,
T
树深度的上界 n, 存在量子回溯算法 FindSolution(T ,P,n,ϵ) 输出 x 使得 P(x) 为真, 或输出“不存在”. 量子回溯算法进
√
3/2
行 O( #V(T )n log(n)log(1/ϵ)) 次对 T 和 P 查询, 正确概率至少 1−ϵ, 每次查询使用 O(1) 次辅助操作, 使用 poly(n)
个量子比特. 基于量子回溯构造枚举的主要步骤总结如下.
(1) 按照经典枚举的方法进行格向量投影和枚举树构造.
(2) 将经典枚举树转化为等价二叉树.
(3) 以新的二叉树为输入, 运行量子回溯算法找到目标节点.
(4) 由该节点恢复目标短向量.
Aono 等人 [57] 给出了量子枚举算法复杂度的理论估计. Bai 等人 [58] 给出了枚举量子线路设计, 并对量子枚举的
复杂度做了更详细的估计. Bindel 等人 [59] 进一步讨论了量子计算深度受限情况下量子枚举算法的复杂度. 给定
ϵ > 0, 枚举树 T 的度上界 d, 预言机 P, 向量长度的函数为 g, 此时量子枚举算法可以输出使 g 取最小值的节点 N, 概率为
√ ⌈ ⌉ ⌈ ⌉
O( T(nlogd) 3/2 T = #V(T ).
1−ϵ . 量子枚举算法需要 log(nlogd)log( log R /ϵ) log R ) 次对 T 和 P 的访问, 其中
2
2