# 隐藏非线性结构：有限域球面、中心平坦与隐藏多项式

在 [Abelian 隐藏子群问题](abelian-hidden-subgroup.md)中，我们已经看到：Simon、Shor 等算法之所以成功，是因为隐藏结构是一个**线性**对象——子群 $H$ 的陪集（coset）是互相平行的 affine flat，而量子傅里叶变换（QFT，见[量子傅里叶变换](../ch03-algo-basics/quantum-fourier-transform.md)）恰好让平行的 affine flat 之间发生精确的相长/相消干涉，从而把"子群的生成元"转写为"频率空间中的线性约束"。

一个自然的问题是：**能不能把"直线/平面"换成弯曲的几何对象**——球面、二次曲面，乃至一般的代数簇？oracle 给出的不再是某个子群的陪集标签，而是某个未知多项式 $h$ 的 level set（等值集）标签。这就是 **hidden nonlinear structure（隐藏非线性结构）** 问题，由 Childs、Schulman 与 Vazirani 在 2007 年系统提出（Zoo 编号 23）。

本课研究三个层层递进的实例：

1. **隐藏半径问题**：oracle 给出 $\mathbb F_q^d$ 中随机平移的单位球面，要求读出半径 $r$。我们将看到，有限域球面的傅里叶谱由经典的指数和（Salié 和与 Kloosterman 和）控制，奇数维时可以相干计算，从而用常数次采样读出 $r$ 的二次特征；
2. **隐藏中心平坦问题**：半径固定为 1，但球心均匀分布在一个未知的 affine flat $H$ 上。我们用在 Winnie Li 图上的连续时间量子行走，把球面壳层上的振幅"聚焦"回球心，进而恢复整个 $H$；
3. **隐藏多项式问题**：从多项式的 level-set 态识别多项式本身。这里我们能证明很强的**查询复杂度**上界，但"少量查询足够"与"存在高效可实现的测量"之间存在鸿沟，后续的 Decker–Draisma–Wocjan（Zoo 编号 31）与 bivariate 工作（Zoo 编号 212）只在特定多项式族上填平了这一鸿沟。

这三个例子合在一起，展示了超越 Abelian HSP 之后量子算法的机会与边界：机会在于非线性几何对象的傅里叶谱仍含有可读的信息；边界在于信息论上的可区分性并不自动意味着多项式时间的算法。

**前置知识**：本章假定读者熟悉有限域 $\mathbb F_q$ 的加法特征与 QFT（[量子傅里叶变换](../ch03-algo-basics/quantum-fourier-transform.md)）、相位估计（[相位估计](../ch03-algo-basics/phase-estimation.md)）、coset state 的基本操作（[Abelian 隐藏子群](abelian-hidden-subgroup.md)），以及密度矩阵与 fidelity 的概念（[量子计算基础](../ch01-basics/quantum-computing-basics.md)）。

:::{admonition} 本课知识点
:class: tip

