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

Abelian HSP 能找到隐藏线性子空间，因为 QFT 让平行 affine flats 发生精确干涉。能否把“直线/平面”换成球面或高次代数簇？本课研究三个层次：从随机平移球面读出半径、把球面振幅量子行走回中心、以及从多项式 level-set state 识别隐藏多项式。它们展示了新量子算法的机会，也展示了“少量查询足够”和“存在高效测量”之间的差距。

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

设

$$
h:\mathbb F_q^d\to\mathbb F_q
$$

为次数受限的未知多项式。oracle 不一定返回 $h(x)$ 本身，而只给 level-set 标签：

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

一次均匀查询并测量标签，得到某个 level set

$$
L_{h,a}=\{x:h(x)=a\}
$$

上的均匀态 $|L_{h,a}\rangle$。丢弃 $a$ 后得到依赖 $h$ 的混合态

$$
\rho_h=\sum_a
\frac{|L_{h,a}|}{q^d}
|L_{h,a}\rangle\langle L_{h,a}|.
$$

若 $h'(x)=\alpha h(x)+\beta$ 且 $\alpha\ne0$，两者 level-set partition 相同，所以只能恢复到这类输出仿射变换等价；这是 oracle 自身的信息限制。

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

对候选 $h,g$，若 level sets 的交都很小，则 $\rho_h$ 与 $\rho_g$ 的 fidelity 严格小于 1。取 $t$ 份独立状态后，fidelity 乘方衰减：

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

当变量数和次数固定时，候选多项式数是 $q^{O(1)}$。若典型不同候选间 fidelity 至多 $1-\Omega(1)$，则 $t=O(\log q)$ 份状态在信息论上足以联合区分全部候选。每份只需常数 oracle 查询，于是查询复杂度为 $\operatorname{poly}(\log q)$，而经典算法为找到 level-set 碰撞通常需要 $\Omega(\sqrt q)$ 甚至更高查询。

但最优 pretty-good measurement 可能难以实现。Childs--Schulman--Vazirani 的一般 hidden polynomial 结果首先是查询/信息上界；Decker--Draisma--Wocjan 随后对 polynomial graph 结构构造可执行测量，在固定变量数与次数下实现 $\operatorname{polylog}(q)$ 总时间。后续 bivariate 算法覆盖 diagonal quadratic forms、elliptic curves 等特定族，而非任意高次多项式。

## 3. 隐藏半径问题

在 $\mathbb F_q^d$ 定义“平方距离”

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

和半径 $r$ 的球面

$$
\mathcal S_r=\{x:\Delta(x)=r\}.
$$

oracle 经过两次相干调用可制备随机中心 $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$ 对所有 translation 不变，故加法 QFT 将它对角化。测得频率 $k$ 的概率为

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

球面的 Fourier 和可写成 twisted Kloosterman sum。奇数 $d$ 时它是有闭式的 Salié sum；当 $r\ne0$，若

$$
\chi(r\Delta(k))=-1,
$$

则该频率概率为 0。重复常数次采样并计算二次特征 $\chi(\Delta(k))$，即可判断 $r$ 是二次剩余、非剩余还是 0。经典 oracle 看不到相干球面，获得任一半径比特需要指数查询。

完整恢复 $r$ 在奇数维只需 $\operatorname{poly}(log q)$ 份状态，但原工作没有给出同样高效的普适测量；偶数维涉及无闭式的普通 Kloosterman sum，连高效近似其所需相位也形成开放障碍。

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

现在半径固定为 1，中心 $h$ 均匀分布在未知 affine flat $H$。输入态为

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

定义 Winnie Li 图：顶点为 $\mathbb F_q^d$，若

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

则连边。邻接矩阵是单位球面卷积

$$
A=\sum_x\sum_{s\in\mathcal S_1}|x+s\rangle\langle x|.
$$

平移不变性使 Fourier 态成为 $A$ 的本征态，本征值正是单位球面的 Fourier/Salié 和，因此奇数固定维时可相干计算并模拟

$$
e^{-iAt}.
$$

从 $|\mathcal S_1+h\rangle$ 出发，短时间展开的第一阶项

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

在中心 $|h\rangle$ 产生相长振幅。适当去掉均匀大本征值并取

$$
t\asymp1/\sqrt{q^{d-1}\log q},
$$

测到真实中心的总概率为 $\Omega(1/\log q)$，非 $H$ 点近似均匀背景。采样 $\operatorname{poly}(log q)$ 次得到含离群点的数据，再枚举常数维 affine span 候选，即恢复 $H$。

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

另一种 oracle 隐藏多项式图

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

测量随机平移标签得到 $|\Gamma_Q+t\rangle$。对固定 $m$ 与次数，Fourier 变换把图态变成由多项式指数和控制的频率态。算法选择可逆坐标变换，把未知系数对频率标签的作用线性化；对少量 level-set superposition 做联合 Fourier 处理与经典低次方程求解，恢复 $Q$ 的规范系数。

这里“低次、固定变量数、除有限个域特征外”不可省略：Jacobian 退化或域特征整除次数时，坐标映射可能多对一，成功率证明会失效。

## 6. 小结与习题

- level-set oracle 产生的状态只确定多项式到输出仿射重标记。
- 小交集使候选状态的 fidelity 乘方衰减，给出多项式查询上界。
- 奇维有限域球面的 Fourier 谱由 Salié sum 控制，可读出半径二次特征。
- Winnie Li 图量子行走把球面壳层振幅聚焦到中心，进而恢复中心 flat。
- 高效总时间只在已有可实现测量的特定多项式族成立。

1. 证明 $h$ 与 $\alpha h+\beta$ 产生相同 level-set partition。
2. 从 translation average 推导 $\rho_r$ 在 Fourier 基对角。
3. 解释为何 $F(\rho,\sigma)<1$ 时 $O(\log q)$ 份可区分 $q^{O(1)}$ 个候选。
4. 用 $e^{-iAt}=I-itA+O(t^2\|A\|^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).