格问题的量子过滤：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 算法的共同结构对照。

本课知识点

  1. 格上的量子困局——能解释为什么 Shor 的阿贝尔 HSP 思路不能直接攻克 SVP/CVP，并列出 Fourier 对偶归约中累积参数损失的三个来源。

  2. 格与对偶格——能写出格、对偶格与 SVP/CVP/BDD 的定义，推导 \(\mathcal L^*=B^{-T}\mathbb Z^n\) 并计算 \(\det\mathcal L^*=1/\det\mathcal L\)。

  3. Poisson 求和与对偶结构——能按四步推导周期化 Gaussian 的 Poisson 求和公式，说明支撑集、宽度反转与平移变相位，并在一维格上手算各峰的位置、权重与相位。

  4. LWE-like 量子态与双 QFT——能写出 LWE 样本与 LWE-like 量子态并验证归一化，完成双寄存器 QFT 的计算导出误差剖面 \(\eta(k)\)，并比较相干剖面 \(\eta\) 与特征函数 \(\widehat D\)。

  5. 量子过滤器的数学——能从受控旋转 \(U_F\) 出发推导 \(P\)、\(D'\) 与 \(\eta_F(k)\) 三条公式，并解释为什么过滤是本质量子的步骤、复值 \(F\) 多出哪些自由度。

  6. 好过滤器的条件与复杂度——能列出好过滤器的三个条件并解释其相互拉扯，写出四因子复杂度乘积与振幅放大改进，用夹逼论证可行区间 \([r_{\min},r_{\max}]\) 何时非空。

  7. 可手算的过滤例子——能复算 \(q=8\) 例子中过滤前后的 \(\eta(k)\)、\(p(k)\) 与 \(p_F(k)\)，解读垃圾频率质量的转移，并说明玩具例与渐近区域的差别。

  8. 可解变体与密码学边界——能列出三类可解变体及其参数条件，并逐条解释为什么它们不落入主流后量子方案的困难参数区域。

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 的观察是：链条中最薄弱环节是误差分布的形状，而误差分布在量子世界里不是被动给定的——在测量之前，可以用一个相干的过滤器去整形它。这就是本教程的主题。

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 得到对偶格信息"这一全部现象，都是这个恒等式的离散化身。

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 节说的"差的一步"，在技术上就是这些损失的累积。过滤技巧要修理的正是这个环节。

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 的作用

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\) 再经典处理"的方案在原理上做不到的。

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\) 至少逆多项式"是硬约束。

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{split} \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} \end{split}\]

由 \(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}<r_{\max}\) 且 slack 是多项式级的——这个"区间非空"的结论依赖于具体误差形状，是一般性结论中必须保留的模型依赖条款。

6. 三类可解变体

过滤器不是万能钥匙：它只在误差分布、模数、矩阵形状配合的参数区域里奏效。论文给出三处这样的区域。

6.1 Wide SIS\(_\infty\)

问题。给定非常宽的矩阵

\[ A\in\mathbb Z_q^{n\times m} \]

（\(m\) 远大于密码学常用的宽度），找非零 \(x\in\mathbb Z^m\) 满足

\[ Ax=0\pmod q,\qquad \|x\|_\infty\le q/2-c, \]

其中 \(c\) 是常数 margin。

先理解这个界有多"松"：标准密码学 SIS 要求 \(\|x\|\le\beta\) 且 \(\beta=\mathrm{poly}(n)\ll q\)——解向量只允许占据以原点为中心、边长相对 \(q\) 可忽略的小盒子，这正是困难性的来源。而这里的上界 \(q/2-c\) 距离模数的一半只差一个常数：\(\mathbb Z_q\) 的 \(q\) 个取值中，只有靠近边界 \(\pm q/2\) 的约 \(2c\) 个值被禁用，范数约束几乎不咬人。换句话说，困难的不是"短"，而只剩"\(Ax=0\) 且非零"本身。

过滤/QFT 在这条参数轴上的作用（骨架，细节超出本教程范围）：在有界盒子上制备由过滤器整形的振幅叠加 \(\sum_x F(x)|x\rangle|Ax\bmod q\rangle\)，条件于第二寄存器测得 \(0\) 即得到核中向量的相干叠加；QFT 结构保证整形后的态在"有界且非零"的向量上集中可测质量。宽度 \(m\) 的角色是提供熵：核的维数约为 \(m-n\)，\(m\) 越大，满足关系式的候选越多，过滤后保留下来的成功质量越足——第 5.5 节条件 2 在这里正是靠宽 \(m\) 来满足的。

