隐藏平移问题

周期问题问“哪个平移不改变一个函数”；隐藏平移问题（hidden shift problem）则给出两个形状相同、位置不同的函数，要求找出它们之间的位移。这个看似微小的改动统一了二面体隐藏子群问题、移位二次特征、bent Boolean 函数和许多非线性黑盒问题，并且是把“量子相位估计”推广到非交换结构时遇到的第一个真正的障碍：位移信息全部藏在相位里，而相位挂在一个我们控制不了的随机标签上。

本词条的组织如下：第 1–2 节给出定义并完成核心推导——一次查询如何把位移编码成相对相位；第 3 节建立它与广义二面体 HSP 的等价，解释为什么通用算法只能是次指数的；第 4–5 节研究两类“谱平坦”的特殊函数（${\mathbb{Z}}_2^n$ 上的 bent 函数与有限域上的 Legendre 符号），说明额外的 Fourier 结构怎样把随机相位变成可解码的线性方程；第 6 节简述 hidden coset 等推广；第 7 节用一个可手算的小例子把全部概念过一遍。

前置知识：的量子 Fourier 变换与 Simon 算法、的群表示矩阵元。我们直接引用“有限 Abel 群的特征标构成对偶群、QFT 实现群寄存器到频率寄存器的酉变换”这些事实，不再重新推导。

0. 问题从哪里来：周期、对称与图同构

先回顾一下我们已经熟悉的图景。Simon 问题和 Shor 算法中的周期寻找都是这样的问题：给定函数 $f$，找出所有满足 $f(x+h)=f(x)$ 的平移 $h$——即函数的对称。隐藏平移问题问的则是对偶的问题：函数本身没有任何对称，但它有两个拷贝，一个被未知地平移了，要求找出这个平移量。

为什么这个问题值得单独研究？至少有三条线索：

• 图同构的联系。图同构问题可以归约为对称群上的隐藏子群问题，而其中最难的情形经过进一步归约后，与二面体群上的 HSP 密切相关；下文将看到，二面体 HSP 与隐藏平移问题是等价的。因此隐藏平移是“图同构量子算法”这条研究路线上的核心障碍之一。
• 密码学的压力测试。移位 Legendre 符号一类的构造曾被提议作为“量子安全的伪随机函数”候选：如果移位特征问题能被量子算法高效求解，这类候选就被攻破。van Dam、Hallgren 与 Ip 的工作正是沿这条线给出了多项式时间量子算法。
• 方法论价值。隐藏平移迫使我们把“Fourier 采样”推向极限：测量结果是一个随机特征标签 $y$，而答案藏在相位 ${\chi }_y(s)$ 里。如何相干地利用一堆随机相位，催生了 Kuperberg 筛法以及一批利用特殊谱结构的精巧算法。

经典算法能做到什么程度？对一般的 injective（一一）函数 $f_0$，经典算法唯一可用的策略是在两个 oracle 之间寻找碰撞：查询一批 $f_0(x)$ 和一批 $f_1(x^{\prime })$，若出现 $f_0(x)=f_1(x^{\prime })$ 则 $s=x-x^{\prime }$。由生日悖论，需要 $\Theta (\sqrt{|G|})$ 次查询才能以可观概率碰到一次碰撞，而且在黑盒模型下这是最优的。也就是说，经典查询复杂度关于 $\log |G|$ 是指数的。本词条将看到：量子算法对一般情形能达到次指数 $\exp (O(\sqrt{\log |G|}))$，对具有平坦 Fourier 谱的特殊函数能达到多项式。

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

定义（隐藏平移问题）。设 $G$ 为有限 Abel 群，$S$ 为某个有限标签集。通过黑盒（oracle）给定两个函数 $f_0,f_1:G\to S$，并承诺存在 $s\in G$ 使得

$$f_1(x)=f_0(x+s),\forall x\in G.$$

任务是求出 $s$。每次查询允许以叠加态访问 $f_0$ 或 $f_1$（必要时还可以用选择位控制查询哪一个），我们以查询次数衡量复杂度。

一个首要问题是：$s$ 是否良定义？答案取决于 $f_0$ 的对称性。

定义（稳定子）。函数 $f_0$ 的**稳定子（stabilizer）**是

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

容易验证 $H$ 是 $G$ 的子群：$0\in H$；若 $h_1,h_2\in H$，则 $f_0(x+h_1+h_2)=f_0(x+h_1)=f_0(x)$，故 $h_1+h_2\in H$；若 $h\in H$，把 $x$ 换成 $x-h$ 即得 $f_0(x-h)=f_0(x)$，故 $-h\in H$。

Lemma 1. $s$ 满足承诺当且仅当整个陪集 $s+H$ 中的每个元素都满足承诺。

证明。分两个方向。

• 充分性：任取 $h\in H$。对任意 $x$，

$$f_0(x+(s+h))=f_0((x+s)+h)=f_0(x+s)=f_1(x),$$

其中第二个等号用了稳定子的定义（把 $x+s$ 看作定义中的“$x$”），第三个等号用了承诺条件。所以 $s+h$ 也是合法解。

• 必要性：设 $s$ 与 $s^{\prime }$ 都满足承诺。则对任意 $x$，

$$f_0(x+s)=f_1(x)=f_0(x+s^{\prime }).$$

令 $h=s^{\prime }-s$，并把 $x$ 替换为 $x-s$（$x$ 遍历 $G$ 时 $x-s$ 也遍历 $G$），得 $f_0(x)=f_0(x+h)$ 对所有 $x$ 成立，即 $h\in H$，故 $s^{\prime }=s+h\in s+H$。Q.E.D.

