隐藏非线性结构

在 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 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,\mathrm{deg}h\le D,$$

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

$$f(x)=f(y)⟺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⟩⟼\frac{1}{q^{d/2}}\sum _{x\in {\mathbb{F}}_q^d}|x⟩|f(x)⟩.$$

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

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

上的均匀叠加态

$$|L_{h,a}⟩=\frac{1}{\sqrt{|L_{h,a}|}}\sum _{x\in L_{h,a}}|x⟩.$$

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

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

$${\rho }_h=\sum _{a\in {\mathbb{F}}_q}\frac{|L_{h,a}|}{q^d}|L_{h,a}⟩⟨L_{h,a}|.$$

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

1.3 输出仿射等价：oracle 的固有信息极限

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

$$h^{\prime }(x)=\alpha h(x)+\beta ,\alpha \ne 0,\beta \in {\mathbb{F}}_q,$$

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

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

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

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

2.1 候选总数只有 $q^{O(1)}$ 个

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

$$M=\left(\genfrac{}{}{0ex}{}{d+D}{D}\right),$$

（这是”把至多 $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}$。于是典型地

$$|⟨L_{h,a}|L_{g,b}⟩|=\frac{|L_{h,a}\cap L_{g,b}|}{\sqrt{|L_{h,a}||L_{g,b}|}}\approx \frac{q^{d-2}}{q^{d-1}}=\frac{1}{q}\ll 1:$$

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

$$F({\rho }_h,{\rho }_g)<1-\epsilon ,\epsilon =\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 )=\Vert \sqrt{\rho }\sqrt{\sigma }{\Vert }_1^2$ 或等价地 $\max |⟨{\psi }_{\rho }|{\psi }_{\sigma }⟩{|}^2$（对所有提纯取最大，Uhlmann 定理）；张量积的提纯可以取各份提纯的张量积，内积随之相乘，取最大后等号成立。）

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

$$(1-\epsilon {)}^t\cdot q^{O(1)}\ll 1⟺t\log \frac{1}{1-\epsilon }\gtrsim O(\log q).$$

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

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

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

$$\text{总查询复杂度}=\mathrm{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}$ 降到了 $\mathrm{poly}(\log q)$，这是一个指数级的查询分离。

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

