格问题的量子过滤

格上的最短向量问题（SVP）与最近向量问题（CVP）是后量子密码的安全基石：目前主流的标准化方案都把安全性归约到这类问题的困难性上。对一般的 SVP/CVP，我们不知道任何多项式时间的量子算法——这与整数分解、离散对数被 Shor 算法一举攻克形成了鲜明对比。因此，一个自然的问题是：量子计算对格问题究竟”差在哪一步”，而这差距能否被某种新的量子技巧补上？

Chen、Liu 与 Zhandry（Zoo 编号 498）给出的答案出人意料地具体：差距集中在 Fourier 对偶归约中的误差分布上。他们的办法是在 Regev 风格的 Fourier duality 框架中插入一个非平凡的量子 measurement filter（测量过滤器），在测量之前相干地重塑误差振幅，把原本”差一点够用”的归约推进可解的参数区域。由此得到的是针对特定 average-case 变体——很宽矩阵的 SIS${}_{\infty }$、带量子样本的 LWE、外推二面体陪集问题（EDCP）——的多项式时间量子算法。

本词条假设读者已掌握前面的词条的内容：量子力学与量子计算基础（）、QFT 与相位估计（）、Grover 与振幅放大（）、以及 QSP/QSVT 中”用辅助比特实现非酉变换”的思想（）。我们会用到这些工具，但不再重新推导它们。

阅读路线图：第 1 节讲历史与动机；第 2 节固定格与对偶格的记号；第 3 节推导 Poisson 求和公式——这是”QFT 交换 primal 与 dual”的全部数学来源；第 4 节定义 LWE 与 LWE-like 量子态，并把双寄存器 QFT 完整算一遍；第 5 节是本词条的核心，讲量子过滤器如何重塑误差分布，并附一个可手算的数值例子；第 6 节介绍三类可解变体；第 7 节解释为什么这一切没有攻破主流后量子方案；第 8 节把它与同章 DQI 算法的共同结构对照。

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 算法（）：整数分解与离散对数都能归约到阿贝尔群上的隐藏子群问题（HSP），而阿贝尔群的 Fourier 变换（QFT）能把隐藏的周期性一次性读出。格问题也有一只”隐藏的周期结构”——格本身就是一个周期点阵——但它对应的群论对象不是阿贝尔群，而是**二面体群（dihedral group）**这样的非阿贝尔群。

2002 年 Regev 形式化了二面体陪集问题（DCP）：给定若干个形如”叠加在 $j$ 上、同时叠加在 $x+js\mathrm{mod}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$ 是行列式为 $\pm 1$ 的整数矩阵（unimodular），则 $B$ 与 $BU$ 生成同一个格，因为 $U{\mathbb{Z}}^n={\mathbb{Z}}^n$。格的基本平行体体积 $\det \mathcal{L}=|\det B|$ 因此与基的选取无关，是格本身的不变量。

定义（对偶格）。格 $\mathcal{L}$ 的**对偶格（dual lattice）**是与所有格点内积都为整数的向量集合：

$${\mathcal{L}}^{\ast }=\{y\in {\mathbb{R}}^n:⟨y,x⟩\in \mathbb{Z},\forall x\in \mathcal{L}\}.$$

我们来推出它的显式形式。条件”$⟨y,x⟩\in \mathbb{Z}$ 对所有 $x\in \mathcal{L}$ 成立”只需对基向量检验（任意格点是基向量的整系数组合，内积是线性的）：$⟨y,b_i⟩\in \mathbb{Z}$ 对所有 $i$ 成立，即 $B^{T}y\in {\mathbb{Z}}^n$，即 $y\in B^{-T}{\mathbb{Z}}^n$。因此

$${\mathcal{L}}^{\ast }=B^{-T}{\mathbb{Z}}^n,$$

也就是说对偶格以 $B^{-T}$ 为一组基。取行列式得 $\det {\mathcal{L}}^{\ast }=1/\det \mathcal{L}$：原格越密（基本体积越小），对偶格越疏，这个反转关系是后面一切”宽度反转”现象的根源。

