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

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)\) 解释中心振幅的一阶来源。

参考文献