两个极端情形值得记住：若 $f_0$ 是一一函数（injective），则 $H=\{0\}$，$s$ 唯一——称为唯一隐藏平移（unique hidden shift）；若 $f_0=f_1$（即承诺的位移可以是 $s=0$，但我们不知道），则问题退化为求整个稳定子 $H$，这正是隐藏子群问题。所以隐藏平移把 HSP 作为特例包含进来，而其“唯一”情形是 HSP 的某种对偶。把这个事实忽略，会把不可辨识性误判成算法失败：当 $H$ 非平凡时，任何算法最多只能输出陪集 $s+H$ 中的一个代表元，而输出任一代表元都应视为正确。

以下两节先集中处理 injective 情形——它已经是全部困难所在；非平凡 $H$ 的情形在第 6 节讨论。

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

本节完成全课最核心的推导：从 oracle 访问到“相位态”$|{\varphi }_y(s)⟩$ 的完整过程。整个流程分四步：制备叠加、查询、测量函数值、做 QFT。

第一步：制备均匀叠加。取三个寄存器：一个“函数选择位”（选 $f_0$ 还是 $f_1$）、一个群寄存器（存储 $x\in G$）、一个函数值寄存器。在选择位上放 $|+⟩=\frac{|0⟩+|1⟩}{\sqrt{2}}$，在群寄存器上放均匀叠加 $\frac{1}{\sqrt{|G|}}{\sum }_{x\in G}|x⟩$，初态为

$$\frac{1}{\sqrt{2|G|}}\sum _{x\in G}(|0⟩|x⟩+|1⟩|x⟩)|0⟩.$$

第二步：查询 oracle。受选择位控制，把函数值写入第三个寄存器：

$$\frac{1}{\sqrt{2|G|}}\sum _{x\in G}(|0⟩|x⟩|f_0(x)⟩+|1⟩|x⟩|f_1(x)⟩).$$

这是一步标准 oracle 调用，对两个函数各查询一次（相干地）。

第三步：测量函数值寄存器。假设 $f_0$ injective。设测量结果为某个标签 $v$，它在 $f_0$ 下的原像是唯一的，记 $u:=f_0^{-1}(v)$。考察叠加中哪些项的第三寄存器等于 $|v⟩$：

• 选择位为 $0$ 的项要求 $f_0(x)=v$，即 $x=u$，恰有一项；
• 选择位为 $1$ 的项要求 $f_1(x)=f_0(x+s)=v=f_0(u)$；由 injective 性，$x+s=u$，即 $x=u-s$，也恰有一项。

因此测量后前两个寄存器坍缩到（已归一化）

$$\frac{|0,u⟩+|1,u-s⟩}{\sqrt{2}}.$$

此刻位移 $s$ 已经进入状态：它表现为两个分支中群寄存器的相对位移。但直接测量群寄存器只会均匀随机地得到 $u$ 或 $u-s$ 中的一个——$u$ 本身是均匀随机的，单个样本不含任何关于 $s$ 的信息。这正是 Simon 算法中我们熟悉的处境，而解法也一样：做 Fourier 变换，把“位移”变成“相位”。

第四步：对群寄存器做 Abelian QFT。回忆约定：有限 Abel 群 $G$ 的不可约特征标（character）由对偶群 $\hat{G}\cong G$ 中的标签 $y$ 索引，记为 ${\chi }_y$，满足同态性质 ${\chi }_y(a+b)={\chi }_y(a){\chi }_y(b)$，从而 ${\chi }_y(a-s)={\chi }_y(a){\chi }_y(-s)$。QFT 的作用约定为

$$|x⟩\mapsto \frac{1}{\sqrt{|G|}}\sum _{y\in \hat{G}}{\chi }_y(x)|y⟩.$$

把它作用到 $\frac{|0,u⟩+|1,u-s⟩}{\sqrt{2}}$ 的群寄存器上，线性性给出

$$\frac{1}{\sqrt{2|G|}}\sum _y({\chi }_y(u)|0⟩+{\chi }_y(u-s)|1⟩)|y⟩=\frac{1}{\sqrt{2|G|}}\sum _y{\chi }_y(u)(|0⟩+{\chi }_y(-s)|1⟩)|y⟩,$$

等号只用了特征标的同态性质：${\chi }_y(u-s)={\chi }_y(u){\chi }_y(-s)$。现在测量频率寄存器，得到标签 $y$ 的概率为

$${\left|\frac{{\chi }_y(u)}{\sqrt{2|G|}}\right|}^2\cdot \Vert |0⟩+{\chi }_y(-s)|1⟩{\Vert }^2=\frac{1}{2|G|}\cdot 2=\frac{1}{|G|},$$

因为 $|{\chi }_y(u)|=1$（特征标取值在单位圆上）。注意这个概率不依赖 $s$：$y$ 是均匀随机的，测量 $y$ 本身学不到任何位移信息。位移去了哪里？它在剩余选择位的相对相位里。测得 $y$ 后，选择位的条件态为

$$|{\varphi }_y(s)⟩=\frac{|0⟩+{\chi }_y(-s)|1⟩}{\sqrt{2}},$$

这里我们忽略了整体相位因子 ${\chi }_y(u)$——它只贡献全局相位，不影响任何后续测量。

小结一下这个推导的逻辑：测量函数值把两个移位输入 $u$ 与 $u-s$ 配成相干二项态（injective 性保证每个测量值恰对应一对）；QFT 把“群寄存器上的相对位移”翻译成“选择位上的相对相位”；而随机标签 $y$ 携带着唯一的未知数 ${\chi }_y(-s)$。问题的真正难点是：每次实验得到的 $y$ 是均匀随机的、不可控的，怎样从一系列随机特征 $y$ 的相位 ${\chi }_y(s)$ 恢复 $s$？下面第 3 节给出通用（但昂贵）的答案，第 4–5 节给出特殊函数的高效答案。

3. 与 generalized dihedral HSP 的等价关系

本节解释为什么隐藏平移问题“天生”是非交换的，以及通用算法能做什么。

