隐藏平移问题：从 Fourier 相位到 Legendre 符号与 Boolean 函数

周期问题问“哪个平移不改变一个函数”；隐藏平移问题则给出两个形状相同、位置不同的函数，要求找出它们之间的位移。这个看似微小的改动统一了二面体 HSP、移位二次特征、bent Boolean 函数和许多非线性黑盒问题。本课先推导 injective 情形的相位态，再说明哪些额外 Fourier 结构能把相位高效解码。

1. 定义、唯一性与稳定子

设有限 Abel 群 \(G\)，给定 oracle \(f_0,f_1:G\to S\)，承诺存在 \(s\in G\) 使

\[ f_1(x)=f_0(x+s). \]

若 \(f_0\) 是一一函数，\(s\) 唯一。一般情况下定义稳定子

\[ H=\{h\in G:f_0(x+h)=f_0(x),\ \forall x\}. \]

那么 \(s\) 只确定到陪集 \(s+H\)；算法若输出其中任一代表元就是正确的。把这个事实忽略，会把不可辨识性误判成算法失败。

2. 一次查询如何产生带位移相位的态

制备函数选择位与群寄存器的均匀叠加：

\[ \frac1{\sqrt{2|G|}} \sum_{x\in G} \bigl(|0,x,f_0(x)\rangle+|1,x,f_1(x)\rangle\bigr). \]

假设 \(f_0\) injective，测量函数值为 \(f_0(u)\) 后，只有两项保留：

\[ \frac{|0,u\rangle+|1,u-s\rangle}{\sqrt2}. \]

对群寄存器做 Abelian QFT。若测得特征标签 \(y\)，忽略共同全局相位 \(\chi_y(u)\)，选择位成为

\[ |\phi_y(s)\rangle =\frac{|0\rangle+\chi_y(-s)|1\rangle}{\sqrt2}. \]

位移没有出现在测量概率 \(y\) 中，而是藏在剩余量子比特的相对相位里。问题的真正难点是：怎样从随机特征 \(y\) 的相位 \(\chi_y(s)\) 恢复 \(s\)？

3. 与 generalized dihedral HSP 的等价关系

构造广义二面体群

\[ \operatorname{Dih}(G)=G\rtimes\mathbb Z_2, \]

其中非平凡的 \(\mathbb Z_2\) 元素把 \(x\) 变为 \(-x\)。把 \(f_0,f_1\) 放在两个群分支上，所得函数隐藏由一个“反射” \((s,1)\) 生成的二阶子群。上面的 \(|\phi_y(s)\rangle\) 正是二面体 HSP 的相位态。

因此，对任意 injective hidden shift，Kuperberg 筛法给出

\[ \exp(O(\sqrt{\log|G|})) \]

型次指数算法；反过来，二面体 HSP 也可写成两个 injective 函数的隐藏平移。特殊函数若具有平坦且可计算的 Fourier 谱，则能远快于通用筛法。

4. \(\mathbb Z_2^n\)：相位直接成为线性方程

在 Boolean 向量群中

\[ \chi_y(s)=(-1)^{y\cdot s}. \]

测量选择位的 \(X\) 基便确定 \(y\cdot s\)。对 injective 函数，收集 \(O(n)\) 个独立随机 \(y\) 后，用 \(\mathbb F_2\) 消元恢复 \(s\)。这是 Simon 式线性代数的“两个函数版本”。

但 Boolean 值函数 \(f:\mathbb Z_2^n\to\{0,1\}\) 不可能 injective。设相位函数 \(F(x)=(-1)^{f(x)}\)。若 \(f\) 是 bent 函数，其归一化 Fourier 变换满足

\[ \widehat F(y)=2^{-n/2}(-1)^{\widetilde f(y)}, \]

即所有 Fourier 系数模相等，符号由可计算的 dual bent function \(\widetilde f\) 给出。对移位函数

\[ G(x)=F(x+s) \]

有

\[ \widehat G(y)=(-1)^{y\cdot s}\widehat F(y). \]