小例子。取 $B=\left(\begin{array}{cc}2& 0\\ 0& 3\end{array}\right)$，则 $\mathcal{L}$ 是平面上横坐标为偶数、纵坐标为 3 的倍数的点阵，$\det \mathcal{L}=6$。对偶基 $B^{-T}=\left(\begin{array}{cc}1/2& 0\\ 0& 1/3\end{array}\right)$，即 ${\mathcal{L}}^{\ast }$ 由步长 $1/2$ 与 $1/3$ 生成，$\det {\mathcal{L}}^{\ast }=1/6$。逐点验证：$y=(1/2,0)$ 与任意格点 $x=(2a,3b)$ 的内积是 $a\in \mathbb{Z}$，确实满足对偶条件。

基本问题。记 ${\lambda }_1(\mathcal{L})={\min }_{v\in \mathcal{L}\setminus \{0\}}\Vert v\Vert$ 为最短非零向量长度。

• SVP（最短向量问题）：给 $B$，找 $v\in \mathcal{L}\setminus \{0\}$ 使 $\Vert v\Vert ={\lambda }_1$。近似版本允许 $\Vert v\Vert \le \gamma (n){\lambda }_1$。
• CVP（最近向量问题）：给 $B$ 与目标点 $t\in {\mathbb{R}}^n$，找 $v\in \mathcal{L}$ 使 $\Vert v-t\Vert$ 最小。
• BDD（有界距离解码）：CVP 的 promise 版本——事先保证 $t$ 到格的距离不超过某个半径 $r$。当 $r<{\lambda }_1/2$ 时解唯一：若两个格点 $v_1\ne v_2$ 都满足 $\Vert v_i-t\Vert \le r$，则由三角不等式 $\Vert v_1-v_2\Vert \le 2r<{\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 \Vert x{\Vert }^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 \Vert x-v-t{\Vert }^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^{\prime }\in \mathcal{L}}f(x-v^{\prime }-t)=\Psi (x),$$

其中第二个等号用了换元 $v^{\prime }=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}}^{\ast }}{c}_w{e}^{2\pi i⟨w,x⟩}.$$

为什么频率必须落在 ${\mathcal{L}}^{\ast }$？因为每个 Fourier 基元 $e^{2\pi i⟨w,x⟩}$ 本身必须满足 $\mathcal{L}$-周期性：$e^{2\pi i⟨w,x+v⟩}=e^{2\pi i⟨w,x⟩}$ 对所有 $v\in \mathcal{L}$ 成立，当且仅当 $⟨w,v⟩\in \mathbb{Z}$，当且仅当 $w\in {\mathcal{L}}^{\ast }$（这正是对偶格的定义）。所以”周期在 $\mathcal{L}$ 上”与”频率在 ${\mathcal{L}}^{\ast }$ 上”是同一件事的两面。

**第 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⟨w,x⟩}dx=\frac{1}{\det \mathcal{L}}{\int }_{\mathcal{F}}\sum _{v\in \mathcal{L}}f(x-v-t)e^{-2\pi i⟨w,x⟩}dx.$$

因为 $w\in {\mathcal{L}}^{\ast }$ 且 $v\in \mathcal{L}$，有 $e^{-2\pi i⟨w,v⟩}=1$，于是可把相位改写为 $e^{-2\pi i⟨w,x-v⟩}$；再把求和与积分交换（绝对收敛保证合法），并对每一项换元 $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⟨w,x⟩}dx=\frac{1}{\det \mathcal{L}}{e}^{-2\pi i⟨w,t⟩}\hat{f}(w),$$

第二个等号对积分做平移 $x\mapsto x+t$，把 $t$ 从 $f$ 的自变量搬到相位因子里。

**第 4 步：代入 Gaussian 的 Fourier 变换。**在约定 $\hat{f}(y)=\int f(x)e^{-2\pi i⟨x,y⟩}dx$ 下，$f(x)=e^{-\pi \Vert x{\Vert }^2/s^2}$ 的变换是 $\hat{f}(y)=s^n{e}^{-\pi s^2\Vert y{\Vert }^2}$——宽度从 $s$ 反转为 $1/s$（自变量越宽，频谱越窄，这是 Fourier 变换的测不准性质）。合并得

$$\hat{\Psi }(y)\propto \sum _{w\in {\mathcal{L}}^{\ast }}{e}^{-\pi s^2\Vert w{\Vert }^2}{e}^{-2\pi i⟨w,t⟩}\delta (y-w).$$

把四步串起来读这个公式：

