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

在 Abelian 隐藏子群问题中，我们已经看到：Simon、Shor 等算法之所以成功，是因为隐藏结构是一个线性对象——子群 \(H\) 的陪集（coset）是互相平行的 affine flat，而量子傅里叶变换（QFT，见量子傅里叶变换）恰好让平行的 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（量子傅里叶变换）、相位估计（相位估计）、coset state 的基本操作（Abelian 隐藏子群），以及密度矩阵与 fidelity 的概念（量子计算基础）。

本课知识点

  1. level-set oracle 与 level-set 态——能写出 level-set oracle 的划分式定义 \(f(x)=f(y)\iff h(x)=h(y)\)，并由一次相干查询推导 level-set 态 \(|L_{h,a}\rangle\) 与丢弃标签后的混合态 \(\rho_h\)。

  2. 输出仿射等价与信息论极限——能证明 \(h\) 与 \(\alpha h+\beta\)（\(\alpha\ne0\)）诱导相同的 level-set 划分（即 \(\rho_h=\rho_{h'}\)），并解释"恢复到输出仿射等价类"为何是 oracle 的固有信息极限。

  3. 查询复杂度上界——能计算候选多项式总数 \(q^{\binom{d+D}{D}}\)，由小交集估计推出不同候选的 fidelity 严格小于 1，并用 fidelity 的可乘性与 union bound 推导 \(t=O(\log q)\) 份足够。

  4. 经典下界与查询-时间鸿沟——能用生日悖论推导经典算法需要 \(\Omega(\sqrt q)\) 次查询才能撞出同一 level set 的两个点，并解释 pretty good measurement 为何只给出查询上界而非多项式时间算法。

  5. 球面傅里叶谱与特征和——能解释 \(\rho_r\) 的平移不变性为何使 QFT 将其对角化，推导频率概率公式 \(P(k|r)\)，并按四步推导把球面傅里叶和化为 Salié 和（奇数维）或 Kloosterman 和（偶数维）。

  6. 二次特征读出与奇偶分水岭——能应用 Salié 消失判据 \(\chi(r\Delta(k))=-1\Rightarrow P(k|r)=0\) 设计常数次采样判定 \(\chi(r)\) 的算法，并说明完整恢复 \(r\) 与偶数维 Kloosterman 障碍的困难所在。

  7. 量子行走的中心聚焦——能证明 Winnie Li 图邻接矩阵的本征值为 \(\lambda(k)=\widehat{\mathcal S_1}(k)\)，并由一阶展开计算中心振幅 \(\sqrt{|\mathcal S_1|}\)，解释行走时间 \(t\asymp\frac{1}{\sqrt{q^{d-1}\log q}}\) 的选取。

  8. 多项式图的可执行测量——能解释多项式图 oracle 与 QFT 如何把未知系数线性化为频率标签上的低次方程，并逐条说明固定变量数、特征限制与 Jacobian 非退化各假设的技术原因。

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

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\) 诱导的划分，而不依赖于任何数值标签。

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)\) 次查询。但我们会强调：这是一个查询/信息上界，离多项式时间算法还有距离。

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

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\) 是相干的球面叠加，球面整体的几何（而不仅仅是单个点）写进了它的频谱里。

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\)，加法特征满足正交关系

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

（\(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\) 的模长控制，但既没有显式值，也没有高效计算其相位的方法。

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

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 恒等式完全一致。于是

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

可以直接看到"\(\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 图。

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\) 模拟哈密顿量"机器（见相位估计），我们就能高效模拟演化

\[ 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)\) 的值。这一点在傅里叶变换后会变成决定性的优势。

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

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

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

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

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

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

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

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

  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)\) 是可观测的。

参考文献