广义二面体群。对有限 Abel 群 $G$（运算写作加法），定义半直积

$$\mathrm{Dih}(G)=G⋊{\mathbb{Z}}_2,$$

其元素为 $(x,b)$（$x\in G$，$b\in {\mathbb{Z}}_2$），乘法规则为

$$(x,b)(y,c)=(x+(-1{)}^{b}y,b+c),$$

即 ${\mathbb{Z}}_2$ 的非平凡元素作用在 $G$ 上是取逆 $x\mapsto -x$。当 $G={\mathbb{Z}}_N$ 时这就是通常的 $N$ 边形二面体群：$(x,0)$ 是旋转，$(x,1)$ 是反射。每个反射 $(t,1)$ 都是二阶元：$(t,1)(t,1)=(t-t,0)=(0,0)$。

从隐藏平移到二面体 HSP。把 $f_0,f_1$ 拼成 $\mathrm{Dih}(G)$ 上的单个函数：

$$F(x,0)=f_0(x),F(x,1)=f_1(x).$$

考察二阶子群 $K=\{(0,0),(-s,1)\}$ 的右陪集。由乘法规则，$(x,0)(-s,1)=(x-s,1)$，故含 $(x,0)$ 的右陪集是

$$\{(x,0),(x-s,1)\}.$$

$F$ 在这个陪集的两个元素上取值分别为 $f_0(x)$ 与 $f_1(x-s)=f_0(x-s+s)=f_0(x)$，相等。反过来，$f_0$ injective 时，不同陪集上的取值互不相同（$f_0$ 的值域与 $f_1$ 的值域相同，而每个值在每个分支中只出现一次，相等的两值必来自同一个陪集配对）。所以 $F$ 恰好是由反射 $(-s,1)$ 生成的二阶子群 $K$ 的隐藏函数（隐藏子群的符号约定使反射的参数与 $s$ 相差一个符号，这不影响问题实质：恢复 $K$ 即恢复 $s$）。第 2 节制备的相位态 $|{\varphi }_y(s)⟩$ 正是二面体 HSP 中标准的“二面体陪集态”经过表示论 Fourier 采样后的产物。

通用算法的代价。既然隐藏平移是二面体 HSP 的特例，所有针对二面体 HSP 的算法都直接适用。目前已知最好的通用结果是 Kuperberg 的筛法（sieve）：它对 $\mathrm{Dih}(G)$ 上的 HSP 给出

$$\exp (O(\sqrt{\log |G|}))$$

型的次指数算法（查询数与时间同阶）。逐项解释这个复杂度表达式的含义：

• 它以 $\log |G|$（即群寄存器的比特数 $n$）为参数，形如 $e^{O(\sqrt{n})}$；
• 它比任何多项式 $\mathrm{poly}(n)$ 都慢（因为 $\sqrt{n}$ 最终超过任何常数乘以 $\log n$），但又比任何指数 $e^{cn}$（$c>0$）都快——这正是“次指数”的含义；
• 与经典最优的 $\Theta (\sqrt{|G|})=e^{\frac{1}{2}n\ln 2}$（生日碰撞）相比，指数从 $O(n)$ 降到了 $O(\sqrt{n})$，是实质但仍然有限的改进。

Kuperberg 筛法的基本思想与第 2 节一脉相承：不断制备随机标签的相位态，然后设计一种“组合”操作，把两个相位态相干地合并成一个标签更“低”的新相位态，如此筛滤 $\sqrt{n}$ 层之后，得到一个几乎确定的标签，从中直接读出 $s$ 的一位。我们不在此展开筛法的组合细节；要点是它能做到次指数，完全得益于巧妙地利用随机标签，而不是消除它们。

反方向的归约。反过来，二面体 HSP 也可以写成两个 injective 函数的隐藏平移：给定二面体群上的隐藏函数 $F$（隐藏子群由某个反射生成），把 $F$ 限制在 $G\times \{0\}$ 与 $G\times \{1\}$ 两个分支上，适当重排后即可得到一对满足平移承诺的 injective 函数。因此两个问题在多项式时间归约意义下等价：对任意 injective hidden shift 有 Kuperberg 型次指数算法，而想对二面体 HSP（进而对图同构路线）取得多项式时间算法，就必须利用具体函数的额外结构——通用黑盒方法到此为止。

这就是本词条后半部分的动机：哪些函数拥有足够好的 Fourier 结构，能让相位被高效解码？答案是“谱平坦且谱相位可计算”的函数。下面两节各给一个典范。

4. ${\mathbb{Z}}_2^n$：相位直接成为线性方程

4.1 injective 情形：Simon 式线性代数

取 $G={\mathbb{Z}}_2^n$（$n$ 维 Boolean 向量群，运算为逐位异或）。它的特征标格外简单：对 $y\in {\mathbb{Z}}_2^n$，

$${\chi }_y(s)=(-1{)}^{y\cdot s},y\cdot s=\sum _{i=1}^n{y}_i{s}_i(\mathrm{mod}2).$$

（验证同态性质：$(-1{)}^{y\cdot (a+b)}=(-1{)}^{y\cdot a}(-1{)}^{y\cdot b}$，因为模 2 加法满足分配律。）代入第 2 节的相位态：

$$|{\varphi }_y(s)⟩=\frac{|0⟩+(-1{)}^{y\cdot s}|1⟩}{\sqrt{2}}.$$

这个态只依赖一个比特 $y\cdot s$：当 $y\cdot s=0$ 时它是 $|+⟩$，当 $y\cdot s=1$ 时它是 $|-⟩$。也就是说，$|{\varphi }_y(s)⟩$ 就是 Pauli $X$ 基下的基矢，本征值恰好是我们要的信息。于是只需对选择位做一次 Hadamard 变换再测量（即在 $X$ 基下测量），就确定性地得到比特