• 支撑集：primal 周期函数的频率全部落在对偶格 ${\mathcal{L}}^{\ast }$ 上（第 2 步）；
• 宽度反转：primal 中 Gaussian 宽度为 $s$，dual 中包络 $e^{-\pi s^2\Vert w{\Vert }^2}$ 作为频率 $w$ 的函数宽度为 $\sim 1/s$（第 4 步）——原格的”近处结构”映射为对偶格的”远处结构”；
• 平移变相位：primal 中的平移 $t$（对应 CVP/BDD 的目标点！）在对偶侧变成每个频率 $w$ 携带的相位 $e^{-2\pi i⟨w,t⟩}$（第 3 步）。单次测量会丢掉相位（概率是振幅模方），但相位就在振幅里，可以被相干的后续电路利用——这正是量子算法比”直接采样对偶格点”多出来的东西。

3.2 一个可手算的一维例子

取一维格 $\mathcal{L}=a\mathbb{Z}$（$a>0$），$t=0$。对偶格是 ${\mathcal{L}}^{\ast }=\frac{1}{a}\mathbb{Z}$（验证：$⟨k/a,am⟩=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^2{k}^2/a^2}{e}^{2\pi ikx/a}.$$

代入数值 $a=2$、$s=1/2$：频率峰位于 $y=k/2\in \frac{1}{2}\mathbb{Z}$，权重为 $e^{-\pi k^2/16}$。逐个算：

$$k=0:1;k=\pm 1:e^{-\pi /16}\approx 0.822;k=\pm 2:e^{-\pi /4}\approx 0.456;k=\pm 3:e^{-9\pi /16}\approx \mathrm{0.170.}$$

现在把 primal 宽度加倍到 $s=1$（其他不变）：权重变成 $e^{-\pi k^2/4}$，即

$$k=0:1;k=\pm 1:e^{-\pi /4}\approx 0.456;k=\pm 2:e^{-\pi }\approx \mathrm{0.043.}$$

primal 的小山变宽一倍，dual 的包络就收窄一倍——宽度反转直接可见。若再把 $t$ 从 $0$ 改为 $t=1/2$，所有权重模不变，但第 $k$ 个峰乘上相位 $e^{-2\pi ik\cdot (1/2)/2}=e^{-\pi ik/2}$，依次是 $1,-i,-1,i,\dots$——平移信息完整地编码在相位序列里。

3.3 从连续公式到量子寄存器

量子算法用不了连续变量，实际制备的是离散化的周期 Gaussian 态：取模数 $q$，在寄存器上制备（近似）

$$|\Psi ⟩\propto \sum _{x\in {\mathbb{Z}}_q^n}\left(\sum _{v\in \mathcal{L}}{e}^{-\pi \Vert x-v-t{\Vert }^2/s^2}\right)|x⟩,$$

然后作用 ${\mathbb{Z}}_q^n$ 上的 QFT。Poisson 公式的离散版本说：测量结果近似服从对偶格点（按 $q$ 折回）上的 Gaussian 分布，权重 $\propto e^{-\pi s^2\Vert w{\Vert }^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=⟨a,s⟩+e\mathrm{mod}q),$$

其中 $a\in {\mathbb{Z}}_q^n$ 均匀随机，$e\leftarrow D$ 是小的误差。LWE 问题是：给定多项式个独立样本，恢复 $s$。

**误差是必不可少的。**若没有误差（$e\equiv 0$），每个样本给出一个线性方程 $⟨a,s⟩=b$（在 ${\mathbb{Z}}_q$ 上），收集 $n$ 个独立方程后 Gaussian 消元立即解出 $s$。误差 $e$ 破坏了精确的线性关系：它把”解线性方程组”变成”带噪解码”，而带噪解码正是格上 BDD 问题的化身——这是 LWE 困难性的来源，也是 Regev 归约的接口。

4.2 LWE-like 量子态

现在把”经典样本”升级为”相干叠加”。LWE-like 量子态保留 error 与线性关系的叠加，抽象写成

$$|{\psi }_s⟩=\frac{1}{q^{n/2}}\sum _{a\in {\mathbb{Z}}_q^n}\sum _{e\in {\mathbb{Z}}_q}\sqrt{D(e)}|a⟩|⟨a,s⟩+e\mathrm{mod}q⟩.$$

