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

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

4 量子格基约化算法

本节介绍基于量子线路的量子格基约化算法, 包括算法设计原理及算法量子线路结构. 经典格基约化算法不
仅是求解格上近似 SVP 的重要手段, 而且在求解多种格上困难问题的过程中发挥关键作用. 实际上, 大多数格问
题都可以归约为求近似最短向量, 进而利用格基约化算法求解. 实际求解格问题过程中, 最常用的算法是 LLL 约
化算法 [39] 、BKZ 约化算法 [40] 及其变形 BKZ 2.0 [82] , 其中 LLL 是第 1 种实用的格基约化算法, 也是后续各种格基
约化算法的结构基础和重要组成部分. LLL 约化算法的一般步骤如算法 2 所示.
算法 2. LLL 算法.
输入: 格基矩阵 B, 参数 δ;
输出: LLL 约化基.

1. i ← 2
2. WHILE i ⩽ n
∗ 2
3. 计算施密特正交系数 u i,j 和 u i,j ||b || , j = 1,...,i−1

j
4. b i = b i −[u i,i−1 ]b i−1 , 更新施密特正交化系数
2
∗ 2
5. IF δ||b || ⩽ ||b || +u 2 ||b || 2
∗
∗
i−1 i i,i−1 i−1
6. FOR j ← i−2 to 0
7. b i = b i −[u i,j ]b j , 更新正交化系数
′
8. v ← x, N ← ⌈(N + N )/2⌉
9. ELSE
10. 交换 b i−1 和 , 更新正交化系数
b i
11. i ← i+1
12. 输出约化基 b 1 ,..., b n
3
文献 [39] 证明, 设给定的 n 维格基中最大长度为 ˜ B, 则通过有理数运算实现的 LLL 约化算法复杂度为 O(n log ˜ B).
6
Schnorr [83] 给出了一个可证明的浮点数近似版本 LLL 约化算法, 将正交化系数用 O(n+log ˜ B) 精度表示, 整体复杂
2
5
4
O(n log ˜ B(n+log ˜ B) ). Nguên 等人 [84] 提出了 2 O(n log ˜ B(n+log ˜ B)). Ryan 等人 [85] 在 LLL
度为 L 约化算法, 复杂度为
运行过程中进行浮点数精度调整, 得到新的启发式 LLL 版本, 复杂度为 O(n (n+log ˜ B) 1+ϵ ), w ∈ (2,3]. 近年来, 量子
w

格基约化方面的研究成果集中在量子 LLL 约化算法的量子线路设计. Tiepelt 等人 [61] 首次提出 LLL 约化算法的量
子版本, 并利用其攻击梅森素数密码体制. 量子 LLL 将主要算法操作通过量子线路进行实现, 主要使用的量子寄
存器种类如表 4 所示.

表 4 量子 LLL 使用量子寄存器种类

寄存器符号 对应变量
|B⟩ 格基
∗
|B ⟩ 正交基
|L⟩ 格基中向量长度
⟩
(i)
U 第i轮的Gram-Schmidt矩阵M
|L⟩ 单个量子比特, 判定格向量是否符合Lovász条件
|I⟩ 主循环计数
|ctl⟩ 控制比特

量子 LLL 中应用的基本量子线路包括加法 A:|x,y,0⟩ 7→ |x,y, x+y⟩、乘法 M:|x,y,0⟩ 7→ |x,y, xy⟩ 和除法 D:|x,y,0⟩

7→ |x,y, x/y⟩. 在基本线路之上, Tiepelt 等人 [61] 为经典 LLL 的循环结构、存储复位、正交化与系数取整、取大值等