• 上述论证是信息论的。pretty good measurement 是一个存在性对象——它是对 $q^{O(1)}$ 个候选态的联合测量，先验地需要作用在 $O(\log q)$ 份态的张量积上、维数关于 $q$ 指数大的测量算子。没有进一步结构时，我们不知道怎样用 $\mathrm{poly}(\log q)$ 个门实现它。
• 因此 Childs–Schulman–Vazirani 的一般 hidden polynomial 结果（2007，Zoo 编号 23）首先是一个查询复杂度/信息量上界，而非完整的多项式时间算法。
• 随后 Decker–Draisma–Wocjan（Zoo 编号 31）利用多项式图（graph）的特殊结构（见第 5 节），对固定变量数与次数构造了可执行的测量，实现 $\mathrm{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 ix/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⟩=\frac{1}{\sqrt{|{\mathcal{S}}_r|}}\sum _{x\in {\mathcal{S}}_r}|x+t⟩.$$

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

$${\rho }_r=\frac{1}{q^d}\sum _{t\in {\mathbb{F}}_q^d}|{\mathcal{S}}_r+t⟩⟨{\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⟩=|x+u⟩$，则

$$T_u{\rho }_r{T}_u^{†}=\frac{1}{q^d}\sum _t|{\mathcal{S}}_r+t+u⟩⟨{\mathcal{S}}_r+t+u|=\frac{1}{q^d}\sum _{t^{\prime }}|{\mathcal{S}}_r+t^{\prime }⟩⟨{\mathcal{S}}_r+t^{\prime }|={\rho }_r,$$

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

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

$$|\hat{k}⟩=\frac{1}{q^{d/2}}\sum _{x\in {\mathbb{F}}_q^d}e(k\cdot x)|x⟩,$$

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

$${\rho }_r=\sum _{k\in {\mathbb{F}}_q^d}P(k|r)|\hat{k}⟩⟨\hat{k}|:$$

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

3.3 频率概率的显式公式

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

$$⟨\hat{k}|{\mathcal{S}}_r+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)\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$ 无关”在振幅层面的原因。取模平方，相位消失：

$$|⟨\hat{k}|{\mathcal{S}}_r+t⟩{|}^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)=⟨\hat{k}|{\rho }_r|\hat{k}⟩=\frac{1}{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$，加法特征满足正交关系

$$\frac{1}{q}\sum _{c\in {\mathbb{F}}_q}e(cu)=\{\begin{array}{ll}1,& u=0,\\ 0,& u\ne 0,\end{array}$$

（$u=0$ 时每项都是 1，共 $q$ 项；$u\ne 0$ 时 $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 \frac{1}{q}\sum _{c\in {\mathbb{F}}_q}e(c(\Delta (x)-r))=\frac{1}{q}\sum _{c\in {\mathbb{F}}_q}e(-cr)\sum _{x\in {\mathbb{F}}_q^d}e(c\Delta (x)+k\cdot x).$$

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

$$\sum _{x\in {\mathbb{F}}_q^d}e(c\Delta (x)+k\cdot x)=\prod _{j=1}^d\left(\sum _{x_j\in {\mathbb{F}}_q}e(c{x}_j^2+k_j{x}_j)\right).$$

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

$$c{x}^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(c{x}^2+kx)=e\left(-\frac{k^2}{4c}\right)\sum _{x}e(c{x}^2)=\chi (c)Ge\left(-\frac{k^2}{4c}\right),$$

其中 $G={\sum }_{x}e(x^2)$ 是二次高斯和，并用了高斯和的标准性质 ${\sum }_{x}e(c{x}^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\ne 0$ 没有贡献；对 $k=0$ 它贡献主项 $\frac{1}{q}\cdot q^d=q^{d-1}$，正好对应 $\widehat{{\mathcal{S}}_r}(0)=|{\mathcal{S}}_r|\approx q^{d-1}$。

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

$$\widehat{{\mathcal{S}}_r}(k)=\frac{G^d}{q}\sum _{c\ne 0}\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$ 只取 $\pm 1$），求和是

$$\sum _{c\ne 0}\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\ne 0$），求和退化为不带特征的

$$\sum _{c\ne 0}e\left(-cr-\frac{\Delta (k)}{4c}\right),$$

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

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

3.5 读出半径的二次特征

把 3.4 的结论用到 $r\ne 0$ 的奇数维情形。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 (r\Delta (k))=-1⟹\widehat{{\mathcal{S}}_r}(k)=0⟹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}$ 在 $\mathrm{poly}(\log q)$ 时间内算出）。若 $r\ne 0$，两种情形各自禁止一类频率出现，而两类频率在非禁止情形下都占 $\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，所以信息论上 $\mathrm{poly}(\log q)$ 份状态足够确定 $r$（奇数维时谱由 Salié 和的闭式完全描述，可区分性可以直接验证）。

但闭式存在 $\ne$ 测量高效：原工作没有给出在 $\mathrm{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\}$，要求三者之和 $\equiv 1(\mathrm{mod}3)$。由于平方和的实际取值最大为 3，$\Delta (x)=1$ 当且仅当恰好一个坐标非零：选哪个坐标（3 种）$\times$ 该坐标取 $1$ 或 $2$（2 种），故

$$|{\mathcal{S}}_1|=6,{\mathcal{S}}_1=\{(\pm 1,0,0),(0,\pm 1,0),(0,0,\pm 1)\},$$

与主项估计 $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,$$

其中前两项来自 $(\pm 1,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 的判据必须为零。验证：

$$\underset{x=(\pm 1,0,0)}{\underbrace{\omega +{\omega }^2}}+\underset{x=(0,\pm 1,0)}{\underbrace{\omega +{\omega }^2}}+\underset{x=(0,0,\pm 1)}{\underbrace{1+1}}=2(\omega +{\omega }^2)+2=-2+2=0.✓$$

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

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

汇总并验证 Parseval。频率分类计数：$k=0$（1 个，模方 $36$）；重量 1（6 个，每个模方 $9$，共 $54$）；重量 2（$\left(\genfrac{}{}{0ex}{}{3}{2}\right)\cdot 2^2=12$ 个，模方全为 $0$）；重量 3（$2^3=8$ 个，每个模方 $9$，共 $72$）。总计

$$36+54+0+72=162=27\cdot 6=q^d|{\mathcal{S}}_1|,$$

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

$$P(k|r=1)=\frac{|\widehat{{\mathcal{S}}_1}(k){|}^2}{27\cdot 6}=\{\begin{array}{ll}36/162=2/9,& k=0,\\ 9/162=1/18,& \Delta (k)=1\text{或}\Delta (k)=0(k\ne 0),\\ 0,& \chi (\Delta (k))=-1,\end{array}$$

可以直接看到"$\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=\frac{1}{|H|}\sum _{h\in H}|{\mathcal{S}}_1+h⟩⟨{\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^{\prime }$ 相邻当且仅当

$$\Delta (x-x^{\prime })=1,$$

即 $x^{\prime }$ 落在以 $x$ 为中心的单位球面上。它是 $|{\mathcal{S}}_1|$ 度正则图，其邻接矩阵正是”单位球面卷积”

$$A=\sum _{x\in {\mathbb{F}}_q^d}\sum _{s\in {\mathcal{S}}_1}|x+s⟩⟨x|.$$

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

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

$$A|\hat{k}⟩=\frac{1}{q^{d/2}}\sum _x\sum _{s\in {\mathcal{S}}_1}e(k\cdot x)|x+s⟩=\left(\sum _{s\in {\mathcal{S}}_1}e(-k\cdot s)\right)|\hat{k}⟩,$$

（第二步换元 $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é 和，其相位可以用 $\mathrm{poly}(\log q)$ 规模的线路相干地计算（把 $k$ 存在寄存器里，算 $\lambda (k)$ 的辐角并 kick back）；配合相位估计的标准”算相位 $\Rightarrow$ 模拟哈密顿量”机器（见相位估计），我们就能高效模拟演化

$$e^{-iAt}.$$

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

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

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

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

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

$$-itA|{\mathcal{S}}_1+h⟩$$

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

$$⟨h|A|{\mathcal{S}}_1+h⟩=\frac{1}{\sqrt{|{\mathcal{S}}_1|}}\sum _{x\in {\mathcal{S}}_1+h}⟨h|A|x⟩=\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^{\prime }$（$s^{\prime }\in {\mathcal{S}}_1$），于是 $s=-s^{\prime }$。由 ${\mathcal{S}}_1$ 的对称性（4.2 节），$-s^{\prime }\in {\mathcal{S}}_1$ 恒成立，所以每一个 $x\in {\mathcal{S}}_1+h$ 都恰有一个合法的 $s$（即 $s=h-x$），求和共 $|{\mathcal{S}}_1|$ 项：

$$⟨h|A|{\mathcal{S}}_1+h⟩=\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$。于是一阶项在中心产生振幅

$$⟨h|(-itA)|{\mathcal{S}}_1+h⟩=-it\sqrt{|{\mathcal{S}}_1|}\approx -it{q}^{(d-1)/2}.$$

作为对照，看一个一般的非中心点 $y\notin {\mathcal{S}}_1+h$：$⟨y|A|{\mathcal{S}}_1+h⟩$ 数的是把 $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}⟩$ 是本征态，$\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 的公式读出：中心概率为

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

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

把各因子汇总：非 $H$ 点保持近似均匀的背景（每点概率 $\sim q^{-d}$，远小于中心峰的 $1/\log q$），所以单次测量以 $\Omega (1/\log q)$ 概率给出一个真正属于 $H$ 的点。采样 $\mathrm{poly}(\log q)$ 次，得到一组”以 $\Omega (1/\log q)$ 密度掺杂着真点的离群点数据”；维数 $d$ 是常数，枚举少数采样点的 affine span 候选（常数个点张成的 flat，枚举数为采样数的常数次幂），检验哪个 flat 聚集了异常多的采样点，即以高概率恢复 $H$。整个过程的查询数与总时间都是 $\mathrm{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⟩=\frac{1}{q^{m/2}}\sum _{x\in {\mathbb{F}}_q^m}|x+t_1⟩|Q(x)+t_2⟩,t=(t_1,t_2)\text{均匀随机}.$$

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

5.2 傅里叶变换把系数变成频率标签

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

$$\sum _{x}e(k_1\cdot (x+t_1)+k_2(Q(x)+t_2))=e(k_1\cdot t_1+k_2{t}_2)\sum _{x}e(k_1\cdot x+k_{2}Q(x)),$$

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

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

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

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

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

• 固定变量数 $m$ 与次数界：经典方程求解的复杂度随变量数和次数爆炸，只有把它们钉死成常数，$\mathrm{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)$ 份、共 $\mathrm{poly}(\log q)$ 的查询上界——但最优联合测量先验地难以实现，查询上界不等于多项式时间算法；
• 奇维有限域球面的傅里叶谱归结为有闭式的 Salié 和，其消失判据 $\chi (r\Delta (k))=-1\Rightarrow P(k|r)=0$ 使常数次 QFT 采样即可读出半径的二次特征；偶维归结为无闭式的普通 Kloosterman 和，连相干实现其相位都是开放障碍；
• Winnie Li 图量子行走的一阶项把 $|{\mathcal{S}}_1|$ 条壳层边的振幅同相聚焦到中心，取 $t\asymp 1/\sqrt{q^{d-1}\log q}$ 时每份拷贝以 $\Omega (1/\log q)$ 概率命中真实中心，配合 affine span 枚举即可恢复中心 flat；
• 高效总时间算法目前只在已有可执行测量的特定多项式族（多项式图、bivariate 特定函数族）上成立，一般隐藏多项式的高效算法仍然开放。

习题（按难度递进）：

1. 证明：若 $h^{\prime }(x)=\alpha h(x)+\beta$ 且 $\alpha \ne 0$，则 $h$ 与 $h^{\prime }$ 在 ${\mathbb{F}}_q^d$ 上诱导相同的 level-set 划分（即把定义验证完整）；并举例说明 $\alpha =0$ 时结论不成立。
2. 从 ${\rho }_r=q^{-d}{\sum }_t|{\mathcal{S}}_r+t⟩⟨{\mathcal{S}}_r+t|$ 的平移平均出发，补全 3.2 节”${\rho }_r$ 与所有 $T_u$ 对易 $\Rightarrow$ ${\rho }_r$ 在傅里叶基下对角”的论证中缺失的一步：证明 $\{T_u\}$ 的公共本征矢恰为 $|\hat{k}⟩$ 且不同 $k$ 的本征值组互不相同。
3. 设 $F(\rho ,\sigma )\le 1-\epsilon$ 对某个常数 $\epsilon >0$ 成立，候选总数为 $q^c$。用 fidelity 对张量积的可乘性与并集界，详细解出”需要 $t=O(\log q)$ 份”的推导，并说明常数因子依赖哪些量。
4. 用展开式 $e^{-iAt}=I-itA+O(t^2\Vert A{\Vert }^2)$ 解释中心振幅的一阶来源：具体计算 $⟨h|A|{\mathcal{S}}_1+h⟩=\sqrt{|{\mathcal{S}}_1|}$（4.3 节），并估计一个典型非中心点 $y$ 上的对应振幅，验证两者相差约 $q$ 倍。
5. 在 3.7 的例子里改取 $r=2$（非剩余）。重新计算 ${\mathcal{S}}_2$ 与它的全部频率概率 $P(k|r=2)$，验证消失判据的角色互换（现在缺席的是 $\chi (\Delta (k))=+1$ 的频率），并用 Parseval 检查你的结果。
6. 3.4 节第四步中，偶数 $d$ 时 $\chi (c{)}^d=1$ 给出普通 Kloosterman 和。查阅你手头的数论资料（或接受 Weil 界 $|K|\le 2\sqrt{q}$ 为已知），定性解释：为什么”模长有界”不足以让我们相干地模拟 $e^{-iAt}$——算法缺的究竟是模长信息还是相位信息？

参考文献

• Zoo 编号 23：Andrew Childs、Leonard Schulman 与 Umesh Vazirani, Quantum Algorithms for Hidden Nonlinear Structures.
• Zoo 编号 31：Thomas Decker、Jan Draisma 与 Pawel Wocjan, Efficient Quantum Algorithm for Identifying Hidden Polynomials.
• Zoo 编号 212：Thomas Decker、Peter Høyer、Gábor Ivanyos 与 Miklos Santha, Polynomial Time Quantum Algorithms for Certain Bivariate Hidden Polynomial Problems.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch10-hidden-structures/hidden-nonlinear-structures
• 内容遵循 CC BY-NC-SA 4.0 许可协议