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

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

′
1. 随机采样整数 N ∈ [0,N 1 ]
1
2. 初始化空列表 L, S
3. FOR i ← 1,...,N ′
1
4. 采样扰动向量 e ← B n (0,ξµ)
′
5. 转化向量 v ← e mod P(B)
′
6. WHILE w ← search{w ∈ L : ||v ±w|| < γ|| v ||}
′
7. 用 w 约化 v'
′
8. 减去扰动向量 e : v ← v −e
9. IF ||v|| > Rµ
10. 将格向量 v 加入列表 L
11. FOR i ← 1,...,N ′
2
12. 采样扰动向量 e ← B n (0,ξµ)
′
13. 转化向量 v ← e mod P(B)
14. WHILE w ← search{w ∈ L : ||v ±w|| < γ|| v ||}
′
′
15. 用 w 约化 v ′
′
16. 减去扰动向量 e : v ← v −e
17. IF ||v|| > Rµ
18. 将格向量 v 加入列表 S
2
19. (s 1 , s 2 ) ← search{(s 1 , s 2 ) ∈ S : ||s 1 − s 2 || ⩽ µ, s 1 , s 2 }
20. 输出 s 1 − s 2
下面以列表筛法第 19 行搜索近似向量对 (s 1 , s 2 ) ∈ S 2 的操作为例, 讨论如何利用量子计算实现向量搜索. 假
设 S 中已存储足够多的短向量, 计算列表中所有向量对的叠加:
1 ∑ 1 ∑ 1 ∑
√ |s 1 ⟩⊗ √ |s 2 ⟩ 7→ |s 1 , s 2 ⟩.
N 2
N 2 s 1 ∈S N 2 s 2 ∈S
s 1 ,s 2 ∈S
该步骤起到了经典算法中遍历所有向量对的作用. 下一步, 计算向量差 s 1 − s 2 的长度并存储在辅助寄存器中:
1 ∑ 1 ∑
|s 1 , s 2 ⟩|0⟩ aux 7→ |s 1 , s 2 ,||s 1 − s 2 ||⟩.
N 2 N 2
s 1 ,s 2 ∈S s 1 ,s 2 ∈S
接下来, 使用 Grover 量子搜索算法找到满足 ||s 1 − s 2 || ⩽ µ 的向量对. 该算法实际上对满足 ||s 1 − s 2 || ⩽ µ 的量子
态 |s 1 , s 2 ,||s 1 − s 2 ||⟩ 进行了幅值放大, 能以高概率得到如下叠加态:

1 ∑ 1 ∑
|s 1 , s 2 ,||s 1 − s 2 ||⟩ 7→ √ |s 1 , s 2 ,||s 1 −v 2 ||⟩.
N 2 N 2 s 1 ,s 2 ∈S,||s 1 −s 2 ||⩽µ
s 1 ,s 2 ∈S
最后, 通过测量得到一对 (s 1 , s 2 ) 满足 ||s 1 − s 2 || ⩽ µ. 在不改变筛法基本运行流程的前提下, 量子可证明筛法
√ √
将第 6、14、19 行中向量搜索的时间复杂度分别降低至 O(N 1 · |L|) = 2 (c g +3/(2c t ))n+o(n) 、 O(N 2 · |L|) = 2 (c g +c b /2+c t /2)n+o(n) 、
O(|S |) = 2 (c g +c b /2)n+o(n) . 综合以上结果, 可得量子列表筛法的整体时间复杂度为 2 1.799n+o(n) .
AKS 筛法 [35,77] 也可使用类似设计思路进行量子加速. AKS 筛法的主要步骤与列表筛法有所区别, 其筛选操作
主要通过 sieving 子过程实现, 但该子过程同样需要在向量列表中搜索符合条件的格向量, 故可以使用 Grover 量
子搜索算法替代经典的穷举搜索. 经典模型下, 一轮 sieving 子过程的时间复杂度为 2 (c 0 +c s )n+o(n) , 其中 c 0 与 c s 是算法
参数, 而 Grover 量子搜索使其复杂度降低至 2 (c 0 +c s /2)n+o(n) . 与列表筛法类似, 在 AKS 筛法最后也需要搜索向量对

(s 1 , s 2 ) 使其向量差最短, 该步骤复杂度可以由经典算法的 2 (2c R +c u )n+o(n) 降低至量子算法的 2 (3c R /2+c u )n+o(n) . 其中, c R 与 c u
是算法参数. 经典 AKS 筛法的时间复杂度为 2 3.398n+o(n) , 存储复杂度为 2 1.985n+o(n) . 综合上述两个部分的改进, 算法的
整体复杂度可由 2 3.398n+o(n) 降低至 2 2.672n+o(n) .