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

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

poly(nlogd, logR) 个量子比特. 利用基础量子枚举算法的复
每个对 T 的访问需要 O(logd) 次辅助操作. 算法需要
杂度可估计各种枚举算法版本的量子复杂度. 例如, 使用量子加速的 Kannan 算法需要 O(n n/(4e) )· poly(log(n), log(1/ϵ), β)
次预言机访问和 poly(n,β) 个量子比特, 其中 β 是格向量元素的比特长度.
经典模型下的枚举算法通常使用剪枝方法对枚举树结构进行修改, 以一定的成功率为代价提高求解速度. 类
√
3
似地, 基于量子回溯的量子枚举算法也可使用剪枝方法实现加速. 量子圆筒剪枝的时间复杂度是 O( Tn )·
√
poly(log(n), log(1/ϵ)), 其中 T 是剪枝枚举所搜索的节点个数. 量子离散剪枝的时间复杂度 O(n 2 M)· poly(log(n),
log(M), log(1/ϵ), β) poly(n,β), M 是剪枝过程中使用的参数, 代表最优标签的个数. 量子极限剪枝的时间复杂度

√ √
3 O( M)· poly(n, log(M), log(1/ϵ), β). 具体复杂度如表 3 所示.
O( Tn β)· poly(log(n), log(1/ϵ), log(β), log(m)) 和

表 3 基于量子回溯的量子枚举算法复杂度 (省略对数部分)

枚举 经典时间 量子时间
无剪枝 O(n n/(2e) ) O(n n/(4e) )
√
4
离散剪枝 O(n M) O(n 2 M)
√
6
3
圆筒剪枝 O(Tn ) O( Tn )
√
3
极限圆筒剪枝 O(Tn β ) O( Tn β)
6 2
√
极限离散剪枝 O(M) O( M)

3.2 基于变分量子算法的枚举算法
以上介绍了典型的通过枚举树上量子回溯算法实现的量子枚举算法. 除此之外, 还存在一类基于量子物理模
型实现的量子枚举算法, 基本思路是通过编码将 SVP 归约为 Hamiltonian 算子的基态, 并采用变分量子算法
(variational quantum algorithm, VQA) [79] 等方法进行搜索. Joseph 等人 [80,81] 考虑使用绝热算法求解 SVP 中的量子态
能量差, 在理论上给出了算法的成功条件. Albrecht 等人 [60] 考虑了在受限的量子计算 (noisy intermediate scale
quantum, NISQ) 模型下实现枚举的量子加速. 基于量子绝热算法的量子枚举算法一般情况下使用的量子比特数为
O(3nlog(n/2)+n+logdet(L)). 基于变分量子算法的量子枚
O(nlogn), 而在特定的格结构上所需的量子比特个数为
举算法的主要步骤如下.
(1) 将最短向量问题编码至 H 算子的基态;
(2) 对参数 θ, 取一个拟设态 |ϕ(θ)⟩: 一个简单量子线路输出的一系列量子态;
(3) 制备其中一个量子态并测量. 估计 ⟨ϕ(θ)|H |ϕ(θ)⟩ 的期望值, 用以计算新的参数值 θ;
(4) 使用新的 θ 重复以上步骤, 直到得到符合条件的量子态.
考察量子枚举算法相关研究成果, 可以将量子枚举按照图 6 所示分类. 相比更适合利用量子搜索技术的筛法,
枚举的树搜索结构限制了应用 Grover 量子搜索加速的效果. 为了更好地将枚举与量子计算技术进行结合, 研究者
探索了在枚举算法中使用量子回溯算法和变分量子算法, 实现了量子加速技术与格算法结构的进一步融合, 为格
上困难问题的量子求解算法的后续发展提供了新思路.

经典枚举 构造枚举树 剪枝枚举树 深度优先搜索

树结构对应
枚举算法
基于回溯 构造枚举树 剪枝枚举树 量子回溯搜索
量子
枚举
量子 NISQ 模型
基于 VQA 构造枚举树 求算子基态
量子绝热算法

图 6 量子枚举算法分类