1. **[level-set oracle 与 level-set 态](#level-set-oracle)**——能写出 level-set oracle 的划分式定义 $f(x)=f(y)\iff h(x)=h(y)$，并由一次相干查询推导 level-set 态 $|L_{h,a}\rangle$ 与丢弃标签后的混合态 $\rho_h$。
2. **[输出仿射等价与信息论极限](#output-affine-equivalence)**——能证明 $h$ 与 $\alpha h+\beta$（$\alpha\ne0$）诱导相同的 level-set 划分（即 $\rho_h=\rho_{h'}$），并解释"恢复到输出仿射等价类"为何是 oracle 的固有信息极限。
3. **[查询复杂度上界](#query-upper-bound)**——能计算候选多项式总数 $q^{\binom{d+D}{D}}$，由小交集估计推出不同候选的 fidelity 严格小于 1，并用 fidelity 的可乘性与 union bound 推导 $t=O(\log q)$ 份足够。
4. **[经典下界与查询-时间鸿沟](#query-time-gap)**——能用生日悖论推导经典算法需要 $\Omega(\sqrt q)$ 次查询才能撞出同一 level set 的两个点，并解释 pretty good measurement 为何只给出查询上界而非多项式时间算法。
5. **[球面傅里叶谱与特征和](#sphere-fourier-spectrum)**——能解释 $\rho_r$ 的平移不变性为何使 QFT 将其对角化，推导频率概率公式 $P(k|r)$，并按四步推导把球面傅里叶和化为 Salié 和（奇数维）或 Kloosterman 和（偶数维）。
6. **[二次特征读出与奇偶分水岭](#read-quadratic-character)**——能应用 Salié 消失判据 $\chi(r\Delta(k))=-1\Rightarrow P(k|r)=0$ 设计常数次采样判定 $\chi(r)$ 的算法，并说明完整恢复 $r$ 与偶数维 Kloosterman 障碍的困难所在。
7. **[量子行走的中心聚焦](#winnie-li-graph)**——能证明 Winnie Li 图邻接矩阵的本征值为 $\lambda(k)=\widehat{\mathcal S_1}(k)$，并由一阶展开计算中心振幅 $\sqrt{|\mathcal S_1|}$，解释行走时间 $t\asymp\frac{1}{\sqrt{q^{d-1}\log q}}$ 的选取。
8. **[多项式图的可执行测量](#executable-graph-measurement)**——能解释多项式图 oracle 与 QFT 如何把未知系数线性化为频率标签上的低次方程，并逐条说明固定变量数、特征限制与 Jacobian 非退化各假设的技术原因。

:::

## 1. 从隐藏线性函数到 level sets

(level-set-oracle)=
### 1.1 level-set oracle

先回顾线性情形作对比。在隐藏线性函数问题中，未知对象是一个线性函数 $h(x) = s\cdot x$，oracle 返回的函数值满足"$f(x) = f(y)$ 当且仅当 $h(x) = h(y)$"，于是 $f$ 的每个 level set 都是超平面 $s\cdot x = a$，即隐藏子空间 $s^\perp$ 的一个陪集。标准 HSP 机器（制备均匀叠加、查询、丢弃函数值寄存器、做 QFT、测量）给出关于 $s$ 的线性方程，采样 $O(d)$ 次即可解出 $s$。

现在把线性函数换成**次数受限的未知多项式**

$$
h:\mathbb F_q^d\to\mathbb F_q,\qquad \deg h\le D,
$$

其中维数 $d$ 与次数上界 $D$ 都视为**固定常数**，而域大小 $q$ 是增长的参数（本章所有复杂度都对 $q$ 而言）。oracle 不一定返回 $h(x)$ 本身——那样的话一次查询就直接暴露了 $h$ 的取值信息——而只给 **level-set 标签**：

$$
f(x)=f(y)
\quad\Longleftrightarrow\quad
h(x)=h(y).
$$

也就是说，$f$ 把 $h$ 的每个 level set 染成一种颜色，但颜色本身不携带 $h$ 的数值。这是隐藏结构问题的标准设定：oracle 编码的是**划分（partition）**，而不是函数值。

### 1.2 一次查询产生的量子态

把标准 HSP 的态制备流程套用这个 oracle。先制备均匀叠加并相干地查询 $f$：

$$
\frac{1}{q^{d/2}}\sum_{x\in\mathbb F_q^d}|x\rangle
\;\longmapsto\;
\frac{1}{q^{d/2}}\sum_{x\in\mathbb F_q^d}|x\rangle|f(x)\rangle.
$$

测量第二个寄存器，以概率 $|L_{h,a}|/q^d$ 得到标签 $a$，同时第一个寄存器坍缩到某个 level set

$$
L_{h,a}=\{x\in\mathbb F_q^d:h(x)=a\}
$$

上的**均匀叠加态**

$$
|L_{h,a}\rangle=\frac{1}{\sqrt{|L_{h,a}|}}\sum_{x\in L_{h,a}}|x\rangle.
$$

注意一次相干查询只产生一份这样的态：测量标签这一步把叠加"耗掉"了。

如果我们**丢弃标签 $a$**（或者 oracle 的标签本身被随机置换过，不携带 $a$ 的信息），那么从我们的视角看，得到的是对所有可能标签取平均的混合态。把"以概率 $|L_{h,a}|/q^d$ 得到纯态 $|L_{h,a}\rangle$"写成密度矩阵，就是

$$
\rho_h=\sum_{a\in\mathbb F_q}
\frac{|L_{h,a}|}{q^d}\,
|L_{h,a}\rangle\langle L_{h,a}|.
$$

这个表达式的结构值得停下来看一眼：$\rho_h$ 是若干个（近似）正交的纯态按 level set 大小的加权混合。它只依赖于 $h$ 诱导的**划分**，而不依赖于任何数值标签。

(output-affine-equivalence)=
### 1.3 输出仿射等价：oracle 的固有信息极限

上述观察立刻给出一个不可逾越的限制。设

$$
h'(x)=\alpha\, h(x)+\beta,\qquad \alpha\ne0,\ \beta\in\mathbb F_q,
$$

则 $h'(x)=h'(y)$ 当且仅当 $\alpha h(x)+\beta=\alpha h(y)+\beta$；由于 $\alpha\ne0$ 时可两边消去 $\alpha$、减去 $\beta$，这等价于 $h(x)=h(y)$。因此 $h$ 与 $h'$ 在 $\mathbb F_q^d$ 上诱导**完全相同的 level-set 划分**，从而 $\rho_h=\rho_{h'}$：任何只接触 level-set oracle 的算法（无论量子还是经典、无论用多少资源）都无法区分 $h$ 与 $h'$。

结论是：这类问题的正确提法只能是**恢复到输出仿射变换等价类**——即把 $h$ 确定到"相差一个 $\alpha\ne0$ 的缩放和平移"为止。这不是算法设计者的失误，而是 oracle 自身的信息论限制；后文一切"识别 $h$"的断言都应在这个意义下理解。

## 2. 状态可区分性给出查询上界

本节回答第一个问题：**信息论上**需要多少份 $\rho_h$ 才能确定 $h$（到输出仿射等价）？答案是出乎意料地少：$O(\log q)$ 份，即总共 $\operatorname{poly}(\log q)$ 次查询。但我们会强调：这是一个查询/信息上界，离多项式时间算法还有距离。

(query-upper-bound)=
### 2.1 候选总数只有 $q^{O(1)}$ 个

先数候选。$\mathbb F_q^d$ 上次数不超过 $D$ 的多项式，是次数不超过 $D$ 的单项式的线性组合。$d$ 元次数 $\le D$ 的单项式个数为

$$
M=\binom{d+D}{D},
$$

（这是"把至多 $D$ 次分配给 $d$ 个变量"的标准组合计数）。由于 $d$ 与 $D$ 是固定常数，$M$ 也是常数；每个单项式的系数独立取遍 $\mathbb F_q$，所以候选多项式的总数是

$$
q^M=q^{O(1)}.
$$

再按 1.3 节的输出仿射等价合并，本质不同的候选更少，但对上界而言 $q^{O(1)}$ 已经够用。**候选集合是多项式规模（对 $\log q$ 而言）**——这是整个论证的支点，它与"候选有指数多个"的情形（例如一般的布尔函数）形成鲜明对比。

### 2.2 小交集导致 fidelity 严格小于 1

再看两个不同候选产生的量子态有多容易区分。设 $h,g$ 是两个输出仿射不等价的多项式，考察它们的 level set 的交。$L_{h,a}\cap L_{g,b}$ 是方程组 $h(x)=a,\ g(x)=b$ 的解集：两个独立的代数方程在 $d$ 维空间里通常交出余维 2 的簇，其大小约为 $q^{d-2}$，而单个 level set 的大小约为 $q^{d-1}$。于是典型地

$$
|\langle L_{h,a}|L_{g,b}\rangle|
=\frac{|L_{h,a}\cap L_{g,b}|}{\sqrt{|L_{h,a}|\,|L_{g,b}|}}
\approx\frac{q^{d-2}}{q^{d-1}}=\frac1q\ll1:
$$

不同候选的 level-set 态**几乎正交**。两个混合态 $\rho_h,\rho_g$ 各自是几乎正交纯态的混合，且两边的纯态之间也几乎正交，因此它们的 fidelity

$$
F(\rho_h,\rho_g)<1-\varepsilon,\qquad \varepsilon=\Omega(1),
$$

对典型的不同候选成立（严格的表述与证明见原论文；这里的计数论证给出直觉：小交集 $\Rightarrow$ 小内积 $\Rightarrow$ 小 fidelity）。

### 2.3 fidelity 的乘方衰减与 $t=O(\log q)$ 份

现在做信息论计数。fidelity 有一条关键性质——对张量积是**可乘的**：

$$
F(\rho_h^{\otimes t},\rho_g^{\otimes t})
=F(\rho_h,\rho_g)^t.
$$

（fidelity 定义为 $F(\rho,\sigma)=\|\sqrt\rho\sqrt\sigma\|_1^2$ 或等价地 $\max|\langle\psi_\rho|\psi_\sigma\rangle|^2$（对所有提纯取最大，Uhlmann 定理）；张量积的提纯可以取各份提纯的张量积，内积随之相乘，取最大后等号成立。）

代入 2.2 的估计：$F(\rho_h,\rho_g)^t\le(1-\varepsilon)^t$。我们希望 $t$ 份态足以同时区分**全部** $q^{O(1)}$ 个候选。用联合测量（例如针对等先验混合态渐近最优的 **pretty good measurement**）区分候选时，错误概率被典型候选对的 fidelity 控制；要求即使对全部候选取并集（union bound）错误率仍然是小常数，只需

$$
(1-\varepsilon)^t\cdot q^{O(1)}\ll1
\quad\Longleftrightarrow\quad
t\log\frac{1}{1-\varepsilon}\gtrsim O(\log q).
$$

由于 $\varepsilon=\Omega(1)$，$\log\frac{1}{1-\varepsilon}$ 是正常数，解出

$$
t=O(\log q).
$$

每份 $\rho_h$ 只需要常数次 oracle 查询（1.2 节：一次相干查询加一次测量），于是

$$
\text{总查询复杂度}=\operatorname{poly}(\log q).
$$

(query-time-gap)=
### 2.4 与经典的对比，以及"查询"与"时间"的鸿沟

经典算法面对同样的 oracle 能做什么？一次经典查询得到一个点 $x$ 和它的标签 $f(x)$；要了解 $h$ 的结构，最基本的手段是找到**同一 level set 里的两个点**（碰撞），因为单个标签本身不携带任何数值信息。但每个 level set 在 $q^d$ 个点中只占约 $q^{d-1}$ 个，即比例 $1/q$；由生日悖论，随机查询要在某个 level set 内撞上一次，需要 $\Omega(\sqrt q)$ 次查询——对 $\log q$ 而言是**指数**的。量子算法把 $\sqrt q$ 降到了 $\operatorname{poly}(\log q)$，这是一个指数级的查询分离。

然而必须诚实地指出本节结论的边界：

- 上述论证是**信息论**的。pretty good measurement 是一个存在性对象——它是对 $q^{O(1)}$ 个候选态的联合测量，先验地需要作用在 $O(\log q)$ 份态的张量积上、维数关于 $q$ 指数大的测量算子。没有进一步结构时，我们不知道怎样用 $\operatorname{poly}(\log q)$ 个门实现它。
- 因此 Childs–Schulman–Vazirani 的一般 hidden polynomial 结果（2007，Zoo 编号 23）首先是一个**查询复杂度/信息量上界**，而非完整的多项式时间算法。
- 随后 Decker–Draisma–Wocjan（Zoo 编号 31）利用多项式**图**（graph）的特殊结构（见第 5 节），对固定变量数与次数构造了可执行的测量，实现 $\operatorname{polylog}(q)$ 总时间；再之后的 bivariate 工作（Zoo 编号 212）把多项式时间的具体算法推进到 diagonal quadratic forms、elliptic curves 等特定函数族——但**任意**高次多项式的高效算法仍然超出目前已知的范围。

"少量查询足够，但最优测量可能难以实现"——这个在第 1、2 节埋下的张力，将贯穿全课：第 3 节给出一个测量**可以**高效实现（至少对半径的部分信息）的几何实例，第 4 节再给出一个把查询优势转化为完整算法的实例，第 5 节回到一般多项式并说明可执行测量从哪里来。

## 3. 隐藏半径问题

### 3.1 问题设定

在 $\mathbb F_q^d$（本章推导中取 $q$ 为奇素数以简化书写；一般 $q=p^s$ 时把下文的 $e(x)=e^{2\pi i x/p}$ 换成含迹（trace）的加法特征即可）上定义"平方距离"函数

$$
\Delta(x)=\sum_{j=1}^d x_j^2
$$

和半径 $r\in\mathbb F_q$ 的**球面**

$$
\mathcal S_r=\{x\in\mathbb F_q^d:\Delta(x)=r\}.
$$

在欧氏空间里球面有 $\Theta(q^{d-1})$ 个点这一直觉在有限域中仍然成立：标准的有限域计数给出 $|\mathcal S_r|=q^{d-1}+O(q^{(d-1)/2})$（误差项来自特征和的 Weil 型界，本课只需"主项是 $q^{d-1}$"这一事实）。

oracle 的功能是：经过**两次相干调用**（一次制备叠加并查询、一次在测量标签后把第二寄存器还原），可制备随机中心 $t\in\mathbb F_q^d$ 的**平移球面态**

$$
|\mathcal S_r+t\rangle=\frac{1}{\sqrt{|\mathcal S_r|}}\sum_{x\in\mathcal S_r}|x+t\rangle.
$$

中心 $t$ 均匀随机且**不告诉我们**。对未知的 $t$ 取平均，得到混合态

$$
\rho_r=\frac1{q^d}
\sum_{t\in\mathbb F_q^d}
|\mathcal S_r+t\rangle
\langle\mathcal S_r+t|.
$$

问题：**用尽量少的 $\rho_r$ 副本，确定半径 $r$**（或先确定它的某个比特，例如二次特征）。

先想经典情形：一次经典查询只能看到球面上的一个点。一个点 $x$ 满足 $\Delta(x+t)=r$，其中 $t$ 未知——单个方程里 $t$ 有 $q^d$ 个自由度，$r$ 只有一个，点本身几乎不透露 $r$ 的任何信息。严格地说，原工作证明经典算法获得半径的**任一比特**都需要指数次查询。量子的机会在于：$\rho_r$ 是**相干**的球面叠加，球面整体的几何（而不仅仅是单个点）写进了它的频谱里。

(sphere-fourier-spectrum)=
### 3.2 平移不变性 $\Rightarrow$ QFT 对角化

关键观察：$\rho_r$ 对**所有**平移不变。记平移算子 $T_u|x\rangle=|x+u\rangle$，则

$$
T_u\rho_r T_u^\dagger
=\frac1{q^d}\sum_{t}|\mathcal S_r+t+u\rangle\langle\mathcal S_r+t+u|
=\frac1{q^d}\sum_{t'}|\mathcal S_r+t'\rangle\langle\mathcal S_r+t'|
=\rho_r,
$$

第二步只是换求和指标 $t'=t+u$（$t$ 跑遍整个 $\mathbb F_q^d$ 时 $t'$ 也跑遍）。也就是说 $[\rho_r,T_u]=0$ 对一切 $u$ 成立。

另一方面，全体 $\{T_u\}$ 在傅里叶基下**同时对角化**，且各频率的本征值互不相同。具体地，记加法特征 $e(\cdot)$（$q=p$ 时 $e(x)=e^{2\pi i x/p}$），定义频率为 $k\in\mathbb F_q^d$ 的傅里叶基矢

$$
|\hat k\rangle=\frac{1}{q^{d/2}}\sum_{x\in\mathbb F_q^d}e(k\cdot x)|x\rangle,
$$

则 $T_u|\hat k\rangle=e(-k\cdot u)|\hat k\rangle$（把定义代入、换求和指标即得；相位符号取决于 QFT 的约定，不影响任何测量概率）。由于不同的 $k$ 给出不同的特征值组 $\{e(-k\cdot u)\}_u$，与全体 $T_u$ 都对易的算子必然在傅里叶基下对角——这是"交换算子组的本征空间就是彼此的本征空间"这一标准事实的应用。因此

$$
\rho_r=\sum_{k\in\mathbb F_q^d}P(k|r)\,|\hat k\rangle\langle\hat k|:
$$

**对 $\rho_r$ 做 QFT 再测量，得到频率 $k$ 的概率 $P(k|r)$ 只依赖于 $r$**。整个算法的信息都装在函数 $P(\cdot|r)$ 里，下面把它算出来。

### 3.3 频率概率的显式公式

直接计算对角元。先用定义：

$$
\langle\hat k|\mathcal S_r+t\rangle
=\frac{1}{q^{d/2}\sqrt{|\mathcal S_r|}}
\sum_{x\in\mathcal S_r}e\big(k\cdot(x+t)\big)
=e(k\cdot t)\,\frac{1}{q^{d/2}\sqrt{|\mathcal S_r|}}
\sum_{x\in\mathcal S_r}e(k\cdot x).
$$

注意右端分解出一个只含 $t$ 的相位 $e(k\cdot t)$——平移只改变相位，不改变模长，这正是 3.2 节"频率概率与 $t$ 无关"在振幅层面的原因。取模平方，相位消失：

$$
\big|\langle\hat k|\mathcal S_r+t\rangle\big|^2
=\frac{1}{q^d\,|\mathcal S_r|}
\left|\sum_{x\in\mathcal S_r}e(k\cdot x)\right|^2.
$$

由于它与 $t$ 无关，代入 $\rho_r$ 的混合式后，$q^d$ 个相同的项平均完还是它自己：

$$
P(k|r)=\langle\hat k|\rho_r|\hat k\rangle
=\frac1{q^d|\mathcal S_r|}
\left|
\sum_{x\in\mathcal S_r}
e(k\cdot x)
\right|^2.
$$

于是问题完全归结为一个经典的指数和：**球面 $\mathcal S_r$ 的傅里叶变换**

$$
\widehat{\mathcal S_r}(k):=\sum_{x\in\mathcal S_r}e(k\cdot x).
$$

顺便验证归一化：由 Parseval 恒等式 $\sum_k|\widehat{\mathcal S_r}(k)|^2=q^d|\mathcal S_r|$（有限阿贝尔群上傅里叶变换保持 $\ell^2$ 范数，左端等于 $q^d$ 乘以示性函数的 $\ell^2$ 范数平方 $|\mathcal S_r|$），确实 $\sum_k P(k|r)=1$。

### 3.4 把球面傅里叶和化为特征和：逐步推导

这一步是全场推导的核心，我们把它完全展开。目标是计算 $\widehat{\mathcal S_r}(k)$，思路是指数和理论的标准手法：**用加法特征的正交性把约束 $\Delta(x)=r$ 写成求和，把受约束的和变成自由变量的高斯和**。

第一步（约束写成特征和）。对任意 $u\in\mathbb F_q$，加法特征满足正交关系

$$
\frac1q\sum_{c\in\mathbb F_q}e(cu)=\begin{cases}1,&u=0,\\0,&u\ne0,\end{cases}
$$

（$u=0$ 时每项都是 1，共 $q$ 项；$u\ne0$ 时 $c\mapsto e(cu)$ 是加法群的非平凡特征，特征在群上求和为 0）。取 $u=\Delta(x)-r$，就得到球面示性函数的傅里叶展开：

$$
\widehat{\mathcal S_r}(k)
=\sum_{x\in\mathbb F_q^d}e(k\cdot x)\cdot\frac1q\sum_{c\in\mathbb F_q}e\big(c(\Delta(x)-r)\big)
=\frac1q\sum_{c\in\mathbb F_q}e(-cr)\sum_{x\in\mathbb F_q^d}e\big(c\Delta(x)+k\cdot x\big).
$$

第二步（分离变量）。由于 $c\Delta(x)+k\cdot x=\sum_j(cx_j^2+k_jx_j)$ 是各坐标之和，而 $e(\cdot)$ 把和变成积，$d$ 维求和分解为 $d$ 个一维求和的乘积：

$$
\sum_{x\in\mathbb F_q^d}e\big(c\Delta(x)+k\cdot x\big)
=\prod_{j=1}^d\left(\sum_{x_j\in\mathbb F_q}e\big(cx_j^2+k_jx_j\big)\right).
$$

第三步（一维二次和 $=$ 高斯和）。对 $c\ne0$（此时可用 $2c$ 可逆来配方——这就是需要 $q$ 为奇的原因），配方

$$
cx^2+kx=c\left(x+\frac{k}{2c}\right)^2-\frac{k^2}{4c},
$$

于是（换元 $x\mapsto x-\frac{k}{2c}$ 是 $\mathbb F_q$ 上的双射，不改变求和值）

$$
\sum_{x}e(cx^2+kx)
=e\left(-\frac{k^2}{4c}\right)\sum_x e(cx^2)
=\chi(c)\,G\,e\left(-\frac{k^2}{4c}\right),
$$

其中 $G=\sum_x e(x^2)$ 是**二次高斯和**，并用了高斯和的标准性质 $\sum_x e(cx^2)=\chi(c)G$（$c$ 是二次剩余时换元 $x\mapsto\sqrt c\,x$ 即得；非剩余时求和变号），这里 $\chi$ 是 $\mathbb F_q$ 的**二次特征**（Legendre 符号）：$\chi(c)=1$ 若 $c$ 是非零二次剩余，$\chi(c)=-1$ 若 $c$ 是非剩余，$\chi(0)=0$。高斯和的模长满足 $|G|=\sqrt q$（直接算 $|G|^2=\sum_{x,y}e(x^2-y^2)$ 并换元即得），但我们只需要这个常数模长，不需要它的辐角。

对 $c=0$，一维和退化为 $\sum_x e(kx)=q\,\delta_{k,0}$，它对 $k\ne0$ 没有贡献；对 $k=0$ 它贡献主项 $\frac1q\cdot q^d=q^{d-1}$，正好对应 $\widehat{\mathcal S_r}(0)=|\mathcal S_r|\approx q^{d-1}$。

第四步（合并，得到一维特征和）。把第三步代入第二步、再代入第一步，对 $k\ne0$ 得到

$$
\widehat{\mathcal S_r}(k)
=\frac{G^d}{q}\sum_{c\ne0}\chi(c)^d\,
e\left(-cr-\frac{\Delta(k)}{4c}\right),
$$

注意 $\prod_j e(-k_j^2/(4c))=e(-\Delta(k)/(4c))$ 自动把各坐标的配方余项拼成了 $\Delta(k)$——球面的对称性在这一步自然地重现。现在按维数的奇偶分岔：

- **奇数 $d$**：$\chi(c)^d=\chi(c)$（$\chi$ 只取 $\pm1$），求和是

$$
\sum_{c\ne0}\chi(c)\,e\left(-cr-\frac{\Delta(k)}{4c}\right),
$$

即一个 **Salié 和**（带二次特征 $\chi$ 的 twisted Kloosterman 和）。Salié 和是指数和理论中少数有**闭式**的对象：Salié 的经典定理给出，当乘积 $ab$ 为非零二次剩余时它等于高斯和乘以两个共轭特征值之和（模长 $2\sqrt q$），而当 $ab$ 为**非剩余时它精确等于 0**。
- **偶数 $d$**：$\chi(c)^d=1$（$c\ne0$），求和退化为不带特征的

$$
\sum_{c\ne0}e\left(-cr-\frac{\Delta(k)}{4c}\right),
$$

即普通的 **Kloosterman 和**。Kloosterman 和**没有已知闭式**：Weil 界给出 $|\cdot|\le2\sqrt q$ 的模长控制，但既没有显式值，也没有高效计算其**相位**的方法。

奇偶维数的这一分岔不是技术细节，而是整个问题复杂度的分水岭，马上就会看到。

(read-quadratic-character)=
### 3.5 读出半径的二次特征

把 3.4 的结论用到 $r\ne0$ 的奇数维情形。Salié 和中的"乘积"是

$$
(-r)\cdot\left(-\frac{\Delta(k)}{4}\right)=\frac{r\,\Delta(k)}{4},
$$

而 $4$ 是平方，所以 $\chi(r\Delta(k)/4)=\chi(r\Delta(k))$。Salié 定理的消失判据于是说：

$$
\chi\big(r\,\Delta(k)\big)=-1
\quad\Longrightarrow\quad
\widehat{\mathcal S_r}(k)=0
\quad\Longrightarrow\quad
P(k|r)=0.
$$

换句话说，**谱中被禁止出现的频率集合直接泄露 $\chi(r)$**：

- 若 $r$ 是二次剩余（$\chi(r)=1$）：凡是 $\chi(\Delta(k))=-1$ 的频率都满足 $\chi(r\Delta(k))=-1$，故全部缺席；能出现的频率都有 $\chi(\Delta(k))\in\{0,+1\}$；
- 若 $r$ 是非剩余（$\chi(r)=-1$）：恰好反过来，能出现的频率都有 $\chi(\Delta(k))\in\{0,-1\}$。

算法因此只有三步：制备常数份 $\rho_r$，对每份做 QFT、测得频率 $k$，经典地计算 $\chi(\Delta(k))$（Legendre 符号可用欧拉判据 $\chi(u)=u^{(q-1)/2}$ 在 $\operatorname{poly}(\log q)$ 时间内算出）。若 $r\ne0$，两种情形各自禁止一类频率出现，而两类频率在非禁止情形下都占 $\Omega(1)$ 的概率质量（由 Parseval 和各类频率的数量估计可知），所以**常数次采样**即可以高置信度判定 $\chi(r)$；$r=0$ 的情形（例如谱集中在 $\Delta(k)=0$ 的锥面上）单独判定。对比 3.1 节：经典 oracle 看不到相干球面，获得半径的任一比特需要指数查询——这是又一个指数分离，而且这里连**测量都是显式高效的**（就是 QFT + 计算基测量）。

### 3.6 完整恢复 $r$：能做到哪一步

读出 $\chi(r)$ 只是一个比特。完整恢复 $r$ 需要 $\log q$ 个比特。第 2 节的一般论证在这里适用：候选只有 $q$ 个，不同 $r$ 对应的 $\rho_r$ 之间 fidelity 严格小于 1，所以信息论上 $\operatorname{poly}(\log q)$ 份状态足够确定 $r$（奇数维时谱由 Salié 和的闭式完全描述，可区分性可以直接验证）。

但闭式存在 $\ne$ 测量高效：原工作**没有**给出在 $\operatorname{poly}(\log q)$ 时间内实现这一最优联合测量的普适方法——我们能高效做的是"QFT + 逐份测量"，它能读出 $\chi(r)$，却不足以高效榨出全部 $\log q$ 个比特。偶数维更困难：谱由没有闭式的普通 Kloosterman 和控制，连"高效地相干近似实现谱所要求的相位"这一步本身都是开放障碍。这就是本节开头说的"奇偶分岔是复杂度分水岭"的确切含义。

### 3.7 小例子：$\mathbb F_3^3$ 中单位球面的完整频谱

把上面的推导在一个能手算的例子里完整验证一遍。取 $q=3$，$d=3$（奇数维），$r=1$。此时 $\mathbb F_3=\{0,1,2\}$，平方表为 $0^2=0,\ 1^2=2^2=1$，加法特征 $e(x)=\omega^x$，$\omega=e^{2\pi i/3}$，满足 $1+\omega+\omega^2=0$。

先数球面。$\Delta(x)=x_1^2+x_2^2+x_3^2$，每个 $x_j^2\in\{0,1\}$，要求三者之和 $\equiv1\pmod3$。由于平方和的实际取值最大为 3，$\Delta(x)=1$ 当且仅当**恰好一个**坐标非零：选哪个坐标（3 种）$\times$ 该坐标取 $1$ 或 $2$（2 种），故

$$
|\mathcal S_1|=6,\qquad
\mathcal S_1=\{(\pm1,0,0),(0,\pm1,0),(0,0,\pm1)\},
$$

与主项估计 $q^{d-1}=9$ 同阶（小 $q$ 下误差项相对较大，属正常）。

逐个频率算 $\widehat{\mathcal S_1}(k)=\sum_{x\in\mathcal S_1}\omega^{k\cdot x}$，按 $k$ 的非零坐标个数（重量）分类：

- $k=(0,0,0)$：每项都是 1，和为 $6$；
- 重量 1，如 $k=(1,0,0)$：$\Delta(k)=1$，$\chi(r\Delta(k))=\chi(1)=1$，不应消失。确实

$$
\omega^{1}+\omega^{2}+1+1+1+1=(\omega+\omega^2)+4=-1+4=3,
$$

其中前两项来自 $(\pm1,0,0)$，后四个 1 来自其余四点（它们的 $k\cdot x=0$）；
- 重量 2，如 $k=(1,1,0)$：$\Delta(k)=1+1=2$，而 $2$ 在 $\mathbb F_3$ 中是非剩余（平方只有 $0,1$），$\chi(r\Delta(k))=\chi(2)=-1$，按 3.5 的判据**必须为零**。验证：

$$
\underbrace{\omega+\omega^2}_{x=(\pm1,0,0)}
+\underbrace{\omega+\omega^2}_{x=(0,\pm1,0)}
+\underbrace{1+1}_{x=(0,0,\pm1)}
=2(\omega+\omega^2)+2=-2+2=0.\ \checkmark
$$

- 重量 3，如 $k=(1,1,1)$：$\Delta(k)=3=0$，$\chi(0)=0$，判据不适用（允许非零）。每个 $x\in\mathcal S_1$ 只有一个非零坐标 $\pm1$，故 $k\cdot x=\pm1$，六项为 $\omega,\omega^2$ 各三次：

$$
3\omega+3\omega^2=-3.
$$

汇总并验证 Parseval。频率分类计数：$k=0$（1 个，模方 $36$）；重量 1（6 个，每个模方 $9$，共 $54$）；重量 2（$\binom32\cdot2^2=12$ 个，模方全为 $0$）；重量 3（$2^3=8$ 个，每个模方 $9$，共 $72$）。总计

$$
36+54+0+72=162=27\cdot6=q^d\,|\mathcal S_1|,
$$

与 Parseval 恒等式完全一致。于是

$$
P(k|r=1)=\frac{|\widehat{\mathcal S_1}(k)|^2}{27\cdot6}
=\begin{cases}
36/162=2/9,&k=0,\\
9/162=1/18,&\Delta(k)=1\ \text{或}\ \Delta(k)=0\ (k\ne0),\\
0,&\chi(\Delta(k))=-1,
\end{cases}
$$

可以直接看到"$\chi(r\Delta(k))=-1\Rightarrow P=0$"逐频率成立——这就是 3.5 节消失判据在最小的非平凡例子中的样子。动手把这个例子的每个频率算一遍，比读十遍"Salié 和有闭式"更能让人相信这个判据。

## 4. 隐藏中心平坦：量子行走把壳层聚焦回中心

### 4.1 问题设定

现在把问题反过来：**半径固定为 1，中心未知，而且不止一个中心**——球心 $h$ 均匀分布在一个未知的 affine flat（仿射子空间）$H\subset\mathbb F_q^d$ 上。输入态为

$$
\rho_H=\frac1{|H|}
\sum_{h\in H}
|\mathcal S_1+h\rangle
\langle\mathcal S_1+h|.
$$

目标是恢复 $H$。直觉上这比第 3 节更难：每个纯态是一个半径 1 的"壳层"，壳层上的点离真正的中心 $h$ 都"差一个单位球面矢量"，而 $h$ 本身还藏在一个未知的 flat 里。

核心思想一句话：**把 $\mathcal S_1$ 看成一张图的邻域结构，让量子态在这张图上走一小段时间；壳层上每一点都"知道"自己与中心相邻，于是行走的一阶项把所有壳层点的振幅同时推给中心——这是规模 $|\mathcal S_1|$ 的相长干涉**。这张就是 Winnie Li 图。

(winnie-li-graph)=
### 4.2 Winnie Li 图与邻接矩阵的谱

定义 **Winnie Li 图**：顶点集为 $\mathbb F_q^d$，两个顶点 $x,x'$ 相邻当且仅当

$$
\Delta(x-x')=1,
$$

即 $x'$ 落在以 $x$ 为中心的单位球面上。它是 $|\mathcal S_1|$ 度正则图，其邻接矩阵正是"单位球面卷积"

$$
A=\sum_{x\in\mathbb F_q^d}\sum_{s\in\mathcal S_1}|x+s\rangle\langle x|.
$$

（验证：$\langle x''|A|x\rangle=\#\{s\in\mathcal S_1:x+s=x''\}$，当 $x''-x\in\mathcal S_1$ 即 $\Delta(x''-x)=1$ 时为 1，否则为 0——正是图的邻接关系。注意 $\mathcal S_1$ 对称：$\Delta(-s)=\Delta(s)$，所以 $-s\in\mathcal S_1\iff s\in\mathcal S_1$，$A$ 是厄米的。）

$A$ 是平移不变的卷积算子（$T_uAT_u^\dagger=A$，代入定义换指标即得），因此和第 3 节同理，傅里叶基矢 $|\hat k\rangle$ 是 $A$ 的本征态。本征值可以直接算出来：

$$
A|\hat k\rangle
=\frac{1}{q^{d/2}}\sum_x\sum_{s\in\mathcal S_1}e(k\cdot x)|x+s\rangle
=\left(\sum_{s\in\mathcal S_1}e(-k\cdot s)\right)|\hat k\rangle,
$$

（第二步换元 $x\mapsto x-s$）。即本征值恰是 3.3 节的球面傅里叶和（取 $r=1$）：

$$
\lambda(k)=\widehat{\mathcal S_1}(k)=\sum_{s\in\mathcal S_1}e(k\cdot s).
$$

于是第 3 节的全部谱分析原样搬过来：奇数固定维时 $\lambda(k)$ 是带闭式的 Salié 和，其相位可以用 $\operatorname{poly}(\log q)$ 规模的线路相干地计算（把 $k$ 存在寄存器里，算 $\lambda(k)$ 的辐角并 kick back）；配合相位估计的标准"算相位 $\Rightarrow$ 模拟哈密顿量"机器（见[相位估计](../ch03-algo-basics/phase-estimation.md)），我们就能高效模拟演化

$$
e^{-iAt}.
$$

偶数维则卡在同一个 Kloosterman 障碍上——和第 3.6 节完全一致。

### 4.3 一阶展开：中心振幅从哪里来

现在看短时间演化的效果。对 $e^{-iAt}$ 做泰勒展开（$A$ 厄米，$\|A\|=\max_k|\lambda(k)|$ 有限，展开在算子范数意义下成立）：

$$
e^{-iAt}=I-itA+O\big(t^2\|A\|^2\big).
$$

作用在壳层态 $|\mathcal S_1+h\rangle$ 上，零阶项 $I$ 把态留在壳层上（壳层上每点的振幅为 $1/\sqrt{|\mathcal S_1|}$，总概率 1 摊在 $|\mathcal S_1|\approx q^{d-1}$ 个点上，每点概率仅 $\approx q^{-(d-1)}$）；一阶项

$$
-itA|\mathcal S_1+h\rangle
$$

把每个壳层点沿图的边推一步。考察它在中心 $|h\rangle$ 上的分量：

$$
\langle h|\,A\,|\mathcal S_1+h\rangle
=\frac{1}{\sqrt{|\mathcal S_1|}}\sum_{x\in\mathcal S_1+h}\langle h|A|x\rangle
=\frac{1}{\sqrt{|\mathcal S_1|}}\sum_{x\in\mathcal S_1+h}\#\{s\in\mathcal S_1:x+s=h\}.
$$

条件 $x+s=h$ 即 $s=h-x$；而 $x\in\mathcal S_1+h$ 意味着 $x=h+s'$（$s'\in\mathcal S_1$），于是 $s=-s'$。由 $\mathcal S_1$ 的对称性（4.2 节），$-s'\in\mathcal S_1$ 恒成立，所以**每一个** $x\in\mathcal S_1+h$ 都恰有一个合法的 $s$（即 $s=h-x$），求和共 $|\mathcal S_1|$ 项：

$$
\langle h|\,A\,|\mathcal S_1+h\rangle
=\frac{|\mathcal S_1|}{\sqrt{|\mathcal S_1|}}
=\sqrt{|\mathcal S_1|}
\approx q^{(d-1)/2}.
$$

这就是"聚焦"的全部来源：中心点与壳层的**每一个**点相邻，$|\mathcal S_1|$ 条边的振幅在中心处同相叠加，集体振幅 $\sqrt{|\mathcal S_1|}$ 远大于任何单个壳层点的振幅 $1$。于是一阶项在中心产生振幅

$$
\langle h|\big(-itA\big)|\mathcal S_1+h\rangle
=-it\sqrt{|\mathcal S_1|}\approx -it\,q^{(d-1)/2}.
$$

作为对照，看一个一般的非中心点 $y\notin\mathcal S_1+h$：$\langle y|A|\mathcal S_1+h\rangle$ 数的是把 $y-h$ 写成两个单位球面矢量之和的方式数，对典型的 $y$ 约为 $|\mathcal S_1|^2/q^d\approx q^{d-2}$（$q^d$ 个点均匀分摊 $|\mathcal S_1|^2$ 对），除以自己的 $\sqrt{|\mathcal S_1|}$ 归一化后约为 $q^{(d-3)/2}$——比中心的 $q^{(d-1)/2}$ 小整整一个 $q$ 因子。**中心在一阶项中以 $q$ 倍的振幅优势脱颖而出**，而其它所有点只分到近似均匀的背景。

### 4.4 时间尺度的选取与成功率

还有两个技术步骤。其一，$A$ 有一个"均匀大本征值"：均匀叠加态 $|\hat 0\rangle$ 是本征态，$\lambda(0)=|\mathcal S_1|\approx q^{d-1}$，远大于其它本征值的典型尺度（Salié/Weil 界给出非平凡本征值 $O(q^{(d-1)/2})$ 量级）。这个最大本征值只对应整体的均匀背景，适当把它去掉（在模拟的哈密顿量中减去 $\lambda(0)$ 方向的贡献，等价于演化一个平移过的邻接矩阵），剩下的谱才是携带中心信息的部分。

其二，取行走时间

$$
t\asymp\frac{1}{\sqrt{q^{d-1}\log q}}.
$$

这个尺度的选取理由可以直接从 4.3 的公式读出：中心概率为

$$
\big|t\sqrt{|\mathcal S_1|}\big|^2
\approx t^2 q^{d-1}
=\frac{1}{\log q},
$$

即**每份拷贝以 $\Omega(1/\log q)$ 的概率命中真实中心**；时间再长，$O(t^2\|A\|^2)$ 的高阶项会把振幅重新摊回壳层、一阶聚焦图像失效；时间再短，中心峰的概率更小、得不偿失。$t$ 正是"聚焦足够强"与"一阶展开仍然有效"两个要求平衡的产物。

把各因子汇总：非 $H$ 点保持近似均匀的背景（每点概率 $\sim q^{-d}$，远小于中心峰的 $1/\log q$），所以单次测量以 $\Omega(1/\log q)$ 概率给出一个真正属于 $H$ 的点。采样 $\operatorname{poly}(\log q)$ 次，得到一组"以 $\Omega(1/\log q)$ 密度掺杂着真点的离群点数据"；维数 $d$ 是常数，枚举少数采样点的 affine span 候选（常数个点张成的 flat，枚举数为采样数的常数次幂），检验哪个 flat 聚集了异常多的采样点，即以高概率恢复 $H$。整个过程的查询数与总时间都是 $\operatorname{poly}(\log q)$。

## 5. Polynomial graph 的可执行测量

回到第 2 节埋下的问题：一般的隐藏多项式，fidelity 论证只给查询上界，测量从哪儿来？Decker–Draisma–Wocjan 的答案是：**换一个有更多代数结构的 oracle，让测量问题化成可解的低次方程组**。

### 5.1 多项式图 oracle

他们考虑的 oracle 隐藏的不是 level set，而是多项式的**图（graph）**

$$
\Gamma_Q=\{(x,Q(x)):x\in\mathbb F_q^m\}\subset\mathbb F_q^{m+1},
$$

其中 $Q$ 是 $m$ 个变量、次数受限的未知多项式。与第 1 节完全平行的态制备：均匀叠加、相干查询、测量随机平移标签，得到平移图态

$$
|\Gamma_Q+t\rangle=\frac{1}{q^{m/2}}\sum_{x\in\mathbb F_q^m}|x+t_1\rangle|Q(x)+t_2\rangle,
\qquad t=(t_1,t_2)\ \text{均匀随机}.
$$

与 level set 相比，图多出一层结构：第二个坐标**线性**地承载 $Q(x)$ 的值。这一点在傅里叶变换后会变成决定性的优势。

(executable-graph-measurement)=
### 5.2 傅里叶变换把系数变成频率标签

对 $|\Gamma_Q+t\rangle$ 做 $\mathbb F_q^{m+1}$ 上的 QFT。第二个坐标的傅里叶变换把 $Q(x)$ 变成相位：

$$
\sum_{x}e\big(k_1\cdot(x+t_1)+k_2(Q(x)+t_2)\big)
=e(k_1\cdot t_1+k_2t_2)\sum_x e\big(k_1\cdot x+k_2Q(x)\big),
$$

于是频率态由**多项式指数和** $\sum_x e(k_1x+k_2Q(x))$ 控制。与 3.4 节同理，这个和的相消/相长模式编码了 $Q$ 的系数——区别在于，这里频率标签 $(k_1,k_2)$ 是算法**可观测**的，而未知系数以代数方式参与指数和的构造。

算法的关键一步是选择**可逆坐标变换** $x\mapsto Mx$（$M$ 为可逆矩阵，由算法者自由选取），它把图态变换到新的坐标系，使得未知系数对频率标签的作用被**线性化**：原本"系数出现在指数和的高次项里"这一非线性依赖，经过坐标变换后变成关于系数的低次（以至于线性）代数关系。对少量 level-set superposition 做联合傅里叶处理，测得的频率标签于是给出关于 $Q$ 的规范系数的**低次方程组**，最后用经典有限域方程求解（固定变量数、固定次数时这是 $\operatorname{poly}(\log q)$ 时间的）恢复 $Q$。

这正是第 2 节所缺的那块拼图：一般的 pretty good measurement 无法实现，但在这个具体问题上，"QFT + 坐标线性化 + 经典方程求解"构成一个显式的、$\operatorname{polylog}(q)$ 时间的替代测量。

### 5.3 假设的边界：每一条都不能省略

这里"**低次、固定变量数、除有限个域特征外**"的每一项限制都有具体的技术原因，不可省略：

- **固定变量数 $m$ 与次数界**：经典方程求解的复杂度随变量数和次数爆炸，只有把它们钉死成常数，$\operatorname{poly}(\log q)$ 才成立；
- **除有限个域特征外**：坐标变换的线性化涉及除以次数等整数，当域特征 $p$ 整除这些整数时变换奇异；
- **Jacobian 非退化**：若 $Q$ 的 Jacobian 矩阵退化（或域特征整除次数），坐标映射可能**多对一**，频率标签不再唯一确定系数，成功率证明随之失效。

换句话说，可执行测量不是凭空掉下来的，而是问题里恰好有足够的代数刚性（图结构 + 低次 + 固定维数 + 好的特征）时才能构造出来。后续的 bivariate 算法（Zoo 编号 212）沿同一路线推进，但覆盖的是 diagonal quadratic forms、elliptic curves 等**特定族**，而非任意高次多项式——一般情形的高效总时间算法至今仍是开放的。

## 6. 本课小结

本课从"把 HSP 的线性对象换成非线性对象"这一问题出发，研究了三个层次的隐藏非线性结构：

- level-set oracle 产生的状态只把多项式确定到**输出仿射重标记**（$h\sim\alpha h+\beta$），这是 oracle 的固有信息极限；
- 小交集使候选状态的 fidelity 严格小于 1 并随份数**乘方衰减**，配合候选总数仅 $q^{O(1)}$，给出 $t=O(\log q)$ 份、共 $\operatorname{poly}(\log q)$ 的查询上界——但最优联合测量先验地难以实现，查询上界不等于多项式时间算法；
- 奇维有限域球面的傅里叶谱归结为**有闭式的 Salié 和**，其消失判据 $\chi(r\Delta(k))=-1\Rightarrow P(k|r)=0$ 使常数次 QFT 采样即可读出半径的二次特征；偶维归结为无闭式的普通 Kloosterman 和，连相干实现其相位都是开放障碍；
- Winnie Li 图量子行走的一阶项把 $|\mathcal S_1|$ 条壳层边的振幅同相聚焦到中心，取 $t\asymp1/\sqrt{q^{d-1}\log q}$ 时每份拷贝以 $\Omega(1/\log q)$ 概率命中真实中心，配合 affine span 枚举即可恢复中心 flat；
- 高效**总时间**算法目前只在已有可执行测量的特定多项式族（多项式图、bivariate 特定函数族）上成立，一般隐藏多项式的高效算法仍然开放。

## 练习题

**练习 1【level-set oracle 与 level-set 态】**（→ [1.1 节](#level-set-oracle)）

1. 基础：复述 level-set oracle 的设定：$h:\mathbb F_q^d\to\mathbb F_q$ 次数 $\le D$、$d$ 与 $D$ 固定、oracle 只满足 $f(x)=f(y)\iff h(x)=h(y)$；并解释为什么说"oracle 编码的是划分而不是函数值"。
2. 进阶：从 $\frac{1}{q^{d/2}}\sum_x|x\rangle|f(x)\rangle$ 出发推导：测得标签 $a$ 的概率为 $|L_{h,a}|/q^d$，第一个寄存器相应坍缩为 $|L_{h,a}\rangle$；丢弃标签后得到 $\rho_h=\sum_a\frac{|L_{h,a}|}{q^d}|L_{h,a}\rangle\langle L_{h,a}|$。

> 提示：对固定 $a$，把所有满足 $f(x)=a$ 的 $x$ 的振幅模方相加；再按测量分支以各自概率加权混合。

**练习 2【输出仿射等价与信息论极限】**（→ [1.3 节](#output-affine-equivalence)）

1. 基础：说明 $\rho_h$ 为什么只依赖 $h$ 诱导的 level-set 划分、不依赖标签的数值，并写出"把 $h$ 恢复到输出仿射等价类"的确切含义。
2. 进阶：证明：若 $h'(x)=\alpha h(x)+\beta$ 且 $\alpha\ne0$，则 $h$ 与 $h'$ 在 $\mathbb F_q^d$ 上诱导相同的 level-set 划分（即把定义验证完整）；并举例说明 $\alpha=0$ 时结论不成立。

> 提示：$\alpha=0$ 时 $h'$ 是常数函数，整个 $\mathbb F_q^d$ 只剩一个 level set。

**练习 3【查询复杂度上界】**（→ [2.1 节](#query-upper-bound)）

1. 基础：取 $d=2$、$D=2$，列出全部次数 $\le2$ 的单项式，验证 $M=\binom{4}{2}=6$，并写出候选多项式的总数。
2. 基础：用 $|L_{h,a}|\approx q^{d-1}$、$|L_{h,a}\cap L_{g,b}|\approx q^{d-2}$ 计算 $|\langle L_{h,a}|L_{g,b}\rangle|$ 的近似值，并复述"小交集 $\Rightarrow$ 小内积 $\Rightarrow$ 小 fidelity"的推理链。
3. 进阶：设 $F(\rho,\sigma)\le1-\varepsilon$ 对某个常数 $\varepsilon>0$ 成立，候选总数为 $q^c$。用 fidelity 对张量积的可乘性与并集界，详细解出"需要 $t=O(\log q)$ 份"的推导，并说明常数因子依赖哪些量。

> 提示：要求 $(1-\varepsilon)^t\cdot q^c$ 仍为小常数，两边取对数解出 $t$。

**练习 4【经典下界与查询-时间鸿沟】**（→ [2.4 节](#query-time-gap)）

1. 基础：解释为什么经典算法要了解 $h$ 的结构，最基本的手段是找到同一 level set 里的两个点，而单个点及其标签本身不携带任何数值信息。
2. 进阶：由"每个 level set 在 $q^d$ 个点中约占 $q^{d-1}$ 个"推出两个随机查询同色的概率约为 $1/q$，再用生日悖论推导撞出一次同色对需要 $\Omega(\sqrt q)$ 次查询，并说明它与量子的 $\operatorname{poly}(\log q)$ 之差对 $\log q$ 而言是指数的。
3. 思考：pretty good measurement 是作用在什么对象上的测量？为什么它的存在只给出查询上界，而不自动给出多项式时间算法？

> 提示：$N$ 次查询产生约 $N^2/2$ 个点对，每对同色的概率约 $1/q$。

**练习 5【球面傅里叶谱与特征和】**（→ [3.2 节](#sphere-fourier-spectrum)）

1. 基础：写出 $P(k|r)=\frac{1}{q^d|\mathcal S_r|}\big|\sum_{x\in\mathcal S_r}e(k\cdot x)\big|^2$，并说明平移相位 $e(k\cdot t)$ 为何在取模平方后消失、从而 $P(k|r)$ 与随机中心无关。
2. 进阶：从 $\rho_r=q^{-d}\sum_t|\mathcal S_r+t\rangle\langle\mathcal S_r+t|$ 的平移平均出发，补全 3.2 节"$\rho_r$ 与所有 $T_u$ 对易 $\Rightarrow$ $\rho_r$ 在傅里叶基下对角"的论证中缺失的一步：证明 $\{T_u\}$ 的公共本征矢恰为 $|\hat k\rangle$ 且不同 $k$ 的本征值组互不相同。
3. 进阶：完成 3.4 节第三步的推导：由配方 $cx^2+kx=c\big(x+\frac{k}{2c}\big)^2-\frac{k^2}{4c}$ 推出 $\sum_x e(cx^2+kx)=\chi(c)\,G\,e\big({-k^2}/{4c}\big)$，并说明 $|G|=\sqrt q$ 从何而来。

> 提示：配方后换元 $z=x+\frac{k}{2c}$；$|G|^2=\sum_{x,y}e(x^2-y^2)$ 再作换元。

**练习 6【二次特征读出与奇偶分水岭】**（→ [3.5 节](#read-quadratic-character)）

1. 基础：写出奇数维的消失判据 $\chi(r\Delta(k))=-1\Rightarrow\widehat{\mathcal S_r}(k)=0\Rightarrow P(k|r)=0$，据此分别列出 $r$ 为二次剩余与非剩余时"能出现的频率"满足的 $\chi(\Delta(k))$ 取值，并说明测得 $k$ 后如何用欧拉判据经典地算出 $\chi(\Delta(k))$。
2. 进阶：在 3.7 的例子里改取 $r=2$（非剩余）。重新计算 $\mathcal S_2$ 与它的全部频率概率 $P(k|r=2)$，验证消失判据的角色互换（现在缺席的是 $\chi(\Delta(k))=+1$ 的频率），并用 Parseval 检查你的结果。
3. 进阶：3.4 节第四步中，偶数 $d$ 时 $\chi(c)^d=1$ 给出普通 Kloosterman 和。查阅你手头的数论资料（或接受 Weil 界 $|K|\le2\sqrt q$ 为已知），定性解释：为什么"模长有界"不足以让我们相干地模拟 $e^{-iAt}$——算法缺的究竟是模长信息还是相位信息？

> 提示：在 $\mathbb F_3$ 中平方只能取 $0,1$，$\Delta(x)=2$ 当且仅当 $x$ 恰有两个非零坐标。

**练习 7【量子行走的中心聚焦】**（→ [4.2 节](#winnie-li-graph)）

1. 基础：写出 Winnie Li 图的顶点集与邻接条件 $\Delta(x-x')=1$，并验证 $A=\sum_x\sum_{s\in\mathcal S_1}|x+s\rangle\langle x|$ 实现该邻接关系、由 $\Delta(-s)=\Delta(s)$ 保证 $A$ 厄米。
2. 进阶：用展开式 $e^{-iAt}=I-itA+O(t^2\|A\|^2)$ 解释中心振幅的一阶来源：具体计算 $\langle h|A|\mathcal S_1+h\rangle=\sqrt{|\mathcal S_1|}$（4.3 节），并估计一个典型非中心点 $y$ 上的对应振幅，验证两者相差约 $q$ 倍。
3. 思考：说明行走时间 $t\asymp\frac{1}{\sqrt{q^{d-1}\log q}}$ 如何同时满足"中心概率 $\approx1/\log q$"与"一阶展开仍然有效"，以及为什么要先去掉均匀大本征值 $\lambda(0)=|\mathcal S_1|$。

> 提示：每条把壳层点 $x=h+s'$ 推向中心的边对应 $s=h-x=-s'\in\mathcal S_1$，$|\mathcal S_1|$ 条边同相叠加。

**练习 8【多项式图的可执行测量】**（→ [5.2 节](#executable-graph-measurement)）

1. 基础：写出多项式图 $\Gamma_Q=\{(x,Q(x)):x\in\mathbb F_q^m\}$ 与平移图态 $|\Gamma_Q+t\rangle$ 的定义，并指出与 level-set 态相比，图结构多出的那一层"第二坐标线性承载 $Q(x)$"意味着什么。
2. 进阶：解释可逆坐标变换 $x\mapsto Mx$ 在算法中的作用：它为什么能把未知系数对频率标签的依赖线性化，使得测得的频率标签给出关于 $Q$ 的规范系数的低次方程组，从而经典求解即可恢复 $Q$？
3. 思考：逐条说明 5.3 节的限制——固定变量数与次数、除有限个域特征外、Jacobian 非退化——各自防住了哪种失效。

> 提示：第二个坐标的 QFT 把 $Q(x)$ 变成相位 $e(k_2Q(x))$，而频率标签 $(k_1,k_2)$ 是可观测的。

## 参考文献

- Zoo 编号 23：Andrew Childs、Leonard Schulman 与 Umesh Vazirani, [Quantum Algorithms for Hidden Nonlinear Structures](https://arxiv.org/abs/0705.2784).
- Zoo 编号 31：Thomas Decker、Jan Draisma 与 Pawel Wocjan, [Efficient Quantum Algorithm for Identifying Hidden Polynomials](https://arxiv.org/abs/0706.1219).
- Zoo 编号 212：Thomas Decker、Peter Høyer、Gábor Ivanyos 与 Miklos Santha, [Polynomial Time Quantum Algorithms for Certain Bivariate Hidden Polynomial Problems](https://arxiv.org/abs/1305.1543).