6.2 量子样本下的 LWE

设定：模数 \(q=\mathrm{poly}(n)\) 为多项式大小；误差分布取 bounded-uniform（有界区间上的均匀分布）或 Laplace 等特定形状；输入是 \(\mathrm{poly}(n)\) 份第 4.2 节的 LWE-like 量子态 \(|\psi_s\rangle\)。

算法轮廓：对每份样本施加过滤器 \(F\)，把误差振幅整形成可 Fourier 解码的剖面（第 5 节的三个条件在这些误差家族下可同时满足——这正是 5.5 节"区间非空"结论成立的地方）；随后走第 4.3 节的双 QFT 流水线，用解码子程序从有用频率中逐位恢复秘密 \(s\)。

必须保留的模型依赖条款：输入是相干的量子样本态，不是经典 LWE 样本对。一个真实的密码方案分发的是已经测量过的经典对 \((a,b)\)，攻击者无从获得 \(|\psi_s\rangle\)——除非方案的某个实现环节（例如用量子设备生成密钥/样本）真的把这种相干态交了出去。算法成立的前提是"对手能拿到量子样本"，这是一个关于攻击模型的假设，而非对标准 LWE 的破解。

6.3 EDCP（外推二面体陪集问题）

背景：Regev 的二面体陪集态（第 1.3 节）形如 \(|j\rangle|x+js\bmod N\rangle\) 的叠加，其中 \(j\) 取自某个标准窗口（例如 \(\{0,1\}^l\)）。对第二寄存器做 QFT 后，频率 \(y\) 处的振幅携带因子

\[ \sum_j \rho(j)\,\omega_N^{yjs}, \]

即 \(j\)-剖面 \(\rho\) 在"频率" \(ys/N\) 处的 Fourier 变换。若 \(j\)-窗口宽度为 \(W\)，这个和式能把相位 \(ys\bmod N\) 分辨到约 \(N/W\) 的精度——窗口越宽，相位分辨率越高，而相位精度正是第 3.3 节列出的参数损失来源之一。

**外推（extrapolated）**的含义：把 \(j\) 的范围扩展到标准窗口之外，带上权重剖面 \(\rho(j)\)，得到形如

\[ \sum_j\rho(j)\,|j\rangle\,|x+js\rangle \]

的态。更宽的 \(j\)-支撑给出更精细的相位分辨，但代价是权重 \(\rho\) 的尾部又带来新的"误差分布"问题——轮到过滤器上场：在 \(j\) 寄存器上做过滤，调整 \(j\)-window 与相位分辨率的权衡，使第 5.2 节的三条件重新同时成立。由此，已知多项式时间可解的 DCP 参数区域被稍微向外扩展；再经 Regev 风格的归约，EDCP 求解器与 6.2 节的 LWE 求解器连成一条链（格问题 \(\to\) 陪集态 \(\to\) LWE 型样本），三类变体共享同一套过滤引擎。

7. 为什么不破坏主流后量子方案

论文明确指出：可解参数不在已知 worst-case 困难的标准参数区域内。逐条展开这个保留条款：

  • SIS 的界太松、矩阵太宽。界 \(q/2-c\) 贴着模数的一半，与密码学 SIS 的"小范数"（\(\beta=\mathrm{poly}(n)\ll q\)）相差悬殊；矩阵宽度 \(m\) 也远超实际方案。worst-case/average-case 归约不覆盖这种极端宽度与松界（见练习 8）。

  • LWE 的输入是相干量子态。算法消费的是 \(|\psi_s\rangle\) 这样的叠加态；现实中的公开样本是已测量的经典对 \((a,b)\)，相干性已经丧失，过滤器无用武之地（第 5.3 节）。攻击模型"对手持有量子样本"需要由具体实现额外提供，标准方案不提供。

  • 误差/模数家族形状特定。多项式大小的模数、bounded-uniform/Laplace 误差是特意挑选的"过滤友好"形状；主流方案使用的误差分布与模数不在这个家族内，第 5.5 节的可行区间 \([r_{\min},r_{\max}]\) 对那些参数是空的。

  • 归约的近似因子不覆盖主流安全参数。即使把可解变体沿 Regev 归约链接回 worst-case 格问题，沿途损失的近似因子（Gaussian 尾部、离散化、相位精度，第 3.3 节）累加后仍大于主流方案所锚定的因子。

