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

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

Pauli-X 门、Pauli-Y 门、Pauli-Z 门、Phase 门等. 另一类特殊的门当一个量子比特满足特定条件时, 才对另一个量
子比特执行操作, 称为受控量子门. 对于受控 U 门, 控制位记为 c, 目标位记为 t. 量子门执行 |c⟩|t⟩ 7→ |c⟩U |t⟩, 即当
|1⟩ 时, 对 t 执行 U 操作, 对其他情况不执行操作. 格上困难问题量子求解算法中最常见的组成部分是 Grover
c 为
量子搜索算法. 给定大小为 N 的无序列表 L, 其中目标元素个数为 M, 引入函数 f(x) : {0,1} → {0,1}, 表示为从 n 比
n
特的元素地址到 0 和 1 上的映射. 若地址 x 上的数据 d x 是一个目标元素, 有 f(x)=1, 否则 f(x)=0. Grover 量子搜索
√
算法以 O( N/M) 的复杂度找到使 f(x)=1 的 x, 即找到 L 中一个目标元素. Grover 量子搜索算法中 f(x) 的计算通过
量子预言实现, 包括两部分: 一部分是将数据 d x 通过索引地址 x 读出来, 这一部分常称为 LOAD; 另一部分是通过
判断数据 d x 是否为目标, 若是目标则将目标量子态翻转, 否则量子态保持不变. Grover 量子搜索算法首先准备量
子态, 之后进行多次目标态翻转和关于平均值翻转的迭代. 经过一次迭代, 目标态的幅值增大. 使用 Grover 量子搜
索迭代足够次数, 目标态的幅值可以比较接近 1. 随后进行测量, 算法可以接近 1 的概率得到目标态, 即搜索到了
目标.
量子傅里叶变换是另一种重要的量子算法, 可用在多种组合类算法中. 经典的离散傅里叶变换将时域中 N 维
1 ∑ N−1 2πijk
(x 1 ,..., x N ) 映射到频域中的 N x j e N , i = −1. 类似地, 量子傅里叶变换
2
向量 维向量 (y 1 ,...,y N ), 其中 y k = √
N j=0
∑ N−1
作用在量子态上可实现类似映射. 任意 N 维向量 (x 1 ,..., x N ) 在量子环境下表示为量子态 x j | j⟩. 经过量子傅里
j=0
∑ N−1 ∑ N−1
叶变换后, 得到新的量子态为 x j | j⟩ 7→ y k |k⟩. 用计算基表示, 有:
j=0 k=0
N−1
1 ∑ 2πi jk (|k⟩+e 2πi0.j n |k⟩)(|k⟩+e 2πi0.j n−1 j n |k⟩)...(|k⟩+e 2πi0.j 1 ... j n |k⟩)
| j⟩ 7→ √ e N |k⟩ = √ ,
N j=0 N
n
2
其中, j 1 j 2 ... j n 是量子态 j 的二进制表示, 0.j 1 ... j n = j 1 /2+ j 2 /2 +...+ j n /2 是小数的二进制形式. 经典傅里叶变换
N 2
的时间复杂度为 O(N2 ), 而量子傅里叶变换的时间复杂度 O(N ).
2 量子筛法
本节从算法分类、量子加速原理、算法复杂度估计等方面对量子筛法进行介绍. 量子筛法的算法主要结构与
已有经典筛法相近, 其主要的量子加速手段是用量子搜索替代经典筛法中的格向量筛取、短向量搜索等关键步
骤 [70] . 最早的可证明筛法是 Ajtai 等人 [34] 提出的 AKS 筛法, 算法的主要思想可以总结为: 1) 生成指数级的格向量;
2) 进行多轮筛选, 直到获得足够多的格上短向量; 3) 将上述向量两两相减, 得到格上最短向量. 研究者后续在
AKS 筛法基础上提出了 NV 筛法 [71,72] 、层次筛法 [73,74] 等启发式筛法. 另一类可证明筛法是 Micciancio 等人 [35] 提
出的列表筛法, 该算法定义一个空列表作为初始列表, 随后不断抽取格向量并使用已经在列表中的向量对其进行
约化, 再添加至列表中, 重复此过程直至找到格中最短向量. 后续的研究者参考列表筛法提出了元组筛法 [75,76] 、
BDGL 筛法 [75] 等启发式筛法.
量子计算模型下, 筛法的研究整体表现出从直观到深入, 从交叉融合到结构创新的发展态势. 相比枚举、格基
约化等格上困难问题求解算法, 筛法的量子化较早受到研究者关注, 产生了较多的量子筛法研究成果, 如图 3 所
示. 从筛法算法基本思想与量子加速相结合的方式观察, 量子筛法的整体发展可分 3 个阶段.
第 1 阶段, 量子筛法开始由经典算法向量子算法迁移. 主要设计思路遵循已有经典筛法结构, 将向量搜索步骤
替换为 Grover 量子搜索算法, 其设计方法较为直观. 2013 年, Laarhoven 等人 [48] 首先提出使用 Grover 量子搜索加
速筛法, 在指数层面降低了时间复杂度. 该阶段量子筛法的研究主要聚焦于已有经典筛法向量子计算模型的迁移,
通过原有经典算法结构与量子搜索的交叉产生一系列基于 Grover 量子搜索的量子筛法.
第 2 阶段, 在基于 Grover 的量子算法基础上, 开始对筛法本身的设计思路与算法结构进行调整, 设计更加适
合量子计算模型的量子筛法. 2019 年, Kirshanova 等人 [52] 提出了新的筛法模型 k-结构问题, 最终利用 Grover 搜索
算法求解, 并据此设计对应的量子筛法, 得到了优化的时间存储效率. 该阶段量子筛法突破了已有筛法的常用结
构, 开始针对量子搜索的性质对筛法进行改造, 更好发挥量子加速的作用.