$$b=y\cdot s.$$

每次实验消耗一次查询，产生一个均匀随机的 $y\in {\mathbb{Z}}_2^n$ 和一个线性方程 $y\cdot s=b$。收集 $n$ 个线性无关的方程后用 ${\mathbb{F}}_2$ 上的高斯消元（$O(n^3)$ 经典时间）解出 $s$。需要采样多少次才能凑够 $n$ 个独立方程？$n$ 个均匀随机向量线性无关的概率是

$$\prod _{k=0}^{n-1}\left(1-\frac{2^k}{2^n}\right)=\prod _{j=1}^n\left(1-2^{-j}\right)>0.288,$$

一个与 $n$ 无关的正常数（无穷乘积 ${\prod }_{j\ge 1}(1-2^{-j})\approx 0.2888$）。因此期望 $O(1)$ 批、每批 $n$ 次采样即可，总查询数 $O(n)$。这与 Simon 算法完全同构——可以说这是 Simon 式线性代数的“两个函数版本”：Simon 问题中每次测量给出一个与 $s$ 正交的随机 $y$，这里每次测量给出 $s$ 在随机方向 $y$ 上的投影。

与经典下界对比：对一般 injective $f_0$，经典算法需要 $\Theta (2^{n/2})$ 次查询（生日碰撞），而量子只需 $O(n)$ 次——指数级分离。

4.2 障碍：Boolean 值函数不可能 injective

上节假设 $f_0$ injective。但在密码学与布尔函数分析中，最自然的情形是 $f:{\mathbb{Z}}_2^n\to \{0,1\}$——值域只有两个元素，而定义域有 $2^n$ 个元素，injective 根本不可能。第 2 节的“测量函数值配成一对”论证随之失效：测量函数值 $0$ 会留下所有满足 $f_0(x)=0$ 或 $f_1(x^{\prime })=0$ 的项的叠加，不是一个二项态。

出路是换一个“值域”：不看比特值 $f(x)$，而看相位值

$$F(x)=(-1{)}^{f(x)}\in \{+1,-1\}.$$

作为相位 oracle，$F$ 总是可以相干地写入（对目标位置加再测量，或用标准相位回传）。现在的核心问题是：$F$ 的 Fourier 谱长什么样？如果谱足够“平”，第 2 节的逻辑就能绕过测量函数值这一步，直接在相位层面工作。

4.3 bent 函数：最平坦的 Boolean 谱

采用如下归一化的 Walsh–Hadamard 变换：对 $F:{\mathbb{Z}}_2^n\to \mathbb{R}$，

$$\hat{F}(y)=\frac{1}{2^n}\sum _{x\in {\mathbb{Z}}_2^n}F(x)(-1{)}^{x\cdot y}.$$

（这是把 $\hat{F}(y)$ 定义为“$F$ 与特征标 ${\chi }_y$ 的相关系数”的约定；Parseval 恒等式表现为 ${\sum }_y|\hat{F}(y){|}^2=\frac{1}{2^n}{\sum }_x|F(x){|}^2$。）当 $F(x)=(-1{)}^{f(x)}$ 时 $|F(x)|=1$，Parseval 给出

$$\sum _y|\hat{F}(y){|}^2=1.$$

即 $2^n$ 个谱系数的模方总和为 $1$。一个自然的问题：这 $2^n$ 个系数能“摊”得多平？最平的情形是每个 $|\hat{F}(y){|}^2$ 都相等，即

$$|\hat{F}(y)|=2^{-n/2},\forall y.$$

定义（bent 函数）。若 Boolean 函数 $f$ 的相位函数 $F(x)=(-1{)}^{f(x)}$ 满足上式，即所有 Walsh 系数模相等，则称 $f$ 为 bent 函数。此时每个谱系数只差一个符号，可以写成

$$\hat{F}(y)=2^{-n/2}(-1{)}^{\tilde{f}(y)},$$

其中 $\tilde{f}:{\mathbb{Z}}_2^n\to \{0,1\}$ 称为 $f$ 的对偶（dual）bent 函数（可以证明它自己也是 bent 函数）。注意 $\hat{F}(y)\cdot 2^n={\sum }_x(-1{)}^{f(x)+x\cdot y}$ 必为整数，而模为 $2^{-n/2}$ 的要求等价于该整数等于 $\pm 2^{n/2}$；$2^{n/2}$ 为整数当且仅当 $n$ 为偶数，因此 bent 函数只可能存在于 $n$ 为偶数的情形。bent 函数恰恰是与所有线性函数“距离最远”的 Boolean 函数——这也是它在对称密码学中重要的原因。

关键性质：平移在谱上只添一个线性相位。设承诺的移位函数为

$$G(x)=F(x+s)$$

（${\mathbb{Z}}_2^n$ 中加法即异或，$x+s$ 也就是 $x\oplus s$）。计算其 Walsh 变换，每一步如下：

$$\hat{G}(y)=\frac{1}{2^n}\sum _{x}F(x+s)(-1{)}^{x\cdot y}=\frac{1}{2^n}\sum _{z}F(z)(-1{)}^{(z+s)\cdot y}=(-1{)}^{s\cdot y}\frac{1}{2^n}\sum _{z}F(z)(-1{)}^{z\cdot y}=(-1{)}^{y\cdot s}\hat{F}(y).$$

第一步是定义；第二步做换元 $z=x+s$（当 $x$ 遍历 ${\mathbb{Z}}_2^n$ 时 $z$ 也遍历整个群，这是有限群平移求和不变性）；第三步把 $(-1{)}^{(z+s)\cdot y}$ 按分配律拆成 $(-1{)}^{z\cdot y}(-1{)}^{s\cdot y}$ 并把不含 $z$ 的因子提出求和号；第四步认出剩余求和正是 $\hat{F}(y)$。这就是 ${\mathbb{Z}}_2^n$ 上的 Fourier 平移定理：时域平移 $s$ 等价于频域乘以线性相位 $(-1{)}^{y\cdot s}$。