结论应当精确表述：这是首次在自然的格相关 average-case 变体上取得多项式时间量子优势，而不是"格上的 Shor 算法"。任何对具体密码方案的影响，都必须重新证明两件事：目标方案（的某个实现）能提供算法所需的量子样本，且其参数能映射进可解区域。在此之前，主流后量子方案的安全性不受此结果影响。

8. 与 decoding/DQI 的共同结构

值得把过滤算法与同章的 Decoded Quantum Interferometry 放在一起看：两者都在 Fourier 对偶域里做同一件事——

\[ \text{线性约束/coset} \xrightarrow{\mathrm{QFT}} \text{dual syndrome/phase} \xrightarrow{\text{measurement/decoder}} \text{短误差或优解}. \]

对照两个算法在这条流水线上的选择：

  • 几何背景不同。格算法面对的是连续/模 Gaussian 几何与对偶格：周期化 Gaussian 的频谱支撑在 \(\mathcal L^*\) 上，宽度反转 \(s\leftrightarrow1/s\)；DQI 工作在有限域上，频率标签是码的 syndrome 的稀疏组合。

  • "过滤器"的实现不同。格过滤是在误差寄存器上做条件测量（POVM/基旋转），重塑的是连续误差的振幅剖面 \(\eta(k)\)；DQI 在频率域实现多项式滤波，靠可逆的经典 syndrome 解码器清除组合标签。

  • 共同的设计原则：在测量/解码之前保持相干。两个算法里，任何提前的测量都会把干涉图样退化成概率混合（第 5.3 节），对偶域里的结构也随之消失。可以说，"相干性必须活到解码器手里"是这一类 Fourier 对偶算法共同的生存条件。

9. 本课小结

  • QFT 把格的周期性变成对偶格上的频率：Poisson 求和给出支撑集在 \(\mathcal L^*\)、宽度反转 \(s\leftrightarrow1/s\)、平移 \(t\) 变成对偶相位 \(e^{-2\pi i\langle w,t\rangle}\)。

  • LWE-like 量子态经双寄存器 QFT 变为 \(\frac1{\sqrt q}\sum_k\eta(k)|ks\bmod q\rangle|k\rangle\)；误差越宽，振幅剖面 \(\eta\)（非相干情形下是特征函数 \(\widehat D\)）对有用频率的衰减越厉害。

  • 量子过滤器通过条件测量把误差分布重塑为 \(D'(e)\propto D(e)|F(e)|^2\)，相干地改写 Fourier 剖面；好过滤器要同时满足尾部抑制、逆多项式成功概率、落入已知子程序射程三个条件，成功概率可用振幅放大以 \(O(1/\sqrt P)\) 买回。

  • 多项式时间算法只覆盖三类变体：wide SIS\(_\infty\)（界 \(q/2-c\)、超宽矩阵）、量子样本下的 LWE（多项式模数、特定误差家族）、以及特定参数的 EDCP。

  • 标准 SVP/CVP 与主流 LWE/SIS 密码参数没有因此被破解：可解区域不在 worst-case 困难的标准参数内，且攻击模型要求对手持有相干量子样本。

练习题

练习 1【格上的量子困局】（→ 第 1 节）

  1. 基础：说明 Ajtai 与 Regev 的两个归约分别连接了哪两类问题（worst-case 与 average-case），并写出经典算法在"近似因子—运行时间"权衡曲线上的两个标志性结论（多项式时间能达到的近似因子量级；精确/近精确求解的时间量级）。

  2. 进阶：解释格问题的隐藏周期结构为什么落在二面体群而非阿贝尔群上，以及为什么二十年来 Fourier 对偶归约始终"差一步"——参数损失从哪三个来源累积？

提示：对照阿贝尔 HSP 中 QFT 直接读出周期与二面体陪集态只能提供相位片段；三个来源见第 3.3 节。

练习 2【格与对偶格】（→ 第 2 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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\) 的小盒子。

参考文献