# 格问题的量子过滤：QFT 对偶性、LWE-like States 与参数边界 格上的最短向量问题（SVP）与最近向量问题（CVP）是后量子密码的安全基石：目前主流的标准化方案都把安全性归约到这类问题的困难性上。对**一般**的 SVP/CVP，我们不知道任何多项式时间的量子算法——这与整数分解、离散对数被 Shor 算法一举攻克形成了鲜明对比。因此，一个自然的问题是：量子计算对格问题究竟"差在哪一步"，而这差距能否被某种新的量子技巧补上？ Chen、Liu 与 Zhandry（Zoo 编号 498）给出的答案出人意料地具体：差距集中在 **Fourier 对偶归约中的误差分布**上。他们的办法是在 Regev 风格的 Fourier duality 框架中插入一个非平凡的量子 **measurement filter（测量过滤器）**，在测量之前相干地重塑误差振幅，把原本"差一点够用"的归约推进可解的参数区域。由此得到的是针对**特定 average-case 变体**——很宽矩阵的 SIS$_\infty$、带量子样本的 LWE、外推二面体陪集问题（EDCP）——的多项式时间量子算法。 本教程假设读者已掌握本站前几章的内容：量子力学与量子计算基础（ch01）、QFT 与相位估计（ch03）、Grover 与振幅放大（ch03）、以及 QSP/QSVT 中"用辅助比特实现非酉变换"的思想（ch05）。我们会用到这些工具，但不再重新推导它们。 阅读路线图：第 1 节讲历史与动机；第 2 节固定格与对偶格的记号；第 3 节推导 Poisson 求和公式——这是"QFT 交换 primal 与 dual"的全部数学来源；第 4 节定义 LWE 与 LWE-like 量子态，并把双寄存器 QFT 完整算一遍；第 5 节是本教程的核心，讲量子过滤器如何重塑误差分布，并附一个可手算的数值例子；第 6 节介绍三类可解变体；第 7 节解释为什么这一切**没有**攻破主流后量子方案；第 8 节把它与同章 DQI 算法的共同结构对照。 :::{admonition} 本课知识点 :class: tip 1. **[格上的量子困局](#lattice-quantum-gap)**——能解释为什么 Shor 的阿贝尔 HSP 思路不能直接攻克 SVP/CVP，并列出 Fourier 对偶归约中累积参数损失的三个来源。 2. **[格与对偶格](#lattice-dual-basics)**——能写出格、对偶格与 SVP/CVP/BDD 的定义，推导 $\mathcal L^*=B^{-T}\mathbb Z^n$ 并计算 $\det\mathcal L^*=1/\det\mathcal L$。 3. **[Poisson 求和与对偶结构](#poisson-sum-duality)**——能按四步推导周期化 Gaussian 的 Poisson 求和公式，说明支撑集、宽度反转与平移变相位，并在一维格上手算各峰的位置、权重与相位。 4. **[LWE-like 量子态与双 QFT](#lwe-state-double-qft)**——能写出 LWE 样本与 LWE-like 量子态并验证归一化，完成双寄存器 QFT 的计算导出误差剖面 $\eta(k)$，并比较相干剖面 $\eta$ 与特征函数 $\widehat D$。 5. **[量子过滤器的数学](#quantum-filter-math)**——能从受控旋转 $U_F$ 出发推导 $P$、$D'$ 与 $\eta_F(k)$ 三条公式，并解释为什么过滤是本质量子的步骤、复值 $F$ 多出哪些自由度。 6. **[好过滤器的条件与复杂度](#filter-conditions-complexity)**——能列出好过滤器的三个条件并解释其相互拉扯，写出四因子复杂度乘积与振幅放大改进，用夹逼论证可行区间 $[r_{\min},r_{\max}]$ 何时非空。 7. **[可手算的过滤例子](#filter-toy-example)**——能复算 $q=8$ 例子中过滤前后的 $\eta(k)$、$p(k)$ 与 $p_F(k)$，解读垃圾频率质量的转移，并说明玩具例与渐近区域的差别。 8. **[可解变体与密码学边界](#solvable-variants-boundary)**——能列出三类可解变体及其参数条件，并逐条解释为什么它们不落入主流后量子方案的困难参数区域。 ::: (lattice-quantum-gap)= ## 1. 来龙去脉：格密码与"差一步"的量子归约 ### 1.1 格问题为什么重要 1996 年 Ajtai 给出了第一个从最坏情况格问题到平均情况问题的归约：如果某个随机生成的格实例上的"短整数解"问题（SIS）能被有效求解，那么所有格上的近似 SVP 都能被有效求解。这类 worst-case/average-case 连接是格密码最有吸引力的性质——破解一个随机公钥等价于破解**所有**格实例。2005 年 Regev 引入 LWE（Learning With Errors）问题并给出量子归约，把它锚定在 worst-case 格问题上；此后 LWE 与 SIS 成为后量子密码标准化的主力假设。 与此相对，SVP/CVP 本身的算法研究给出的是一条很陡的复杂度曲线（见下一小节）。这意味着密码学家可以选取参数使已知经典与量子攻击都失效——除非出现结构上的新突破。 ### 1.2 经典算法能做什么 对经典算法，格问题的现状大致是： - **多项式时间内只能拿到指数级近似**。LLL 算法及其块化推广（BKZ）在多项式时间内求得的"短向量"，长度可以达到 $2^{O(n)}$ 倍于真实最短向量；要把近似因子压到 $\mathrm{poly}(n)$，已知算法的运行时间就变成次指数乃至指数。 - **精确或近精确求解需要指数时间**。求解（近似因子接近 1 的）SVP/CVP 的已知最好算法——枚举（enumeration）与筛法（sieving）——运行时间都是 $2^{\Theta(n)}$ 量级。量子计算对筛法有加速，但只是降低指数中的常数因子，并没有改变"指数时间"这一定性结论。 换句话说，在经典世界里，"近似因子"与"运行时间"之间存在一条坚硬的权衡曲线，而密码方案恰好把参数放在这条曲线的安全一侧。 ### 1.3 量子侧的历史线：为什么 Shor 的思路不直接适用 回顾 Shor 算法（ch04）：整数分解与离散对数都能归约到**阿贝尔群上的隐藏子群问题（HSP）**，而阿贝尔群的 Fourier 变换（QFT）能把隐藏的周期性一次性读出。格问题也有一只"隐藏的周期结构"——格本身就是一个周期点阵——但它对应的群论对象不是阿贝尔群，而是**二面体群（dihedral group）**这样的非阿贝尔群。 2002 年 Regev 形式化了**二面体陪集问题（DCP）**：给定若干个形如"叠加在 $j$ 上、同时叠加在 $x+js \bmod N$ 上"的量子态，要求恢复隐藏的 $s$。他证明：如果 DCP 有多项式时间量子算法，那么 $\mathrm{poly}(n)$ 近似的（unique）SVP 也有多项式时间量子算法。问题在于，二面体群上的 QFT 并不能像阿贝尔情形那样直接读出隐藏元——迄今对 DCP 及其背后的二面体 HSP，已知最好的量子算法仍只是**次指数**的（Kuperberg 的筛法）。这就是"差的一步"。 2003 年 Aharonov 与 Ta-Shma（Zoo 编号 5）发展了绝热态制备与"lattice state"技术，系统地研究了制备格周期态、对其做 QFT 能得到什么；Regev 的归约（Zoo 编号 78）则把格问题、二面体陪集态与 LWE 型样本连成了一条链。这条链的每一环都会损失一点参数——损失的来源是 Gaussian 尾部、模数离散化、以及需要区分的相位精度——二十年来，这些损失累加起来，恰好把多项式算法挡在了门外。 Chen–Liu–Zhandry 的观察是：链条中最薄弱环节是**误差分布的形状**，而误差分布在量子世界里不是被动给定的——在测量之前，可以用一个相干的过滤器去**整形**它。这就是本教程的主题。 (lattice-dual-basics)= ## 2. 格、对偶与基本问题 **定义（格）**。给定满秩基矩阵 $B\in\mathbb R^{n\times n}$（列向量 $b_1,\dots,b_n$ 线性无关），它生成的**格（lattice）**是所有整数系数线性组合的集合： $$ \mathcal L(B)=\{Bz:z\in\mathbb Z^n\}. $$ 直觉：格是 $\mathbb R^n$ 中一个规则的、离散的、向各方向无限延伸的点阵，$B$ 的列是它的"基本步长"。同一个格有很多组基：若 $U$ 是行列式为 $\pm1$ 的整数矩阵（unimodular），则 $B$ 与 $BU$ 生成同一个格，因为 $U\mathbb Z^n=\mathbb Z^n$。格的基本平行体体积 $\det\mathcal L=|\det B|$ 因此与基的选取无关，是格本身的不变量。 **定义（对偶格）**。格 $\mathcal L$ 的**对偶格（dual lattice）**是与所有格点内积都为整数的向量集合： $$ \mathcal L^* =\{y\in\mathbb R^n:\langle y,x\rangle\in\mathbb Z, \ \forall x\in\mathcal L\}. $$ 我们来推出它的显式形式。条件"$\langle y,x\rangle\in\mathbb Z$ 对所有 $x\in\mathcal L$ 成立"只需对基向量检验（任意格点是基向量的整系数组合，内积是线性的）：$\langle y,b_i\rangle\in\mathbb Z$ 对所有 $i$ 成立，即 $B^Ty\in\mathbb Z^n$，即 $y\in B^{-T}\mathbb Z^n$。因此 $$ \mathcal L^*=B^{-T}\mathbb Z^n, $$ 也就是说对偶格以 $B^{-T}$ 为一组基。取行列式得 $\det\mathcal L^*=1/\det\mathcal L$：**原格越密（基本体积越小），对偶格越疏**，这个反转关系是后面一切"宽度反转"现象的根源。 **小例子**。取 $B=\begin{pmatrix}2&0\\0&3\end{pmatrix}$，则 $\mathcal L$ 是平面上横坐标为偶数、纵坐标为 3 的倍数的点阵，$\det\mathcal L=6$。对偶基 $B^{-T}=\begin{pmatrix}1/2&0\\0&1/3\end{pmatrix}$，即 $\mathcal L^*$ 由步长 $1/2$ 与 $1/3$ 生成，$\det\mathcal L^*=1/6$。逐点验证：$y=(1/2,0)$ 与任意格点 $x=(2a,3b)$ 的内积是 $a\in\mathbb Z$，确实满足对偶条件。 **基本问题**。记 $\lambda_1(\mathcal L)=\min_{v\in\mathcal L\setminus\{0\}}\|v\|$ 为最短非零向量长度。 - **SVP（最短向量问题）**：给 $B$，找 $v\in\mathcal L\setminus\{0\}$ 使 $\|v\|=\lambda_1$。近似版本允许 $\|v\|\le\gamma(n)\lambda_1$。 - **CVP（最近向量问题）**：给 $B$ 与目标点 $t\in\mathbb R^n$，找 $v\in\mathcal L$ 使 $\|v-t\|$ 最小。 - **BDD（有界距离解码）**：CVP 的 promise 版本——事先保证 $t$ 到格的距离不超过某个半径 $r$。当 $r<\lambda_1/2$ 时解唯一：若两个格点 $v_1\ne v_2$ 都满足 $\|v_i-t\|\le r$，则由三角不等式 $\|v_1-v_2\|\le2r<\lambda_1$，但 $v_1-v_2$ 是非零格点，矛盾。BDD 是 LWE 译码视角的格语言表述。 这些问题的**近似因子**决定了困难性与密码的关联：worst-case/average-case 归约说，破解 SIS/LWE 密码意味着能以某个 $\mathrm{poly}(n)$ 近似因子求解 worst-case 格问题；而因子越大问题越容易。第 7 节讨论"为什么新算法不威胁密码"时，近似因子是关键判据。 ## 3. QFT 为什么交换 primal 与 dual 本节推导本教程的数学引擎：**Poisson 求和公式**。它告诉我们：在格上做周期化的 Gaussian，其 Fourier 变换恰好支撑在对偶格上，且宽度反转、平移变相位。量子算法中"对格周期态做 QFT 得到对偶格信息"这一全部现象，都是这个恒等式的离散化身。 (poisson-sum-duality)= ### 3.1 Poisson 求和：逐步推导 固定宽度参数 $s>0$ 与平移 $t\in\mathbb R^n$，考虑 Gaussian 峰 $f(x)=e^{-\pi\|x\|^2/s^2}$ 在格 $\mathcal L$ 上的**周期化和** $$ \Psi_{\mathcal L,t}(x) =\sum_{v\in\mathcal L} f(x-v-t) =\sum_{v\in\mathcal L} e^{-\pi\|x-v-t\|^2/s^2}. $$ 直觉上，$\Psi$ 是在每个格点附近放一座宽度 $s$ 的 Gaussian 小山再全部加起来。我们分四步算它的 Fourier 变换。 **第 1 步：$\Psi$ 是 $\mathcal L$-周期函数。**对任意 $u\in\mathcal L$， $$ \Psi(x+u)=\sum_{v\in\mathcal L}f(x+u-v-t)=\sum_{v'\in\mathcal L}f(x-v'-t)=\Psi(x), $$ 其中第二个等号用了换元 $v'=v-u$：因为 $u\in\mathcal L$，当 $v$ 跑遍 $\mathcal L$ 时 $v-u$ 也跑遍 $\mathcal L$（格对加法封闭）。由于 Gaussian 衰减极快，这个级数绝对收敛且各阶光滑，求和与换元都合法。 **第 2 步：周期函数的 Fourier 展开只允许对偶格频率。**$\mathbb R^n/\mathcal L$ 上的光滑周期函数可以展开成 Fourier 级数 $$ \Psi(x)=\sum_{w\in\mathcal L^*}c_w\,e^{2\pi i\langle w,x\rangle}. $$ 为什么频率必须落在 $\mathcal L^*$？因为每个 Fourier 基元 $e^{2\pi i\langle w,x\rangle}$ 本身必须满足 $\mathcal L$-周期性：$e^{2\pi i\langle w,x+v\rangle}=e^{2\pi i\langle w,x\rangle}$ 对所有 $v\in\mathcal L$ 成立，当且仅当 $\langle w,v\rangle\in\mathbb Z$，当且仅当 $w\in\mathcal L^*$（这正是对偶格的定义）。所以"周期在 $\mathcal L$ 上"与"频率在 $\mathcal L^*$ 上"是同一件事的两面。 **第 3 步：计算 Fourier 系数。**用基本区域（fundamental domain）$\mathcal F=\mathbb R^n/\mathcal L$（体积 $\det\mathcal L$）上的标准内积， $$ c_w=\frac{1}{\det\mathcal L}\int_{\mathcal F}\Psi(x)e^{-2\pi i\langle w,x\rangle}\,dx =\frac{1}{\det\mathcal L}\int_{\mathcal F}\sum_{v\in\mathcal L}f(x-v-t)e^{-2\pi i\langle w,x\rangle}\,dx. $$ 因为 $w\in\mathcal L^*$ 且 $v\in\mathcal L$，有 $e^{-2\pi i\langle w,v\rangle}=1$，于是可把相位改写为 $e^{-2\pi i\langle w,x-v\rangle}$；再把求和与积分交换（绝对收敛保证合法），并对每一项换元 $x\mapsto x+v$：基本区域平移 $v$ 后恰好无缝拼满整个 $\mathbb R^n$，所以 $$ c_w=\frac{1}{\det\mathcal L}\int_{\mathbb R^n}f(x-t)e^{-2\pi i\langle w,x\rangle}\,dx =\frac{1}{\det\mathcal L}\,e^{-2\pi i\langle w,t\rangle}\,\widehat f(w), $$ 第二个等号对积分做平移 $x\mapsto x+t$，把 $t$ 从 $f$ 的自变量搬到相位因子里。 **第 4 步：代入 Gaussian 的 Fourier 变换。**在约定 $\widehat f(y)=\int f(x)e^{-2\pi i\langle x,y\rangle}dx$ 下，$f(x)=e^{-\pi\|x\|^2/s^2}$ 的变换是 $\widehat f(y)=s^n e^{-\pi s^2\|y\|^2}$——**宽度从 $s$ 反转为 $1/s$**（自变量越宽，频谱越窄，这是 Fourier 变换的测不准性质）。合并得 $$ \widehat\Psi(y) \propto \sum_{w\in\mathcal L^*} e^{-\pi s^2\|w\|^2} e^{-2\pi i\langle w,t\rangle} \delta(y-w). $$ 把四步串起来读这个公式： - **支撑集**：primal 周期函数的频率全部落在对偶格 $\mathcal L^*$ 上（第 2 步）； - **宽度反转**：primal 中 Gaussian 宽度为 $s$，dual 中包络 $e^{-\pi s^2\|w\|^2}$ 作为频率 $w$ 的函数宽度为 $\sim 1/s$（第 4 步）——原格的"近处结构"映射为对偶格的"远处结构"； - **平移变相位**：primal 中的平移 $t$（对应 CVP/BDD 的目标点！）在对偶侧变成每个频率 $w$ 携带的相位 $e^{-2\pi i\langle w,t\rangle}$（第 3 步）。单次测量会丢掉相位（概率是振幅模方），但相位就在振幅里，可以被相干的后续电路利用——这正是量子算法比"直接采样对偶格点"多出来的东西。 ### 3.2 一个可手算的一维例子 取一维格 $\mathcal L=a\mathbb Z$（$a>0$），$t=0$。对偶格是 $\mathcal L^*=\frac1a\mathbb Z$（验证：$\langle k/a,am\rangle=km\in\mathbb Z$）。上面的公式给出 $$ \Psi(x)=\sum_{m\in\mathbb Z}e^{-\pi(x-am)^2/s^2} =\frac{s}{a}\sum_{k\in\mathbb Z}e^{-\pi s^2k^2/a^2}\,e^{2\pi ikx/a}. $$ 代入数值 $a=2$、$s=1/2$：频率峰位于 $y=k/2\in\frac12\mathbb Z$，权重为 $e^{-\pi k^2/16}$。逐个算： $$ k=0:\ 1;\qquad k=\pm1:\ e^{-\pi/16}\approx0.822;\qquad k=\pm2:\ e^{-\pi/4}\approx0.456;\qquad k=\pm3:\ e^{-9\pi/16}\approx0.170. $$ 现在把 primal 宽度加倍到 $s=1$（其他不变）：权重变成 $e^{-\pi k^2/4}$，即 $$ k=0:\ 1;\qquad k=\pm1:\ e^{-\pi/4}\approx0.456;\qquad k=\pm2:\ e^{-\pi}\approx0.043. $$ primal 的小山变宽一倍，dual 的包络就收窄一倍——宽度反转直接可见。若再把 $t$ 从 $0$ 改为 $t=1/2$，所有权重模不变，但第 $k$ 个峰乘上相位 $e^{-2\pi i k\cdot(1/2)/2}=e^{-\pi ik/2}$，依次是 $1,-i,-1,i,\dots$——平移信息完整地编码在相位序列里。 ### 3.3 从连续公式到量子寄存器 量子算法用不了连续变量，实际制备的是**离散化的周期 Gaussian 态**：取模数 $q$，在寄存器上制备（近似） $$ |\Psi\rangle\propto\sum_{x\in\mathbb Z_q^n}\Big(\sum_{v\in\mathcal L}e^{-\pi\|x-v-t\|^2/s^2}\Big)|x\rangle, $$ 然后作用 $\mathbb Z_q^n$ 上的 QFT。Poisson 公式的离散版本说：测量结果近似服从对偶格点（按 $q$ 折回）上的 Gaussian 分布，权重 $\propto e^{-\pi s^2\|w\|^2}$；而 $t$ 的信息留在振幅相位中。Aharonov–Ta-Shma（Zoo 编号 5）与 Regev（Zoo 编号 78）的归约正是用这种结构，把格问题、二面体陪集态、LWE 型样本相互联系起来。 但要让归约多项式时间跑通，需要三件事同时成立：Gaussian 尾部足够小（否则有限模数 $q$ 截断引入的"折回"误差污染频谱）、模数离散化足够细（否则对偶频率读不准）、需要区分的相位间隔足够大（否则少量样本分不开候选相位）。这三个来源各损失一点参数——第 1.3 节说的"差的一步"，在技术上就是这些损失的累积。过滤技巧要修理的正是这个环节。 (lwe-state-double-qft)= ## 4. LWE 与 quantum sample ### 4.1 经典 LWE **定义（LWE 样本）**。固定维数 $n$、模数 $q$、秘密 $s\in\mathbb Z_q^n$ 与 $\mathbb Z_q$ 上的误差分布 $D$。一个 **LWE 样本**是 $$ (a,\;b=\langle a,s\rangle+e\bmod q), $$ 其中 $a\in\mathbb Z_q^n$ 均匀随机，$e\leftarrow D$ 是小的误差。LWE 问题是：给定多项式个独立样本，恢复 $s$。 **误差是必不可少的。**若没有误差（$e\equiv0$），每个样本给出一个线性方程 $\langle a,s\rangle=b$（在 $\mathbb Z_q$ 上），收集 $n$ 个独立方程后 Gaussian 消元立即解出 $s$。误差 $e$ 破坏了精确的线性关系：它把"解线性方程组"变成"带噪解码"，而带噪解码正是格上 BDD 问题的化身——这是 LWE 困难性的来源，也是 Regev 归约的接口。 ### 4.2 LWE-like 量子态 现在把"经典样本"升级为"相干叠加"。**LWE-like 量子态**保留 error 与线性关系的叠加，抽象写成 $$ |\psi_s\rangle =\frac{1}{q^{n/2}}\sum_{a\in\mathbb Z_q^n}\sum_{e\in\mathbb Z_q}\sqrt{D(e)} \,|a\rangle\, |\langle a,s\rangle+e\bmod q\rangle. $$ 先检查归一化：固定 $a$ 时，$e$ 跑遍 $\mathbb Z_q$ 给出 $q$ 个互不相同的基矢，内积 $\sum_e D(e)=1$；不同 $a$ 的块彼此正交；总范数平方为 $q^{-n}\cdot q^n\cdot1=1$。 与经典样本的本质区别在**相干性**：振幅 $\sqrt{D(e)}$ 不是概率，不同 $e$ 的分量之间可以干涉。下面会看到，正是这个干涉让 Fourier 技术有发挥空间——也正是过滤器可以下刀的地方。 ### 4.3 两个寄存器上做 QFT：完整计算 记 $\omega_q=e^{2\pi i/q}$，采用约定 $\mathrm{QFT}_q|b\rangle=q^{-1/2}\sum_k\omega_q^{kb}|k\rangle$。我们分两步，每步算到底。 **第 1 步：对第二寄存器做 QFT。**把 $b=\langle a,s\rangle+e$ 代入，相位因子分裂为 $\omega_q^{kb}=\omega_q^{k\langle a,s\rangle}\cdot\omega_q^{ke}$，于是 $$ |\psi_s\rangle\longmapsto \frac{1}{q^{(n+1)/2}}\sum_{a,k}\Big(\underbrace{\sum_{e}\sqrt{D(e)}\,\omega_q^{ke}}_{=:\,\eta(k)}\Big)\omega_q^{k\langle a,s\rangle}\,|a\rangle|k\rangle. $$ 这里出现了本教程的关键量——**误差振幅的 Fourier 剖面** $$ \eta(k):=\sum_{e\in\mathbb Z_q}\sqrt{D(e)}\,\omega_q^{ke}. $$ 注意 $\eta$ 是**振幅** $\sqrt D$（而非概率 $D$）的 Fourier 变换：它来自相干叠加，不同 $e$ 的贡献先相加再取模方。由 Parseval 恒等式，$\sum_k|\eta(k)|^2=q\sum_e D(e)=q$，这个等式马上用来验算归一化。 **第 2 步：对第一寄存器做 QFT（$n$ 个独立的模 $q$ QFT）。**用 $|a\rangle\mapsto q^{-n/2}\sum_u\omega_q^{-\langle a,u\rangle}|u\rangle$，得到 $|u\rangle|k\rangle$ 处的振幅 $$ \frac{\eta(k)}{q^{(2n+1)/2}}\sum_{a\in\mathbb Z_q^n}\omega_q^{\langle a,\,ks-u\rangle} =\frac{\eta(k)}{q^{(2n+1)/2}}\cdot q^n\,\delta_{u,\,ks\bmod q}, $$ 等号用了正交关系 $\sum_{a\in\mathbb Z_q^n}\omega_q^{\langle a,v\rangle}=q^n\delta_{v,0}$（等比数列求和：每位独立求和给出 $q$ 倍 delta）。于是两个 QFT 之后的末态有紧凑的封闭形式： $$ \boxed{\;\mathrm{QFT}^{\otimes2}|\psi_s\rangle =\frac{1}{\sqrt q}\sum_{k\in\mathbb Z_q}\eta(k)\,|k\cdot s\bmod q\rangle\,|k\rangle.\;} $$ 归一化验算：$\frac1q\sum_k|\eta(k)|^2=1$，正是上面的 Parseval 结果。 **无噪声情形** $D(0)=1$：$\eta(k)=1$ 对所有 $k$ 成立，末态是 $\frac1{\sqrt q}\sum_k|ks\bmod q\rangle|k\rangle$。测量第二寄存器得到均匀随机的 $k$，第一寄存器随之坍缩为 $|ks\bmod q\rangle$；只要 $k$ 在 $\mathbb Z_q$ 中可逆（例如 $q$ 为素数时任何 $k\ne0$，发生概率 $1-1/q$），读出 $ks$ 再乘 $k^{-1}$ 即得 $s$——**一份样本就够**。这与经典无噪 LWE 被线性代数秒杀完全平行。 **有噪声情形**：测量第二寄存器得到 $k$ 的概率是 $$ p(k)=\frac{|\eta(k)|^2}{q}. $$ 一切尽在这个分布里。若 $D$ 散布在宽度约 $w$ 的区间上，由 Fourier 变换的测不准性质，$\eta(k)$ 集中在 $|k|\lesssim q/w$ 的低频区。而低频恰恰是最没用的： - $k=0$ 是纯垃圾结果——第一寄存器是 $|0\rangle$，对 $s$ 没有任何信息； - 小的非零 $k$ 即使可逆，其概率权重也被 $\eta$ 的衰减压低； - 真正有用的频率（可逆且不太小的 $k$）质量被误差尾部吞噬。 与相干剖面 $\eta(k)$ 密切相关的一个量是误差的**特征函数（characteristic function）** $$ \widehat D(k)=\mathbb E_e\!\left[e^{2\pi ike/q}\right]=\sum_e D(e)\,\omega_q^{ke}, $$ 即**概率分布** $D$（而非振幅 $\sqrt D$）的 Fourier 变换。它支配的是退相干情形：如果我们先把 $e$ 测掉（或在经典样本上做事后 Fourier 分析），不同 $e$ 的贡献以概率而非振幅相加，有用频率就被 $\widehat D(k)$ 衰减。无论相干还是退相干图景，结论一致：**误差越宽，有用频率的衰减越厉害**；标准的"制备—QFT—测量"流程要么保留太多噪声（不过滤，$\eta$ 衰减），要么接受概率太小（硬性后选择，见下节）。这就是需要过滤器的原因，也是过滤器能起作用的位置。 ## 5. Quantum filter 的作用 (quantum-filter-math)= ### 5.1 过滤的数学：条件测量如何重塑分布 **定义（过滤器）**。一个过滤器是由函数 $F:\mathbb Z_q\to\mathbb C$（满足 $|F(e)|\le1$）指定的条件测量。实现方式是借用一个辅助比特做受控旋转（ch05 中 QSP/块编码的标准技巧）： $$ U_F|e\rangle|0\rangle =F(e)\,|e\rangle|0\rangle+\sqrt{1-|F(e)|^2}\,|e\rangle|1\rangle. $$ $U_F$ 是酉的（每个 $|e\rangle$ 张成的二维子空间里是一个旋转，不同 $e$ 的子空间正交）。把 $U_F$ 作用在 $|\psi_s\rangle|0\rangle$ 上，然后测量辅助比特： **接受概率**。辅助位为 $0$（接受）的概率，按 Born 规则把接受分支的振幅模方求和： $$ P=\sum_e D(e)\,|F(e)|^2. $$ 注意交叉项全部消失——不同 $e$ 对应正交的计算基矢。这就是"$P$ 是 $|F|^2$ 在 $D$ 下的期望"。 **条件态**。接受分支（未归一化）是 $\sum_{a,e}F(e)\sqrt{D(e)}\,|a\rangle|\langle a,s\rangle+e\rangle$。按 Born 规则条件化等价于把振幅统一除以 $\sqrt P$，所以过滤后的态与 $|\psi_s\rangle$ **形式完全相同**，只是误差分布换成了 $$ D'(e)=\frac{D(e)\,|F(e)|^2}{P}\;\propto\;D(e)\,|F(e)|^2. $$ 同理，第 4.3 节的整套 QFT 计算原样通过，频率剖面换成 $$ \eta_F(k)=\sum_e F(e)\sqrt{D(e)}\,\omega_q^{ke}. $$ 这三行公式（$P$、$D'$、$\eta_F$）是过滤技术的全部内容：过滤器在 QFT **之前**相干地改写振幅，于是 Fourier 域里的剖面从 $\eta$ 变成 $\eta_F$。特别地，$F$ 允许取**复数值**——可以给不同 $e$ 加相位，让它们在目标频率处相长干涉，这是任何"先测出 $e$ 再经典处理"的方案在原理上做不到的。 (filter-conditions-complexity)= ### 5.2 好 filter 的三个条件 $F$ 的 Fourier 剖面要同时满足三个互相拉扯的要求： 1. **抑制误差尾部**：$|F(e)|$ 在大 $|e|$ 处迅速衰减，使妨碍相位可区分性的误差尾巴不再污染频谱（第 3.3 节的三个参数损失来源之一）； 2. **保住总成功概率**：$P=\sum_eD(e)|F(e)|^2$ 至少是逆多项式（inverse polynomial），否则任何放大都救不回来； 3. **落进已知子程序的射程**：过滤后的态要接近某个已知可处理的分布——例如可以被已有的解码或 hidden-shift 子程序消费的形状。 条件 1 想把 $F$ 收窄，条件 2 想把 $F$ 放宽，条件 3 规定 $F$ 的形状。可解性命题本质上是在说：**对特定的误差家族与参数区域，存在同时满足三条件的 $F$**；Chen–Liu–Zhandry 的技术工作就是对这些家族具体构造出 $F$ 并验证三条。 ### 5.3 为什么必须是量子的 这是本节的要害，值得单独强调：**过滤器是本质的量子步骤，不能用任何经典预处理替代。**原因在于相干性——如果先把误差 $e$ 测出来（哪怕只是为了"看看该不该丢弃这个样本"），第二寄存器就坍缩到某个确定的 $|\langle a,s\rangle+e\rangle$，与第一寄存器 $|a\rangle$ 的相干关系随之破坏，手里剩下的只是一个经典 LWE 样本 $(a,b)$。而经典 LWE 被认为（在适当参数下）是困难的：第 4.3 节的 Fourier 奇迹依赖不同 $e$ 分量之间的干涉，测量把干涉项变成了概率混合，特征函数 $\widehat D$ 取代振幅剖面 $\eta$，再也没有过滤器可以下刀的位置。 反过来，只要保持相干，过滤器就可以在**非计算基**中利用振幅与干涉做整形——例如用 $F$ 的相位让若干个中等大小的 $e$ 在某个有用频率 $k$ 处相长叠加。这是"量子过滤"相对"经典后选择"的真正增量。 **成功概率可以用振幅放大买回来。**过滤是一个"以概率 $P$ 成功的量子子过程"，由 ch03 的振幅放大，把接受概率从 $P$ 提升到常数的代价是 $O(1/\sqrt P)$ 次重复，而非朴素重试的 $O(1/P)$。但这不是免费的：放大因子必须乘进总复杂度（见 5.5 节），所以条件 2 中"$P$ 至少逆多项式"是硬约束。 (filter-toy-example)= ### 5.4 一个可手算的过滤小例子 取 $q=8$，误差支撑在 $\{-2,-1,0,1,2\}$ 上： $$ D(0)=\tfrac14,\qquad D(\pm1)=\tfrac14,\qquad D(\pm2)=\tfrac18. $$ **第一步：算未过滤的剖面 $\eta(k)$。**由 $\eta(k)=\sum_e\sqrt{D(e)}\,\omega_8^{ke}$ 及 $\sqrt{D(0)}=1/2$、$\sqrt{D(\pm1)}=1/2$、$\sqrt{D(\pm2)}=1/(2\sqrt2)$，配对共轭项（$\omega^{ke}+\omega^{-ke}=2\cos(2\pi ke/8)$）得 $$ \eta(k)=\tfrac12+\cos\tfrac{\pi k}{4}+\tfrac{1}{\sqrt2}\cos\tfrac{\pi k}{2}. $$ 逐点计算（$\cos\frac\pi4=\frac{\sqrt2}{2}\approx0.707$，$\cos\frac\pi2=0$，$\cos\frac{3\pi}4=-\frac{\sqrt2}2$，$\cos\pi=-1$）： $$ \begin{aligned} \eta(0)&=0.5+1+0.707\approx2.207, & \eta(1)=\eta(7)&=0.5+0.707+0\approx1.207,\\ \eta(2)=\eta(6)&=0.5+0-0.707\approx-0.207, & \eta(3)=\eta(5)&=0.5-0.707+0\approx-0.207,\\ \eta(4)&=0.5-1+0.707\approx0.207. && \end{aligned} $$ 由 $p(k)=|\eta(k)|^2/8$（Parseval 验算：$\sum_k|\eta(k)|^2=8\sum_eD(e)=8$）： $$ p(0)\approx0.609,\qquad p(1)=p(7)\approx0.182,\qquad p(2)=p(4)=p(6)\approx0.0054,\qquad p(3)=p(5)\approx0.0054. $$ **$k=0$ 这个纯垃圾结果独吞了 $60.9\%$ 的概率**，而可直接读出 $s$ 的单位频率 $k\in\{1,3,5,7\}$ 合计只有约 $37.5\%$。这就是"标准测量保留太多噪声"在一个八维例子里的样子。 对照地，特征函数 $\widehat D(k)=\frac14+\frac12\cos\frac{\pi k}4+\frac14\cos\frac{\pi k}2$ 给出 $\widehat D(1)\approx0.604$、$\widehat D(2)=0$——概率图景下衰减同样剧烈，第 4.4 节的论断在此坐实。 **第二步：加硬截断过滤器。**取 $F(e)=1$（$|e|\le1$），$F(\pm2)=0$。则 - 接受概率 $P=\sum_eD(e)|F(e)|^2=\frac14+\frac14+\frac14=\frac34$； - 新剖面 $\eta_F(k)=\frac12+\cos\frac{\pi k}4$（尾部两项被滤掉）。 逐点：$\eta_F(0)=1.5$，$\eta_F(1)=\eta_F(7)\approx1.207$，$\eta_F(2)=\eta_F(6)=0.5$，$\eta_F(3)=\eta_F(5)\approx-0.207$，$\eta_F(4)=-0.5$。条件概率为 $p_F(k)=|\eta_F(k)|^2/(8P)=|\eta_F(k)|^2/6$： $$ p_F(0)=0.375,\qquad p_F(1)=p_F(7)\approx0.243,\qquad p_F(2)=p_F(6)\approx0.0417,\qquad p_F(3)=p_F(5)\approx0.0071,\qquad p_F(4)\approx0.0417. $$ （验算：$0.375+2(0.243)+2(0.0417)+2(0.0071)+0.0417\approx1$。） **第三步：读结果。**过滤把垃圾结果 $k=0$ 的条件概率从 $60.9\%$ 压到 $37.5\%$，单位频率的条件质量从 $37.5\%$ 升到约 $50\%$，代价是接受概率 $P=3/4$——用振幅放大的话只相当于 $O(\sqrt{4/3})\approx1.15$ 倍的常数开销。 这个玩具例子只展示了**机制**：在误差宽度仅为 $2$、模数仅为 $8$ 时，过滤的收益是有限的。真正的分水岭出现在渐近区域：当误差宽度随 $n$ 增长时，未过滤的 $\eta$ 会把几乎全部质量堆在垃圾频率上（有用质量指数小），而精心设计的 $F$（一般不是硬截断，而是带相位的光滑剖面）能在有用频率上保住逆多项式质量。这一渐近论断是**模型与误差家族依赖的**——它正是第 6 节三个变体各自要验证的内容，而不是一条普遍定理。 ### 5.5 复杂度账：每个因子从哪来 把整条流水线的时间复杂度写成四项乘积，逐项交代来源： $$ T\;=\;\underbrace{N_{\rm samples}}_{\text{解码所需样本数}} \times\underbrace{C_{\rm prep}}_{\text{制备一份样本态}} \times\underbrace{C_{\rm filter}}_{\text{实现 }F} \times\underbrace{C_{\rm amp}}_{\text{振幅放大}}. $$ - $N_{\rm samples}$：后端的 Fourier 解码/hidden-shift 子程序每消费一份过滤后的样本，获得逆多项式量的信息，故需要 $\mathrm{poly}(n)$ 份（依赖条件 3：过滤后的分布确实落在子程序射程内）。 - $C_{\rm prep}$：制备周期 Gaussian/陪集态，涉及 Gaussian 振幅的相干加载与模运算，$\mathrm{poly}(n,\log q,\log(1/\varepsilon))$。 - $C_{\rm filter}$：对多项式时间可计算的 $F$，用受控旋转/块编码实现，$\mathrm{poly}(\log q)$ 量级。 - $C_{\rm amp}=O(1/\sqrt P)$：$P$ 是接受概率（条件 2 保证它逆多项式）。朴素后选择这里是 $O(1/P)$——振幅放大贡献了二次改进，这是 ch03 机器直接进入格算法的地方。 **参数平衡**。设过滤器有一个"宽度"旋钮 $r$（例如硬截断半径，或光滑剖面的衰减尺度）。两个条件沿相反方向拉它： - 条件 1（尾部抑制）：残余尾部质量 $L(r)=\sum_{|e|>r}D(e)|F(e)|^2$ 必须小于解码器能容忍的阈值 $\varepsilon_{\rm dec}$——**$r$ 越小越好**； - 条件 2（成功概率）：$P(r)=\sum_eD(e)|F(e)|^2\ge1/\mathrm{poly}(n)$——**$r$ 越大越好**（滤得越狠，丢的概率越多）。 求解过程是标准的"夹逼"：由条件 1 解出上界 $r\le r_{\max}$（取使 $L(r)\le\varepsilon_{\rm dec}$ 成立的最大 $r$），由条件 2 解出下界 $r\ge r_{\min}$，可行域是区间 $[r_{\min},r_{\max}]$。**可解性 $\Longleftrightarrow$ 这个区间非空。**对密码学标准参数（误差宽度与模数同阶地"贴得很紧"），可以验证区间是空的；而 Chen–Liu–Zhandry 指出，对第 6 节的特定误差家族（bounded-uniform、Laplace 等）与多项式模数，$r_{\min} 提示：对照阿贝尔 HSP 中 QFT 直接读出周期与二面体陪集态只能提供相位片段；三个来源见第 3.3 节。 **练习 2【格与对偶格】**（→ [第 2 节](#lattice-dual-basics)） 1. 基础：证明 $\mathbb Z^n$ 的对偶格是它自身；再对 $B=\begin{pmatrix}4&0\\0&6\end{pmatrix}$ 写出 $\mathcal L^*$ 的一组基与 $\det\mathcal L^*$，并逐点验证 $y=(1/4,0)$ 满足对偶条件。 2. 进阶：证明 $\det\mathcal L^*=1/\det\mathcal L$，以及 BDD 在半径 $r<\lambda_1/2$ 时解唯一。 > 提示：前者对基矩阵 $B^{-T}$ 取行列式；后者用三角不等式把两个候选解之差与 $\lambda_1$ 比较。 **练习 3【Poisson 求和与对偶结构】**（→ [3.1 节](#poisson-sum-duality)） 1. 基础：写出周期化 Gaussian 的 Fourier 变换的三条结构性质（支撑集、宽度反转、平移变相位），并各指出它来自四步推导中的哪一步。 2. 进阶：（对偶与 Poisson 峰）对一维格 $\mathcal L=a\mathbb Z$：(a) 验证对偶格是 $\frac1a\mathbb Z$；(b) 从第 3.1 节的四步推导出发，写出其周期化 Gaussian 的 Fourier 展开，明确指出每个峰的位置、权重与（当 $t\ne0$ 时）相位；(c) 取 $a=2$、$s=1/2$、$t=1/2$，算出前四个峰的权重与相位。 > 提示：峰位于 $k/a$、权重 $e^{-\pi s^2k^2/a^2}$、相位 $e^{-2\pi ikt/a}$；(c) 的数值可与第 3.2 节直接核对。 **练习 4【LWE-like 量子态与双 QFT】**（→ [第 4 节](#lwe-state-double-qft)） 1. 基础：写出 LWE 样本与 $|\psi_s\rangle$ 的定义并验证归一化；在无噪声 $D(0)=1$ 时，分别对素数 $q$ 与 $q=8$ 计算测量后可直接解出 $s$ 的概率（注意哪些 $k$ 在 $\mathbb Z_q$ 中可逆）。 2. 计算：取 $q=8$、$D(0)=D(1)=\tfrac12$（误差只取 $0$ 或 $1$），计算 $\eta(k)$ 的模长与 $p(k)$，并用 Parseval 恒等式验算 $\sum_k p(k)=1$。 3. 进阶：（经典样本 vs 量子样本）比较一个经典 LWE 样本 $(a,b)$ 与一份 LWE-like 量子态 $|\psi_s\rangle$ 的信息含量：(a) 解释为什么无噪声时两者都"一条样本解出 $s$"；(b) 解释为什么有噪声时量子态仍有 Fourier 结构可挖，而先测掉 $e$ 会永久破坏它（用 $\eta$ 与 $\widehat D$ 的区别作答）。 > 提示：$1+e^{i\theta}=2\cos(\theta/2)\,e^{i\theta/2}$；(b) 问想想"先相加再取模方"与"先取模方再相加"的差别。 **练习 5【量子过滤器的数学】**（→ [5.1 节](#quantum-filter-math)） 1. 基础：写出 $U_F|e\rangle|0\rangle$ 的作用与 $P$、$D'(e)$、$\eta_F(k)$ 三条公式，并说明过滤后的态为何与 $|\psi_s\rangle$ 形式完全相同。 2. 进阶：（条件分布）从过滤酉 $U_F$ 与 Born 规则出发，完整推导接受概率 $P=\sum_eD(e)|F(e)|^2$ 与条件分布 $D'(e)\propto D(e)|F(e)|^2$，并说明交叉项为什么消失。 3. 思考：为什么"先测出 $e$、再按经典规则丢弃部分样本"无法实现同样的整形，而复值 $F$ 还能安排相长干涉？ > 提示：不同 $e$ 对应正交的计算基矢；测量把干涉项变成概率混合。 **练习 6【好过滤器的条件与复杂度】**（→ [5.2 节](#filter-conditions-complexity)） 1. 基础：列出过滤器要同时满足的三个条件，指出哪两个把过滤器宽度 $r$ 往相反方向拉；写出四因子复杂度乘积并说明振幅放大为什么把重复次数从 $O(1/P)$ 降到 $O(1/\sqrt P)$。 2. 进阶：（可行区间，较难）按第 5.5 节建立不等式链：设误差 $D$ 在 $\{|e|>r\}$ 上的质量为 $L_0(r)$，过滤器取硬截断半径 $r$。写出条件 1（$L_0(r)\le\varepsilon_{\rm dec}$）与条件 2（$P(r)\ge1/\mathrm{poly}(n)$）对 $r$ 的约束方向，证明可行 $r$ 构成一个区间，并举例说明当误差宽度与 $q$ 同阶增长时该区间为何会变空。（可用定性论证，不需精确常数。） > 提示：两个条件分别给出 $r\le r_{\max}$ 与 $r\ge r_{\min}$；比较误差宽度与 $q$ 的增长速度对 $L_0(r)$、$P(r)$ 的影响。 **练习 7【可手算的过滤例子】**（→ [5.4 节](#filter-toy-example)） 1. 基础：由 $D(0)=\tfrac14$、$D(\pm1)=\tfrac14$、$D(\pm2)=\tfrac18$ 推出 $\eta(k)=\tfrac12+\cos\tfrac{\pi k}{4}+\tfrac{1}{\sqrt2}\cos\tfrac{\pi k}{2}$，并计算 $\eta(2)$ 与 $p(2)$，与正文数值核对。 2. 进阶：（玩具例子的延伸）在第 5.4 节的 $q=8$ 玩具模型中：(a) 验证 $p(0)\approx0.609$ 与过滤后 $p_F(0)=0.375$ 的全部中间步骤；(b) 改用软过滤器 $F(\pm2)=t$（$0\le t\le1$，其余 $F=1$），写出 $P(t)$ 与 $p_{F,t}(0)$ 的表达式，并求使垃圾概率 $p_{F,t}(0)$ 最小化的 $t$；(c) 对该最优 $t$，比较朴素后选择 $O(1/P)$ 与振幅放大 $O(1/\sqrt P)$ 的期望开销。 > 提示：先写出 $P(t)=\tfrac34+\tfrac{t^2}{4}$，再对 $p_{F,t}(0)$ 关于 $t$ 求导看符号。 **练习 8【可解变体与密码学边界】**（→ [第 6 节](#solvable-variants-boundary)） 1. 基础：列出三类可解变体及各自的关键参数条件，并指出"量子样本下的 LWE"依赖的攻击模型假设是什么、现实方案为何通常不满足它。 2. 进阶：（松界 SIS）解释为什么 $\|x\|_\infty\le q/2-c$（$c$ 为常数）的 SIS 界远弱于密码学的"小范数"要求：分别数一下 $\mathbb Z_q$ 中被范数约束排除的取值个数，并说明这一差别如何使 worst-case 困难性归约失效。 > 提示：松界只排除 $\mathbb Z_q$ 中贴着 $\pm q/2$ 的约 $2c$ 个值；标准 SIS 只允许 $\beta=\mathrm{poly}(n)\ll q$ 的小盒子。 ## 参考文献 - Zoo 编号 498：Chen、Liu 与 Zhandry, [Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering](https://arxiv.org/abs/2108.11015). - Zoo 编号 78：Regev, [Quantum Computation and Lattice Problems](https://arxiv.org/abs/cs/0304005). - Zoo 编号 5：Aharonov--Ta-Shma 的 adiabatic state generation 与 lattice-state 技术.