4.4 bent 函数隐藏平移的量子算法

现在把上面的零件装成算法。承诺：oracle 给出移位函数 $f_s(x)=f(x+s)$，其中 $f$ 是我们已知的 bent 函数（因此也能计算其对偶 $\tilde{f}$——对标准构造如 Maiorana–McFarland 类，$\tilde{f}$ 是高效可计算的），$s$ 未知。算法四步：

1. 写入相位。在均匀叠加 $\frac{1}{2^{n/2}}{\sum }_x|x⟩$ 上调用一次相位 oracle，制备

$$\frac{1}{2^{n/2}}\sum _x(-1{)}^{f(x+s)}|x⟩=\frac{1}{2^{n/2}}\sum _{x}G(x)|x⟩.$$

2. Hadamard 变换到频域。对全部 $n$ 个量子比特做 $H^{\otimes n}$。由 $H^{\otimes n}|x⟩=\frac{1}{2^{n/2}}{\sum }_y(-1{)}^{x\cdot y}|y⟩$ 及线性性，$y$ 的振幅为

$$\frac{1}{2^n}\sum _{x}G(x)(-1{)}^{x\cdot y}=\hat{G}(y)=(-1{)}^{y\cdot s}\hat{F}(y)=2^{-n/2}(-1{)}^{y\cdot s+\tilde{f}(y)},$$

依次用了上一步的态、平移定理、bent 平坦性。态即

$$\frac{1}{2^{n/2}}\sum _y(-1{)}^{y\cdot s}(-1{)}^{\tilde{f}(y)}|y⟩.$$

3. 相干消去已知的 Fourier 符号。因为 $\tilde{f}$ 可计算，存在高效经典电路计算 $\tilde{f}(y)$；用标准相位回传对它作用，给每个 $|y⟩$ 乘上 $(-1{)}^{\tilde{f}(y)}$，与原有符号相消（$(-1{)}^{2\tilde{f}(y)}=1$）。态变为

$$\frac{1}{2^{n/2}}\sum _y(-1{)}^{y\cdot s}|y⟩.$$

4. 逆 Hadamard 变换聚焦。注意上式正是 $H^{\otimes n}|s⟩$（把定义式中 $x$ 换成 $s$ 即见）。故再做一次 $H^{\otimes n}$（它自逆）得到

$$|s⟩.$$

测量即确定性地得到 $s$。全程只用一次 oracle 查询加 $O(n)$ 个门（外加计算 $\tilde{f}$ 的经典电路）。这个算法应理解为 bent 版本的 Bernstein–Vazirani：正是谱的完全平坦性保证第 2 步后每个 $y$ 的振幅非零且模相等，第 3 步的相位校正才能“一次性”剥掉函数信息，只留下位移的线性相位。

4.5 一般 Boolean 函数：influence 控制的算法与保留条款

对任意 Boolean 函数，Fourier 谱不再平坦，上述“一次性相位校正”失效。Gavinsky–Rötteler–Roland 对一般的 Boolean hidden shift 问题给出了一个算法，其复杂度由函数 $f$ 的最小 influence 控制。这里 influence 指 Boolean 分析中的标准量：第 $i$ 个变量的 influence 为 ${\mathrm{Inf}}_i[f]={\mathrm{Pr}}_x[f(x)\ne f(x\oplus e_i)]$，即随机输入下翻转第 $i$ 位会改变函数值的概率；它度量函数值对各个输入位的“敏感程度”。直觉上，influence 越大，$f$ 的 Fourier 质量越不容易集中在低频或少数系数上，谱越接近平坦，算法每一步能提取的信息就越多。

需要完整保留并强调原文的两个保留条款：

• 这是平均情形、而非最坏情形的结果。随机 Boolean 函数通常有足够大的 influence，因此该算法对随机函数给出平均情形多项式时间，并与经典的指数查询下界形成分离；但对最坏情形的函数（例如 influence 很小的函数，如只依赖少数输入位的 dictator 型函数），算法不因此自动高效。
• 谱平坦性是关键资源，而非“存在位移”本身。bent 情形的成功依赖“所有 Walsh 系数模相等”这一极强的结构假设；只知道 $f_1$ 是 $f_0$ 的移位，不提供任何可解码性保证。

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

第二个典范来自数论。它在概念上与 bent 情形完全平行：特殊函数的 Fourier 谱模平坦、相位可由已知量表达，区别只是群从 ${\mathbb{Z}}_2^n$ 换成 ${\mathbb{F}}_p$ 的加法群。

5.1 问题设定与经典难度

设 $p$ 为奇素数，${\mathbb{F}}_p$ 为 $p$ 元有限域。Legendre 符号（二次乘法特征）$\chi :{\mathbb{F}}_p\to \{-1,0,+1\}$ 定义为

