# 格问题的量子过滤：QFT 对偶性、LWE-like States 与参数边界

格上的 shortest/closest vector 问题支撑后量子密码。一般 SVP/CVP 没有已知多项式量子算法；Chen--Liu--Zhandry 的突破针对特定 average-case SIS、LWE 与 extrapolated dihedral coset 参数。核心是在 Regev-style Fourier duality 中加入非平凡量子 measurement filter，改变 error distribution，使原本差一点够用的 reduction 进入可解区域。

## 1. 格、对偶与基本问题

给满秩 basis $B\in\mathbb R^{n\times n}$：

$$
\mathcal L(B)=\{Bz:z\in\mathbb Z^n\}.
$$

对偶格

$$
\mathcal L^*
=\{y:\langle y,x\rangle\in\mathbb Z,
\ \forall x\in\mathcal L\}
=B^{-T}\mathbb Z^n.
$$

SVP 找最短非零 lattice vector；CVP/BDD 给 target $t$ 找最近 lattice point（BDD 另有 target 足够接近的 promise）。这些最坏问题的近似因子决定 hardness/密码关联。

## 2. QFT 为什么交换 primal 与 dual

连续 Poisson summation：周期 Gaussian

$$
\Psi_{\mathcal L,t}(x)
=\sum_{v\in\mathcal L}
e^{-\pi\|x-v-t\|^2/s^2}
$$

的 Fourier transform 支持在 dual frequencies：

$$
\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).
$$

宽度反转 $s\leftrightarrow1/s$，平移 $t$ 变为 dual phase。离散量子寄存器上近似制备 periodic Gaussian/coset state 并做 QFT，就能在 primal nearest-vector information 与 dual short-vector/phase information 间转换。

Aharonov--Ta-Shma、Regev reductions 用这种结构把 lattice problems、dihedral coset、LWE-like samples 相互联系；参数损失来自 Gaussian tails、modulus 离散化和需要区分的 phase 精度。

## 3. LWE 与 quantum sample

Classical LWE sample：

$$
(a,b=\langle a,s\rangle+e\bmod q),
$$

$a\in\mathbb Z_q^n$，secret $s$，error $e$ 小。LWE-like quantum state 则保留 error/linear relation 的叠加，例如抽象写成

$$
|\psi_s\rangle
\propto\sum_{a,e}\sqrt{D(e)}
|a\rangle
|\langle a,s\rangle+e\bmod q\rangle.
$$

对 registers 做 QFT，理想无噪声线性关系会产生集中在 $s$ 约束上的频率；error 的 characteristic function

$$
\widehat D(k)=\mathbb E_e[e^{2\pi ike/q}]
$$

衰减有用频率。标准测量可能保留太多噪声或接受概率太小。

## 4. Quantum filter 的作用

在 error/register 上实现 POVM 或 basis rotation，使某结果的 acceptance amplitude 为函数 $F(e)$。条件于成功，error distribution 变为

$$
D'(e)
\propto D(e)|F(e)|^2.
$$

选择 $F$ 的 Fourier profile：

- 抑制妨碍 phase distinguishability 的 error tails；
- 保留足够总成功概率（至少 inverse polynomial）；
- 让后续 QFT state 接近可由已知解码/hidden-shift 子程序处理的分布。

这是本质量子步骤：filter 可在非计算基中利用 amplitudes/interference；先经典测出 $e$ 会破坏与 secret 的相干关系。Amplitude amplification 可放大成功 filter，但其成本必须乘入。

## 5. 三类可解变体

### Wide SIS$_\infty$

给

$$
A\in\mathbb Z_q^{n\times m}
$$

非常宽，找非零 $x$：

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

（常数 margin）。Bound 接近模数一半，比标准 cryptographic SIS 的“小范数”宽松得多。Filtering/QFT 生成满足 relation 的 bounded vector，wide $m$ 保证足够熵与成功质量。

### LWE with quantum samples

对 polynomial modulus 和 bounded-uniform/Laplace 等 error distributions，filter 整形成可 Fourier 解码的 state，从 polynomial 数量 quantum LWE-like states 恢复 secret。

### EDCP

Extrapolated dihedral coset state 形如

$$
\sum_j\rho(j)|j\rangle|x+js\rangle.
$$

过滤调整 $j$-window/phase resolution，稍微扩展已知 polynomial-time 参数，并通过 reduction 连到上述 LWE solver。

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

论文明确指出可解参数不在已知 worst-case-hard 标准 regime：

- SIS bound 太接近 $q/2$、矩阵特别宽；
- LWE 输入是相干 quantum states，而现实 public samples 是已测经典 pairs；
- error/modulus family 有特定形状；
- reductions 的 approximation factors 不覆盖主流安全参数。

因此这是首次在自然 lattice-related average-case variants 上的 quantum polynomial advantage，而不是 Shor-for-lattices。任何密码影响必须重新证明目标 scheme 能提供所需 quantum samples 与参数映射。

## 7. 与 decoding/DQI 的共同结构

Filtering 与 DQI 都在 Fourier-dual domain 做：

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

差别是格算法的连续/模 Gaussian geometry 与 dual lattice，DQI 主要在有限域 code syndrome 上用可逆 decoder。两者都依赖“测量/解码前保持相干”。

## 8. 小结与习题

- QFT 把 lattice periodicity 变成 dual-lattice frequencies，宽度反转、平移变 phase。
- Quantum filter 通过条件 measurement 重塑 error amplitudes。
- Polynomial algorithms 只覆盖 wide SIS$_\infty$、quantum-sample LWE 与特定 EDCP。
- 标准 SVP/CVP 与主流 LWE/SIS 密码参数没有因此被破解。

1. 对一维格 $a\mathbb Z$ 写出 dual 与 Poisson Fourier peaks。
2. 推导条件 filter 后 $D'(e)$。
3. 比较 classical LWE sample 与 quantum LWE-like state 的信息。
4. 解释 $q/2-c$ 的 SIS bound 为什么远弱于 cryptographic small norm。

## 参考文献

- 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 技术。