先检查归一化：固定 $a$ 时，$e$ 跑遍 ${\mathbb{Z}}_q$ 给出 $q$ 个互不相同的基矢，内积 ${\sum }_{e}D(e)=1$；不同 $a$ 的块彼此正交；总范数平方为 $q^{-n}\cdot q^n\cdot 1=1$。

与经典样本的本质区别在相干性：振幅 $\sqrt{D(e)}$ 不是概率，不同 $e$ 的分量之间可以干涉。下面会看到，正是这个干涉让 Fourier 技术有发挥空间——也正是过滤器可以下刀的地方。

4.3 两个寄存器上做 QFT：完整计算

记 ${\omega }_q=e^{2\pi i/q}$，采用约定 ${\mathrm{QFT}}_q|b⟩=q^{-1/2}{\sum }_k{\omega }_q^{kb}|k⟩$。我们分两步，每步算到底。

**第 1 步：对第二寄存器做 QFT。**把 $b=⟨a,s⟩+e$ 代入，相位因子分裂为 ${\omega }_q^{kb}={\omega }_q^{k⟨a,s⟩}\cdot {\omega }_q^{ke}$，于是

$$|{\psi }_s⟩⟼\frac{1}{q^{(n+1)/2}}\sum _{a,k}(\underset{=:\eta (k)}{\underbrace{\sum _e\sqrt{D(e)}{\omega }_q^{ke}}}){\omega }_q^{k⟨a,s⟩}|a⟩|k⟩.$$

这里出现了本词条的关键量——误差振幅的 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⟩\mapsto q^{-n/2}{\sum }_u{\omega }_q^{-⟨a,u⟩}|u⟩$，得到 $|u⟩|k⟩$ 处的振幅

$$\frac{\eta (k)}{q^{(2n+1)/2}}\sum _{a\in {\mathbb{Z}}_q^n}{\omega }_q^{⟨a,ks-u⟩}=\frac{\eta (k)}{q^{(2n+1)/2}}\cdot q^n{\delta }_{u,ks\mathrm{mod}q},$$

等号用了正交关系 ${\sum }_{a\in {\mathbb{Z}}_q^n}{\omega }_q^{⟨a,v⟩}=q^n{\delta }_{v,0}$（等比数列求和：每位独立求和给出 $q$ 倍 delta）。于是两个 QFT 之后的末态有紧凑的封闭形式：

$$\boxed{{\mathrm{QFT}}^{\otimes 2}|{\psi }_s⟩=\frac{1}{\sqrt{q}}\sum _{k\in {\mathbb{Z}}_q}\eta (k)|k\cdot s\mathrm{mod}q⟩|k⟩.}$$

归一化验算：$\frac{1}{q}{\sum }_k|\eta (k){|}^2=1$，正是上面的 Parseval 结果。

无噪声情形 $D(0)=1$：$\eta (k)=1$ 对所有 $k$ 成立，末态是 $\frac{1}{\sqrt{q}}{\sum }_k|ks\mathrm{mod}q⟩|k⟩$。测量第二寄存器得到均匀随机的 $k$，第一寄存器随之坍缩为 $|ks\mathrm{mod}q⟩$；只要 $k$ 在 ${\mathbb{Z}}_q$ 中可逆（例如 $q$ 为素数时任何 $k\ne 0$，发生概率 $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⟩$，对 $s$ 没有任何信息；
• 小的非零 $k$ 即使可逆，其概率权重也被 $\eta$ 的衰减压低；
• 真正有用的频率（可逆且不太小的 $k$）质量被误差尾部吞噬。

与相干剖面 $\eta (k)$ 密切相关的一个量是误差的特征函数（characteristic function）

