# 隐藏平移问题：从 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 覆盖

- 框架与二面体联系：Zoo 43、66、143、312，见 [Friedl 等](https://arxiv.org/abs/quant-ph/0211091)、[Kuperberg](https://arxiv.org/abs/quant-ph/0302112) 与 [Rötteler](https://arxiv.org/abs/1608.02005)。
- 二次特征与有限域平移：Zoo 86、88、89，核心综述论文为 [van Dam--Hallgren--Ip](https://arxiv.org/abs/quant-ph/0211140)。
- Boolean、quadratic 与高阶 Fourier 结构：Zoo 105、130、142，见 [Boolean Hidden Shift](https://arxiv.org/abs/1103.3017)。
- 线性 disequation 与子集学习推广：Zoo 407、408，见 [Ivanyos--Prakash--Santha](https://arxiv.org/abs/1806.09660) 与 [Ivanyos](https://arxiv.org/abs/0704.2988)。