$$\chi (x)=x^{(p-1)/2}\mathrm{mod}p=\{\begin{array}{ll}0,& x=0,\\ +1,& x\text{ 是模 }p\text{ 的二次剩余},\\ -1,& x\text{ 是模 }p\text{ 的二次非剩余}.\end{array}$$

等号成立由 Euler 判别法给出；乘法性 $\chi (xy)=\chi (x)\chi (y)$ 可直接验证。移位 Legendre 符号问题：oracle 给出

$$f_s(x)=\chi (x+s),x\in {\mathbb{F}}_p,$$

求未知的 $s\in {\mathbb{F}}_p$。van Dam–Hallgren–Ip 研究这个问题的动机部分来自密码学：移位 Legendre 序列曾被提议作为抗量子的伪随机构造候选。经典上，没有关于 $\log p$ 多项式的已知算法：对随机位置查询，函数值看起来像随机符号串，通用策略退化为生日式碰撞搜索，需要关于 $p$ 本身（而非 $\log p$）多项式量级的查询。而下面将看到量子算法只需常数次查询加 $\mathrm{poly}(\log p)$ 的计算。这个超多项式优势完全来自二次特征的特定代数结构，而不是任意移位函数都具有的性质。

5.2 Legendre 符号的 Fourier 谱：Gauss 和

取加法特征 $\psi (z)=e^{2\pi iz/p}$，并采用酉归一化的加法 Fourier 变换

$$\hat{g}(y)=\frac{1}{\sqrt{p}}\sum _{x\in {\mathbb{F}}_p}g(x)\psi (xy).$$

Fourier 平移定理（与 4.3 节的证明逐行平行）：对 $f_s(x)=\chi (x+s)$，

$${\hat{f}}_s(y)=\frac{1}{\sqrt{p}}\sum _x\chi (x+s)\psi (xy)=\frac{1}{\sqrt{p}}\sum _z\chi (z)\psi ((z-s)y)=\psi (-sy)\hat{\chi }(y),$$

第二步换元 $z=x+s$，第三步把 $\psi (zy-sy)=\psi (zy)\psi (-sy)$ 拆开并提出与 $z$ 无关的因子（用了 $\psi$ 的同态性 $\psi (a+b)=\psi (a)\psi (b)$）。

接下来是关键的数论事实。Gauss 和为

$$\tau :=\sum _{x\in {\mathbb{F}}_p}\chi (x)\psi (x),$$

经典结果给出 $|\tau |=\sqrt{p}$，且 $\tau /\sqrt{p}$ 是一个完全已知的相位（等于 $1$ 或 $i$，取决于 $p\mathrm{mod}4$）。用 Gauss 和的标准计算，对 $y\ne 0$：

$$\hat{\chi }(y)=\frac{1}{\sqrt{p}}\sum _x\chi (x)\psi (xy)\stackrel{(a)}{=}\frac{\chi (y)}{\sqrt{p}}\sum _x\chi (xy)\psi (xy)\stackrel{(b)}{=}\frac{\chi (y)}{\sqrt{p}}\tau ,$$

其中 (a) 处乘上 $\chi (y{)}^2=1$（$y\ne 0$ 时 $\chi (y)=\pm 1$，并用乘法性 $\chi (y)\chi (x)=\chi (xy)$）；(b) 处换元 $x^{\prime }=xy$（$x$ 遍历 ${\mathbb{F}}_p$ 时 $x^{\prime }$ 亦遍历）。于是对一切非零频率 $y$，

$$|\hat{\chi }(y)|=\frac{|\chi (y)|\cdot \sqrt{p}}{\sqrt{p}}=1,$$

即 Legendre 符号的加法谱在所有非零频率上模平坦，其相位分解成“可计算的部分”$\chi (y)$（$y$ 的 Legendre 符号，经典上 $O({\log }^{3}p)$ 内可算）乘以“已知的固定常数”$\tau /\sqrt{p}$。而 $y=0$ 处 $\hat{\chi }(0)=\frac{1}{\sqrt{p}}{\sum }_x\chi (x)=0$（二次剩余与非剩余各半，相互抵消）。

5.3 量子算法

对照 bent 情形的四步，Legendre 情形的算法是：

1. 将 $f_s(x)$ 写入相位，制备移位特征态。在均匀叠加 $\frac{1}{\sqrt{p}}{\sum }_x|x⟩$ 上调用 oracle 并以标准技巧（先把 $\chi (x+s)\in \{-1,0,+1\}$ 算入辅助寄存器，再施加相应相位，最后反算）给每个 $|x⟩$ 乘上 $\chi (x+s)$。理想态为

$$\frac{1}{\sqrt{p}}\sum _x\chi (x+s)|x⟩.$$

这里有一个技术细节：$x=-s$ 处 $\chi (0)=0$，该基矢的振幅缺失（无法通过任何酉相位操作制造一个零振幅项的同时保持其余项为 $\pm 1$；实际实现中这一位只能任给一个相位或留空）。我们把它当作对理想态的一个小扰动，误差分析见下。 2. 做加法 QFT（${\mathbb{F}}_p$ 上的 $|x⟩\mapsto \frac{1}{\sqrt{p}}{\sum }_y\psi (xy)|y⟩$）。由平移定理，频域态为

$$\sum _y\psi (-sy)\hat{\chi }(y)|y⟩=\frac{\tau }{\sqrt{p}}\sum _{y\ne 0}\psi (-sy)\chi (y)|y⟩,$$

等号代入了 5.2 节的谱公式（$y=0$ 项因 $\hat{\chi }(0)=0$ 自动消失）。 3. 相干消去已知的 $\hat{\chi }(y)$ 相位。分两部分：整体常数 $\tau /\sqrt{p}$ 是已知固定相位，直接以单比特相位门消去；$\chi (y)$ 部分用相位回传——相干地计算 $y$ 的 Legendre 符号（Euler 判别法即模幂运算，$\mathrm{poly}(\log p)$ 个门）并施加相应相位，与态中原有的 $\chi (y)$ 相消。剩余态为

$$\frac{1}{\sqrt{p-1}}\sum _{y\ne 0}\psi (-sy)|y⟩\approx \frac{1}{\sqrt{p}}\sum _y\psi (-sy)|y⟩,$$

后者正是 $\mathrm{QFT}|-s⟩$（前者与后者的差别只是缺 $y=0$ 一项，权重 $1/p$）。 4. 逆 QFT，将线性相位聚焦到 $|-s⟩$。测量得到 $-s$，即得 $s$。

误差分析：单个零值为何只造成 $O(1/p)$ 误差。两处“缺失振幅”——第 1 步 $x=-s$ 的基矢与第 3 步 $y=0$ 的基矢——每一个在均匀叠加中的模方权重都恰为 $1/p$。把理想态记为 $|\Psi ⟩$、实际制备的态记为 $|{\Psi }^{\prime }⟩$，则两者相差至多两个模方各为 $1/p$ 的分量；不把缺失项重新归一化（等价于把它视为以概率 $1/p$ 发生的“制备失败”），则任何最终测量的成功概率从理想值 $c$ 至多下降到 $(1-O(1/p))c\ge c-O(1/p)$。理想的第 4 步以常数概率（事实上接近 $1$）输出 $-s$，故实际算法仍以常数成功率工作；重复 $O(1)$ 次即可放大。

复杂度总账。oracle 查询 $O(1)$ 次；QFT over ${\mathbb{F}}_p$ 用 $O({\log }^{2}p)$ 个基本门；第 3 步的 Legendre 符号相干计算为 $\mathrm{poly}(\log p)$。总量子运行时间 $\mathrm{poly}(\log p)$，而经典上没有已知的 $\log p$ 多项式算法，故相对于输入规模 $\log p$ 这是超多项式加速。再次强调保留条款：这个超多项式优势来自二次特征的特定结构——乘法性把谱相位锁定为 $\chi (y)$、Gauss 和把谱模锁定为常数——而不是任意移位函数都能享受的待遇。

6. Hidden coset 与非线性推广

回到非 injective 的一般情形。第 1 节已经看到，此时 $s$ 只确定到陪集 $s+H$。把“恢复稳定子”与“恢复位移”合成一个问题，就得到 hidden coset 问题：给定 $f_0,f_1:G\to S$，承诺存在 $s$ 使 $f_1(x)=f_0(x+s)$，要求同时输出 $f_0$ 的稳定子 $H$ 与陪集 $s+H$。它统一了两个经典问题：

• 令 $f_0=f_1$（承诺以 $s=0$ 平凡成立），任务退化为求 $H$——即隐藏子群问题；
• 令 $H=\{0\}$（$f_0$ injective），任务退化为求唯一的 $s$——即唯一隐藏平移问题。

Friedl、Ivanyos、Magniez、Santha 与 Sen 提出了 translating coset（平移陪集）框架，把 hidden coset 推广到非交换群：给定群 $G$ 作用于某集合，两个“轨道函数”相差一个未知群元素的作用，要求恢复该元素（确定到稳定子陪集）。他们用群作用的结构与递归的正规列（把大群沿子群链逐层降解）处理了若干可解群族。这条线的意义在于：它说明“先求对称（稳定子）、再求位移（陪集代表）”的两阶段策略在相当一般的非交换情形下仍然可行，而真正的瓶颈始终是第 2 节那个问题——随机标签上的相位如何解码。

除正文详述的两类外，还有一批高效或次指数结果，各自依赖不同的谱结构：

• 二次型与高 Gowers 范数：${\mathbb{Z}}_2^n$ 上的移位二次型可高效求解；更一般地，谱由低次相位主导（Gowers 范数大）的函数允许类似的相位校正；
• weighing matrices 与 Abel 差集：这两类组合设计对应的函数具有“两级”或平坦的谱，可用与 bent/Legendre 相同的精神处理；
• 随机线性 disequation 与从子集样本学习线性函数：把隐藏平移思想推广到“方程以噪声或子集方式给出”的学习问题，仍有高效或次指数算法。

它们共享同一个模式：先证明目标函数的 Fourier 质量集中在一个可解码的集合上（平坦谱、低次谱、稀疏谱等），再设计相应的相位校正或滤波步骤；只知道“存在位移”这一承诺本身通常不够。这也是第 3 节次指数通用算法与本节多项式特殊算法之间的真正分界。

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

把第 2 节的推导在一个能完全手算的例子里过一遍。令 $G={\mathbb{Z}}_8$，$f_0$ 返回八个互异标签（比如 $f_0(x)=x$ 本身，这保证 injective），并承诺 $f_1(x)=f_0(x+3)$，即 $s=3$——算法不知道这个数。

配成二项态。制备

$$\frac{1}{4}\sum _{x=0}^7(|0⟩|x⟩|f_0(x)⟩+|1⟩|x⟩|f_1(x)⟩)$$

（$\frac{1}{\sqrt{2\cdot 8}}=\frac{1}{4}$）。设测量函数值得到 $v=f_0(u)$ 的某个值，比如 $u=5$。则选择位为 $0$ 的存活项要求 $x=5$；选择位为 $1$ 的存活项要求 $f_0(x+3)=f_0(5)$，由 injective 性 $x+3=5$，即 $x=2=u-s$（模 8）。测量后状态为

$$\frac{|0,5⟩+|1,2⟩}{\sqrt{2}}=\frac{|0,u⟩+|1,u-3⟩}{\sqrt{2}}.$$

QFT 与相位。${\mathbb{Z}}_8$ 的特征标为 ${\chi }_y(x)=e^{2\pi ixy/8}$，QFT 为 $|x⟩\mapsto \frac{1}{\sqrt{8}}{\sum }_{y=0}^7{e}^{2\pi ixy/8}|y⟩$。作用后 $y$ 频率处的（未归一化）振幅为

$${\chi }_y(u)|0⟩+{\chi }_y(u-3)|1⟩={\chi }_y(u)(|0⟩+{\chi }_y(-3)|1⟩).$$

每个 $y$ 被测得的概率都是 $1/8$——再次确认测量 $y$ 本身不含 $s$ 的信息。选择位的相对相位 ${\chi }_y(-3)=e^{-2\pi i\cdot 3y/8}$ 随随机标签 $y$ 变化：

$y$	相对相位 $e^{-2\pi i\cdot 3y/8}$	值
0	$e^0$	$1$
1	$e^{-3\pi i/4}$	$-\frac{\sqrt{2}}{2}(1+i)$
2	$e^{-3\pi i/2}$	$i$
3	$e^{-9\pi i/4}=e^{-\pi i/4}$	$\frac{\sqrt{2}}{2}(1-i)$
4	$e^{-3\pi i}=e^{-\pi i}$	$-1$

例如 $y=2$ 时，选择位状态为（忽略全局相位 ${\chi }_2(5)$）

$$\frac{|0⟩+i|1⟩}{\sqrt{2}},$$

相对相位 $i=e^{-2\pi i(2)(3)/8}$：指数里 $2\times 3=6$，直接算得 $e^{-2\pi i\cdot 6/8}=e^{-3\pi i/2}=\cos \frac{3\pi }{2}-i\sin \frac{3\pi }{2}=0-i\cdot (-1)=i$，与表中一致。

读出 $s$ 的两种情形。这个例子正好横跨本词条的两类方法：

• 若把 ${\mathbb{Z}}_8$ 当作一般的循环群处理，单个相位态无法直接读出 $s$：$y$ 均匀随机，每次实验只给出 $e^{-2\pi i\cdot 3y/8}$ 中“$3y\mathrm{mod}8$”这一混杂信息。通用二面体筛法（Kuperberg）负责的正是把大量这样的随机标签相干地组合，筛出易读的频率，复杂度 $\exp (O(\sqrt{\log 8}))$ 型（当然 $n=3$ 时“渐近”没有意义，这里只示意方法归属）。
• 若群是 ${\mathbb{Z}}_2^n$（比如把问题改写到 ${\mathbb{Z}}_2^3$ 上），则特征标只取 $\pm 1$，上表的相对相位列只剩两个值 $+1$ 与 $-1$，每份相位态已经直接给出一位线性信息 $y\cdot s$：$O(n)$ 份之后高斯消元即得 $s$。

这个对照就是全课的缩影：相位永远在那里，差别只在于它是否落在一个我们能逐位解码的集合上。

8. 小结与习题

小结。

• 测量函数值把两个移位输入配成相干二项态 $\frac{|0,u⟩+|1,u-s⟩}{\sqrt{2}}$；injective 性保证每个测量值恰对应一对。
• QFT 后位移成为随机特征上的相对相位 ${\chi }_y(-s)$；$y$ 均匀分布且不含 $s$ 的信息，全部困难在于解码随机相位。
• injective hidden shift 等价于 generalized dihedral HSP；通用算法（Kuperberg 筛法）为次指数 $\exp (O(\sqrt{\log |G|}))$，经典最优为 $\Theta (\sqrt{|G|})$。
• ${\mathbb{Z}}_2^n$ 上相位即线性方程，injective 情形 $O(n)$ 次查询解出 $s$；bent 函数与二次特征的平坦 Fourier 谱允许一次性相位校正，把查询复杂度降到 $O(1)$ 并高效恢复位移。
• 谱平坦性（或更一般的谱集中性）是高效性的真正来源；“存在位移”的承诺本身不保证可解码。

习题。

1. 按本词条的 QFT 约定 $|x⟩\mapsto \frac{1}{\sqrt{|G|}}{\sum }_y{\chi }_y(x)|y⟩$，逐步推导第 2 节 $|{\varphi }_y(s)⟩$ 中相对相位是 ${\chi }_y(-s)$ 而非 ${\chi }_y(s)$，并说明若改用共轭约定的 QFT，结论应如何改写。
2. 补全 Lemma 1 中未写出的一步：证明若 $f_0$ 的稳定子 $H$ 非平凡，则对任意满足承诺的 $s$，陪集 $s+H$ 中不同元素作为“答案”在黑盒模型下不可区分（即：对任意 $h\in H$，把 $s$ 换成 $s+h$ 后两个 oracle 完全不变）。
3. 模仿 4.3 节的换元论证，在一般有限 Abel 群 $G$ 上证明 Fourier 平移定理：若 $f_s(x)=f_0(x+s)$，则 ${\hat{f}}_s(y)={\chi }_y(-s){\hat{f}}_0(y)$，并指出证明中用到特征标同态性质的具体步骤。
4. 在 4.1 节中，证明 $n$ 个独立均匀随机向量 $y_1,\dots ,y_n\in {\mathbb{F}}_2^n$ 线性无关的概率等于 ${\prod }_{j=1}^n(1-2^{-j})$，并由此说明为何期望 $O(n)$ 次采样即可恢复 $s$。（提示：逐个加入向量，计算第 $k+1$ 个向量落入前 $k$ 个张成的 $2^k$ 维子空间的概率。）
5. 解释 Legendre oracle 的单个零值（$x=-s$ 处的缺失振幅）为何只造成 $O(1/p)$ 的成功概率损失；进一步说明若改为“把缺失项重新归一化”，实际态与理想态的内积平方为 $1-1/p$，结论为何不变。
6. 验证 bent 函数定义中的 Parseval 恒等式 ${\sum }_y|\hat{F}(y){|}^2=1$（按 4.3 节的归一化），并据此说明“所有 Walsh 系数模相等”强制 $|\hat{F}(y)|=2^{-n/2}$；结合 $\hat{F}(y)\cdot 2^{n/2}$ 必为整数这一观察，解释 bent 函数为何只可能存在于 $n$ 为偶数的情形。

参考文献与 Zoo 覆盖

• 框架与二面体联系：Zoo 43、66、143、312，见 Friedl 等、Kuperberg 与 Rötteler。
• 二次特征与有限域平移：Zoo 86、88、89，核心综述论文为 van Dam—Hallgren—Ip。
• Boolean、quadratic 与高阶 Fourier 结构：Zoo 105、130、142，见 Boolean Hidden Shift。
• 线性 disequation 与子集学习推广：Zoo 407、408，见 Ivanyos—Prakash—Santha 与 Ivanyos。

---

参考资料

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