$$\hat{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$ 的贡献以概率而非振幅相加，有用频率就被 $\hat{D}(k)$ 衰减。无论相干还是退相干图景，结论一致：误差越宽，有用频率的衰减越厉害；标准的”制备—QFT—测量”流程要么保留太多噪声（不过滤，$\eta$ 衰减），要么接受概率太小（硬性后选择，见下节）。这就是需要过滤器的原因，也是过滤器能起作用的位置。

5. Quantum filter 的作用

5.1 过滤的数学：条件测量如何重塑分布

定义（过滤器）。一个过滤器是由函数 $F:{\mathbb{Z}}_q\to \mathbb{C}$（满足 $|F(e)|\le 1$）指定的条件测量。实现方式是借用一个辅助比特做受控旋转（中 QSP/块编码的标准技巧）：

$$U_F|e⟩|0⟩=F(e)|e⟩|0⟩+\sqrt{1-|F(e){|}^2}|e⟩|1⟩.$$

$U_F$ 是酉的（每个 $|e⟩$ 张成的二维子空间里是一个旋转，不同 $e$ 的子空间正交）。把 $U_F$ 作用在 $|{\psi }_s⟩|0⟩$ 上，然后测量辅助比特：

接受概率。辅助位为 $0$（接受）的概率，按 Born 规则把接受分支的振幅模方求和：

$$P=\sum _{e}D(e)|F(e){|}^2.$$

注意交叉项全部消失——不同 $e$ 对应正交的计算基矢。这就是”$P$ 是 $|F{|}^2$ 在 $D$ 下的期望”。

条件态。接受分支（未归一化）是 ${\sum }_{a,e}F(e)\sqrt{D(e)}|a⟩|⟨a,s⟩+e⟩$。按 Born 规则条件化等价于把振幅统一除以 $\sqrt{P}$，所以过滤后的态与 $|{\psi }_s⟩$ 形式完全相同，只是误差分布换成了

$$D^{\prime }(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^{\prime }$、${\eta }_F$）是过滤技术的全部内容：过滤器在 QFT 之前相干地改写振幅，于是 Fourier 域里的剖面从 $\eta$ 变成 ${\eta }_F$。特别地，$F$ 允许取复数值——可以给不同 $e$ 加相位，让它们在目标频率处相长干涉，这是任何”先测出 $e$ 再经典处理”的方案在原理上做不到的。

5.2 好 filter 的三个条件

$F$ 的 Fourier 剖面要同时满足三个互相拉扯的要求：

1. 抑制误差尾部：$|F(e)|$ 在大 $|e|$ 处迅速衰减，使妨碍相位可区分性的误差尾巴不再污染频谱（第 3.3 节的三个参数损失来源之一）；
2. 保住总成功概率：$P={\sum }_{e}D(e)|F(e){|}^2$ 至少是逆多项式（inverse polynomial），否则任何放大都救不回来；
3. 落进已知子程序的射程：过滤后的态要接近某个已知可处理的分布——例如可以被已有的解码或 hidden-shift 子程序消费的形状。

条件 1 想把 $F$ 收窄，条件 2 想把 $F$ 放宽，条件 3 规定 $F$ 的形状。可解性命题本质上是在说：对特定的误差家族与参数区域，存在同时满足三条件的 $F$；Chen–Liu–Zhandry 的技术工作就是对这些家族具体构造出 $F$ 并验证三条。

5.3 为什么必须是量子的

这是本节的要害，值得单独强调：**过滤器是本质的量子步骤，不能用任何经典预处理替代。**原因在于相干性——如果先把误差 $e$ 测出来（哪怕只是为了”看看该不该丢弃这个样本”），第二寄存器就坍缩到某个确定的 $|⟨a,s⟩+e⟩$，与第一寄存器 $|a⟩$ 的相干关系随之破坏，手里剩下的只是一个经典 LWE 样本 $(a,b)$。而经典 LWE 被认为（在适当参数下）是困难的：第 4.3 节的 Fourier 奇迹依赖不同 $e$ 分量之间的干涉，测量把干涉项变成了概率混合，特征函数 $\hat{D}$ 取代振幅剖面 $\eta$，再也没有过滤器可以下刀的位置。

反过来，只要保持相干，过滤器就可以在非计算基中利用振幅与干涉做整形——例如用 $F$ 的相位让若干个中等大小的 $e$ 在某个有用频率 $k$ 处相长叠加。这是”量子过滤”相对”经典后选择”的真正增量。

**成功概率可以用振幅放大买回来。**过滤是一个”以概率 $P$ 成功的量子子过程”，由振幅放大，把接受概率从 $P$ 提升到常数的代价是 $O(1/\sqrt{P})$ 次重复，而非朴素重试的 $O(1/P)$。但这不是免费的：放大因子必须乘进总复杂度（见 5.5 节），所以条件 2 中”$P$ 至少逆多项式”是硬约束。

5.4 一个可手算的过滤小例子

取 $q=8$，误差支撑在 $\{-2,-1,0,1,2\}$ 上：

$$D(0)=\frac{1}{4},D(\pm 1)=\frac{1}{4},D(\pm 2)=\frac{1}{8}.$$

**第一步：算未过滤的剖面 $\eta (k)$。**由 $\eta (k)={\sum }_e\sqrt{D(e)}{\omega }_8^{ke}$ 及 $\sqrt{D(0)}=1/2$、$\sqrt{D(\pm 1)}=1/2$、$\sqrt{D(\pm 2)}=1/(2\sqrt{2})$，配对共轭项（${\omega }^{ke}+{\omega }^{-ke}=2\cos (2\pi ke/8)$）得

$$\eta (k)=\frac{1}{2}+\cos \frac{\pi k}{4}+\frac{1}{\sqrt{2}}\cos \frac{\pi k}{2}.$$

逐点计算（$\cos \frac{\pi }{4}=\frac{\sqrt{2}}{2}\approx 0.707$，$\cos \frac{\pi }{2}=0$，$\cos \frac{3\pi }{4}=-\frac{\sqrt{2}}{2}$，$\cos \pi =-1$）：

$$\begin{array}{rlrl}\eta (0)& =0.5+1+0.707\approx 2.207,& \eta (1)=\eta (7)& =0.5+0.707+0\approx 1.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\approx \mathrm{0.207.}& & \end{array}$$

由 $p(k)=|\eta (k){|}^2/8$（Parseval 验算：${\sum }_k|\eta (k){|}^2=8{\sum }_{e}D(e)=8$）：

$$p(0)\approx 0.609,p(1)=p(7)\approx 0.182,p(2)=p(4)=p(6)\approx 0.0054,p(3)=p(5)\approx \mathrm{0.0054.}$$

$k=0$ 这个纯垃圾结果独吞了 $60.9\%$ 的概率，而可直接读出 $s$ 的单位频率 $k\in \{1,3,5,7\}$ 合计只有约 $37.5\%$。这就是”标准测量保留太多噪声”在一个八维例子里的样子。

对照地，特征函数 $\hat{D}(k)=\frac{1}{4}+\frac{1}{2}\cos \frac{\pi k}{4}+\frac{1}{4}\cos \frac{\pi k}{2}$ 给出 $\hat{D}(1)\approx 0.604$、$\hat{D}(2)=0$——概率图景下衰减同样剧烈，第 4.4 节的论断在此坐实。

**第二步：加硬截断过滤器。**取 $F(e)=1$（$|e|\le 1$），$F(\pm 2)=0$。则

• 接受概率 $P={\sum }_{e}D(e)|F(e){|}^2=\frac{1}{4}+\frac{1}{4}+\frac{1}{4}=\frac{3}{4}$；
• 新剖面 ${\eta }_F(k)=\frac{1}{2}+\cos \frac{\pi k}{4}$（尾部两项被滤掉）。

逐点：${\eta }_F(0)=1.5$，${\eta }_F(1)={\eta }_F(7)\approx 1.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,p_F(1)=p_F(7)\approx 0.243,p_F(2)=p_F(6)\approx 0.0417,p_F(3)=p_F(5)\approx 0.0071,p_F(4)\approx \mathrm{0.0417.}$$

（验算：$0.375+2(0.243)+2(0.0417)+2(0.0071)+0.0417\approx 1$。）

**第三步：读结果。**过滤把垃圾结果 $k=0$ 的条件概率从 $60.9\%$ 压到 $37.5\%$，单位频率的条件质量从 $37.5\%$ 升到约 $50\%$，代价是接受概率 $P=3/4$——用振幅放大的话只相当于 $O(\sqrt{4/3})\approx 1.15$ 倍的常数开销。

这个玩具例子只展示了机制：在误差宽度仅为 $2$、模数仅为 $8$ 时，过滤的收益是有限的。真正的分水岭出现在渐近区域：当误差宽度随 $n$ 增长时，未过滤的 $\eta$ 会把几乎全部质量堆在垃圾频率上（有用质量指数小），而精心设计的 $F$（一般不是硬截断，而是带相位的光滑剖面）能在有用频率上保住逆多项式质量。这一渐近论断是模型与误差家族依赖的——它正是第 6 节三个变体各自要验证的内容，而不是一条普遍定理。

5.5 复杂度账：每个因子从哪来

把整条流水线的时间复杂度写成四项乘积，逐项交代来源：

$$T=\underset{\text{解码所需样本数}}{\underbrace{N_{\mathrm{samples}}}}\times \underset{\text{制备一份样本态}}{\underbrace{C_{\mathrm{prep}}}}\times \underset{\text{实现 }F}{\underbrace{C_{\mathrm{filter}}}}\times \underset{\text{振幅放大}}{\underbrace{C_{\mathrm{amp}}}}.$$

• $N_{\mathrm{samples}}$：后端的 Fourier 解码/hidden-shift 子程序每消费一份过滤后的样本，获得逆多项式量的信息，故需要 $\mathrm{poly}(n)$ 份（依赖条件 3：过滤后的分布确实落在子程序射程内）。
• $C_{\mathrm{prep}}$：制备周期 Gaussian/陪集态，涉及 Gaussian 振幅的相干加载与模运算，$\mathrm{poly}(n,\log q,\log (1/\epsilon ))$。
• $C_{\mathrm{filter}}$：对多项式时间可计算的 $F$，用受控旋转/块编码实现，$\mathrm{poly}(\log q)$ 量级。
• $C_{\mathrm{amp}}=O(1/\sqrt{P})$：$P$ 是接受概率（条件 2 保证它逆多项式）。朴素后选择这里是 $O(1/P)$——振幅放大贡献了二次改进，这是振幅放大机器直接进入格算法的地方。

参数平衡。设过滤器有一个”宽度”旋钮 $r$（例如硬截断半径，或光滑剖面的衰减尺度）。两个条件沿相反方向拉它：

• 条件 1（尾部抑制）：残余尾部质量 $L(r)={\sum }_{|e|>r}D(e)|F(e){|}^2$ 必须小于解码器能容忍的阈值 ${\epsilon }_{\mathrm{dec}}$——$r$ 越小越好；
• 条件 2（成功概率）：$P(r)={\sum }_{e}D(e)|F(e){|}^2\ge 1/\mathrm{poly}(n)$——$r$ 越大越好（滤得越狠，丢的概率越多）。

求解过程是标准的”夹逼”：由条件 1 解出上界 $r\le r_{\max }$（取使 $L(r)\le {\epsilon }_{\mathrm{dec}}$ 成立的最大 $r$），由条件 2 解出下界 $r\ge r_{\min }$，可行域是区间 $[r_{\min },r_{\max }]$。**可解性 $⟺$ 这个区间非空。**对密码学标准参数（误差宽度与模数同阶地”贴得很紧”），可以验证区间是空的；而 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(\mathrm{mod}q),\Vert x{\Vert }_{\infty }\le q/2-c,$$

其中 $c$ 是常数 margin。

先理解这个界有多”松”：标准密码学 SIS 要求 $\Vert x\Vert \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⟩|Ax\mathrm{mod}q⟩$，条件于第二寄存器测得 $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⟩$。

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

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

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

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

$$\sum _j\rho (j){\omega }_N^{yjs},$$

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

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

$$\sum _j\rho (j)|j⟩|x+js⟩$$

的态。更宽的 $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 归约不覆盖这种极端宽度与松界（见习题 4）。
• LWE 的输入是相干量子态。算法消费的是 $|{\psi }_s⟩$ 这样的叠加态；现实中的公开样本是已测量的经典对 $(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}\stackrel{\mathrm{QFT}}{\to }\text{dual syndrome/phase}\stackrel{\text{measurement/decoder}}{\to }\text{短误差或优解}.$$

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

• 几何背景不同。格算法面对的是连续/模 Gaussian 几何与对偶格：周期化 Gaussian 的频谱支撑在 ${\mathcal{L}}^{\ast }$ 上，宽度反转 $s\leftrightarrow 1/s$；DQI 工作在有限域上，频率标签是码的 syndrome 的稀疏组合。
• “过滤器”的实现不同。格过滤是在误差寄存器上做条件测量（POVM/基旋转），重塑的是连续误差的振幅剖面 $\eta (k)$；DQI 在频率域实现多项式滤波，靠可逆的经典 syndrome 解码器清除组合标签。
• 共同的设计原则：在测量/解码之前保持相干。两个算法里，任何提前的测量都会把干涉图样退化成概率混合（第 5.3 节），对偶域里的结构也随之消失。可以说，“相干性必须活到解码器手里”是这一类 Fourier 对偶算法共同的生存条件。

9. 小结与习题

小结

• QFT 把格的周期性变成对偶格上的频率：Poisson 求和给出支撑集在 ${\mathcal{L}}^{\ast }$、宽度反转 $s\leftrightarrow 1/s$、平移 $t$ 变成对偶相位 $e^{-2\pi i⟨w,t⟩}$。
• LWE-like 量子态经双寄存器 QFT 变为 $\frac{1}{\sqrt{q}}{\sum }_k\eta (k)|ks\mathrm{mod}q⟩|k⟩$；误差越宽，振幅剖面 $\eta$（非相干情形下是特征函数 $\hat{D}$）对有用频率的衰减越厉害。
• 量子过滤器通过条件测量把误差分布重塑为 $D^{\prime }(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. （对偶与 Poisson 峰）对一维格 $\mathcal{L}=a\mathbb{Z}$：(a) 验证对偶格是 $\frac{1}{a}\mathbb{Z}$；(b) 从第 3.1 节的四步推导出发，写出其周期化 Gaussian 的 Fourier 展开，明确指出每个峰的位置、权重与（当 $t\ne 0$ 时）相位；(c) 取 $a=2$、$s=1/2$、$t=1/2$，算出前四个峰的权重与相位。
2. （条件分布）从过滤酉 $U_F$ 与 Born 规则出发，完整推导接受概率 $P={\sum }_{e}D(e)|F(e){|}^2$ 与条件分布 $D^{\prime }(e)\propto D(e)|F(e){|}^2$，并说明交叉项为什么消失。
3. （经典样本 vs 量子样本）比较一个经典 LWE 样本 $(a,b)$ 与一份 LWE-like 量子态 $|{\psi }_s⟩$ 的信息含量：(a) 解释为什么无噪声时两者都”一条样本解出 $s$”；(b) 解释为什么有噪声时量子态仍有 Fourier 结构可挖，而先测掉 $e$ 会永久破坏它（用 $\eta$ 与 $\hat{D}$ 的区别作答）。
4. （松界 SIS）解释为什么 $\Vert x{\Vert }_{\infty }\le q/2-c$（$c$ 为常数）的 SIS 界远弱于密码学的”小范数”要求：分别数一下 ${\mathbb{Z}}_q$ 中被范数约束排除的取值个数，并说明这一差别如何使 worst-case 困难性归约失效。
5. （玩具例子的延伸）在第 5.4 节的 $q=8$ 玩具模型中：(a) 验证 $p(0)\approx 0.609$ 与过滤后 $p_F(0)=0.375$ 的全部中间步骤；(b) 改用软过滤器 $F(\pm 2)=t$（$0\le t\le 1$，其余 $F=1$），写出 $P(t)$ 与 $p_{F,t}(0)$ 的表达式，并求使垃圾概率 $p_{F,t}(0)$ 最小化的 $t$；(c) 对该最优 $t$，比较朴素后选择 $O(1/P)$ 与振幅放大 $O(1/\sqrt{P})$ 的期望开销。
6. （可行区间，较难）按第 5.5 节建立不等式链：设误差 $D$ 在 $\{|e|>r\}$ 上的质量为 $L_0(r)$，过滤器取硬截断半径 $r$。写出条件 1（$L_0(r)\le {\epsilon }_{\mathrm{dec}}$）与条件 2（$P(r)\ge 1/\mathrm{poly}(n)$）对 $r$ 的约束方向，证明可行 $r$ 构成一个区间，并举例说明当误差宽度与 $q$ 同阶增长时该区间为何会变空。（可用定性论证，不需精确常数。）

参考文献

• Zoo 编号 498：Chen、Liu 与 Zhandry, Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering.
• Zoo 编号 78：Regev, Quantum Computation and Lattice Problems.
• Zoo 编号 5：Aharonov—Ta-Shma 的 adiabatic state generation 与 lattice-state 技术.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch14-optimization-numerics/lattice-filtering
• 内容遵循 CC BY-NC-SA 4.0 许可协议