先查询 \(G\) 的相位，Hadamard 变换到频域，再用 \(\widetilde f(y)\) 消去已知 Fourier 符号，最后 Hadamard 逆变换，便把 \((-1)^{y\cdot s}\) 聚焦为 \(|s\rangle\)。

对任意 Boolean 函数，Fourier 谱不再平坦。Gavinsky--Rötteler--Roland 的算法复杂度由函数的最小 influence 控制；随机 Boolean 函数通常有足够大的 influence，从而得到平均情形多项式时间与经典指数分离，但最坏函数不因此自动高效。

5. 移位 Legendre 符号为何可高效求解

在奇素域 \(\mathbb F_p\) 中令 \(\chi\) 为二次乘法特征，oracle 给出

\[ f_s(x)=\chi(x+s). \]

其加法 Fourier 变换满足平移定理

\[ \widehat f_s(y) =\psi(-sy)\widehat\chi(y), \]

其中 \(\psi(z)=e^{2\pi iz/p}\)。非零频率上，\(\widehat\chi(y)\) 的模由 Gauss 和给出并保持平坦，其相位又可由 \(\chi(y)\) 与已知 Gauss 相位表达。量子算法的步骤是：

  1. 将 \(f_s(x)\) 写入相位，制备移位特征态；

  2. 做加法 QFT，得到带有 \(\psi(-sy)\) 的频域态；

  3. 相干消去已知的 \(\widehat\chi(y)\) 相位；

  4. 逆 QFT，将线性相位聚焦到 \(|-s\rangle\)。

\(x=-s\) 处 Legendre 符号为 0，会造成一个缺失振幅，但其权重只有 \(1/p\)，不会破坏常数成功率。这里的超多项式优势来自特定二次特征结构，而不是任意移位函数。

6. Hidden coset 与非线性推广

hidden coset 问题同时要求恢复稳定子 \(H\) 和使 \(f_1(x)=f_0(x+s)\) 的陪集 \(s+H\)，统一了 HSP（令 \(f_0=f_1\)）与唯一 hidden shift（令 \(H=\{0\}\)）。Friedl 等给出了 translating coset 框架，用群作用和递归正规列处理若干可解群。

其他高效或次指数结果依赖不同谱结构：quadratic forms 与高 Gowers norm、weighing matrices、Abelian difference sets、随机线性 disequations，以及从子集样本学习线性函数。它们共享的模式是：先证明 Fourier 质量集中在可解码集合，再设计相位校正；只知道“存在位移”本身通常不够。

7. 小例子：循环数组的未知平移

令 \(G=\mathbb Z_8\)，\(f_0(x)\) 返回八个互异标签，\(f_1(x)=f_0(x+3)\)。测得某一标签后得到

\[ \frac{|0,u\rangle+|1,u-3\rangle}{\sqrt2}. \]

若 QFT 测得 \(y=2\)，选择位相对相位为

\[ e^{-2\pi i(2)(3)/8}=i. \]

不同随机 \(y\) 给出关于 \(s=3\) 的不同模相位。通用二面体筛法负责把这些随机标签组合成易读频率；若群是 \(\mathbb Z_2^n\)，相位只有 \(\pm1\)，则每份状态已直接给出一位线性信息。

8. 小结与习题

  • 测量函数值把两个移位输入配成相干二项态。

  • QFT 后位移成为随机特征上的相对相位 \(\chi_y(s)\)。

  • injective hidden shift 等价于 generalized dihedral HSP；一般算法为次指数。

  • bent 函数与二次特征的平坦 Fourier 谱允许相位校正并高效恢复位移。

  1. 按本课 QFT 约定推导 \(|\phi_y(s)\rangle\) 中的负号。

  2. 证明 hidden shift 只确定到 \(s+H\)。

  3. 推导 Fourier 平移定理 \(\widehat f_s(y)=\chi_y(-s)\widehat f_0(y)\)。

  4. 解释 Legendre oracle 的单个零值为何只造成 \(O(1/p)\) 误差。

参考文献与 Zoo 覆盖