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

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

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

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

:::{admonition} 本课知识点
:class: tip

1. **[问题背景与经典复杂度](#hidden-shift-motivation)**——能写出隐藏平移问题的承诺条件，说明它与“求对称”的周期问题在提问方式上互为对偶，并解释经典碰撞算法为何需要 $\Theta(\sqrt{|G|})$ 次查询。
2. **[定义、稳定子与陪集不确定性](#hidden-shift-definition)**——能写出稳定子 $H$ 的定义并验证它是子群，证明合法解集恰为陪集 $s + H$。
3. **[相位态的四步推导](#phase-state-derivation)**——能逐步推导一次查询加 QFT 后选择位的条件态 $|\phi_y(s)\rangle$，并解释 $y$ 为何均匀随机且不含位移信息。
4. **[二面体 HSP 等价与次指数筛法](#dihedral-hsp-equivalence)**——能把两个函数拼成广义二面体群上的隐藏函数，并比较 Kuperberg 筛法与经典碰撞下界的查询复杂度。
5. **[Simon 式线性代数解法](#simon-linear-algebra)**——能计算 $\mathbb Z_2^n$ 上相位态给出的线性方程 $y \cdot s = b$，并解释 $O(n)$ 次采样加高斯消元为何足以恢复 $s$。
6. **[bent 函数隐藏平移算法](#bent-function-algorithm)**——能用 Fourier 平移定理与 bent 谱的模平坦性推导四步算法，并证明单次 oracle 查询即可恢复 $s$。
7. **[移位 Legendre 符号量子算法](#legendre-shift-algorithm)**——能用 Gauss 和证明 Legendre 符号的加法谱在非零频率模平坦，并解释相位回传算法为何以常数次查询恢复 $s$。
8. **[循环数组手算例子](#z8-worked-example)**——能在 $G = \mathbb Z_8$、$s = 3$ 的例子中手算二项态与各频率相对相位，并比较 $\mathbb Z_2^n$ 与一般循环群的两种读出方式。

:::

(hidden-shift-motivation)=
## 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')$，若出现 $f_0(x)=f_1(x')$ 则 $s = x - x'$。由生日悖论，需要 $\Theta(\sqrt{|G|})$ 次查询才能以可观概率碰到一次碰撞，而且在黑盒模型下这是最优的。也就是说，经典查询复杂度关于 $\log|G|$ 是指数的。本课将看到：量子算法对一般情形能达到次指数 $\exp(O(\sqrt{\log|G|}))$，对具有平坦 Fourier 谱的特殊函数能达到多项式。

(hidden-shift-definition)=
## 1. 定义、唯一性与稳定子

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

$$
f_1(x) = f_0(x + s), \qquad \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\bigl(x + (s + h)\bigr) = f_0\bigl((x + s) + h\bigr) = f_0(x + s) = f_1(x),
$$
其中第二个等号用了稳定子的定义（把 $x + s$ 看作定义中的“$x$”），第三个等号用了承诺条件。所以 $s + h$ 也是合法解。
- 必要性：设 $s$ 与 $s'$ 都满足承诺。则对任意 $x$，
$$
f_0(x + s) = f_1(x) = f_0(x + s').
$$
令 $h = s' - s$，并把 $x$ 替换为 $x - s$（$x$ 遍历 $G$ 时 $x - s$ 也遍历 $G$），得 $f_0(x) = f_0(x + h)$ 对所有 $x$ 成立，即 $h \in H$，故 $s' = 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 节讨论。

(phase-state-derivation)=
## 2. 一次查询如何产生带位移相位的态

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

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

$$
\frac{1}{\sqrt{2|G|}}\sum_{x \in G}\bigl(|0\rangle|x\rangle + |1\rangle|x\rangle\bigr)|0\rangle.
$$

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

$$
\frac{1}{\sqrt{2|G|}}\sum_{x \in G}\Bigl(|0\rangle|x\rangle|f_0(x)\rangle + |1\rangle|x\rangle|f_1(x)\rangle\Bigr).
$$

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

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

- 选择位为 $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\rangle + |1, u - s\rangle}{\sqrt 2}.
$$

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

**第四步：对群寄存器做 Abelian QFT**。回忆约定：有限 Abel 群 $G$ 的不可约特征标（character）由对偶群 $\widehat 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\rangle \mapsto \frac{1}{\sqrt{|G|}}\sum_{y \in \widehat G} \chi_y(x)\,|y\rangle.
$$

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

$$
\frac{1}{\sqrt{2|G|}}\sum_{y}\Bigl(\chi_y(u)|0\rangle + \chi_y(u - s)|1\rangle\Bigr)|y\rangle
= \frac{1}{\sqrt{2|G|}}\sum_{y}\chi_y(u)\Bigl(|0\rangle + \chi_y(-s)|1\rangle\Bigr)|y\rangle,
$$

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

$$
\left|\frac{\chi_y(u)}{\sqrt{2|G|}}\right|^2 \cdot \bigl\||0\rangle + \chi_y(-s)|1\rangle\bigr\|^2
= \frac{1}{2|G|} \cdot 2 = \frac{1}{|G|},
$$

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

$$
|\phi_y(s)\rangle = \frac{|0\rangle + \chi_y(-s)|1\rangle}{\sqrt 2},
$$

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

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

(dihedral-hsp-equivalence)=
## 3. 与 generalized dihedral HSP 的等价关系

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

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

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

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

$$
(x, b)(y, c) = \bigl(x + (-1)^b y,\ b + c \bigr),
$$

即 $\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$ 拼成 $\operatorname{Dih}(G)$ 上的单个函数：

$$
F(x, 0) = f_0(x), \qquad 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 节制备的相位态 $|\phi_y(s)\rangle$ 正是二面体 HSP 中标准的“二面体陪集态”经过表示论 Fourier 采样后的产物。

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

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

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

- 它以 $\log|G|$（即群寄存器的比特数 $n$）为参数，形如 $e^{O(\sqrt n)}$；
- 它比任何多项式 $\operatorname{poly}(n)$ 都慢（因为 $\sqrt n$ 最终超过任何常数乘以 $\log n$），但又比任何指数 $e^{cn}$（$c > 0$）都快——这正是“次指数”的含义；
- 与经典最优的 $\Theta(\sqrt{|G|}) = e^{\frac12 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$：相位直接成为线性方程

(simon-linear-algebra)=
### 4.1 injective 情形：Simon 式线性代数

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

$$
\chi_y(s) = (-1)^{y \cdot s}, \qquad y \cdot s = \sum_{i=1}^n y_i s_i \pmod 2.
$$

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

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

这个态只依赖一个比特 $y \cdot s$：当 $y \cdot s = 0$ 时它是 $|+\rangle$，当 $y \cdot s = 1$ 时它是 $|-\rangle$。也就是说，$|\phi_y(s)\rangle$ 就是 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\ge1}(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') = 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$，

$$
\widehat F(y) = \frac{1}{2^n}\sum_{x \in \mathbb Z_2^n} F(x)(-1)^{x \cdot y}.
$$

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

$$
\sum_{y} \bigl|\widehat F(y)\bigr|^2 = 1.
$$

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

$$
\bigl|\widehat F(y)\bigr| = 2^{-n/2}, \qquad \forall y.
$$

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

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

其中 $\widetilde f : \mathbb Z_2^n \to \{0,1\}$ 称为 $f$ 的**对偶（dual）bent 函数**（可以证明它自己也是 bent 函数）。注意 $\widehat 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 变换，每一步如下：

$$
\widehat 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}\,\widehat 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$ 的因子提出求和号；第四步认出剩余求和正是 $\widehat F(y)$。这就是 $\mathbb Z_2^n$ 上的 **Fourier 平移定理**：时域平移 $s$ 等价于频域乘以线性相位 $(-1)^{y \cdot s}$。

(bent-function-algorithm)=
### 4.4 bent 函数隐藏平移的量子算法

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

1. **写入相位**。在均匀叠加 $\frac{1}{2^{n/2}}\sum_x |x\rangle$ 上调用一次相位 oracle，制备
$$
\frac{1}{2^{n/2}}\sum_x (-1)^{f(x+s)}|x\rangle = \frac{1}{2^{n/2}}\sum_x G(x)|x\rangle.
$$
2. **Hadamard 变换到频域**。对全部 $n$ 个量子比特做 $H^{\otimes n}$。由 $H^{\otimes n}|x\rangle = \frac{1}{2^{n/2}}\sum_y (-1)^{x\cdot y}|y\rangle$ 及线性性，$y$ 的振幅为
$$
\frac{1}{2^n}\sum_x G(x)(-1)^{x\cdot y} = \widehat G(y) = (-1)^{y\cdot s}\widehat F(y) = 2^{-n/2}(-1)^{y\cdot s + \widetilde f(y)},
$$
依次用了上一步的态、平移定理、bent 平坦性。态即
$$
\frac{1}{2^{n/2}}\sum_y (-1)^{y \cdot s}\,(-1)^{\widetilde f(y)}|y\rangle.
$$
3. **相干消去已知的 Fourier 符号**。因为 $\widetilde f$ 可计算，存在高效经典电路计算 $\widetilde f(y)$；用标准相位回传对它作用，给每个 $|y\rangle$ 乘上 $(-1)^{\widetilde f(y)}$，与原有符号相消（$(-1)^{2\widetilde f(y)} = 1$）。态变为
$$
\frac{1}{2^{n/2}}\sum_y (-1)^{y \cdot s}|y\rangle.
$$
4. **逆 Hadamard 变换聚焦**。注意上式正是 $H^{\otimes n}|s\rangle$（把定义式中 $x$ 换成 $s$ 即见）。故再做一次 $H^{\otimes n}$（它自逆）得到
$$
|s\rangle.
$$

测量即**确定性地**得到 $s$。全程只用一次 oracle 查询加 $O(n)$ 个门（外加计算 $\widetilde 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 为 $\operatorname{Inf}_i[f] = \Pr_x[f(x) \neq 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} \bmod p =
\begin{cases}
0, & x = 0,\\
+1, & x \text{ 是模 } p \text{ 的二次剩余},\\
-1, & x \text{ 是模 } p \text{ 的二次非剩余}.
\end{cases}
$$

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

$$
f_s(x) = \chi(x + s), \qquad x \in \mathbb F_p,
$$

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

### 5.2 Legendre 符号的 Fourier 谱：Gauss 和

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

$$
\widehat 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)$，

$$
\widehat f_s(y) = \frac{1}{\sqrt p}\sum_x \chi(x + s)\psi(xy)
= \frac{1}{\sqrt p}\sum_z \chi(z)\psi\bigl((z - s)y\bigr)
= \psi(-sy)\,\widehat\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 \bmod 4$）。用 Gauss 和的标准计算，对 $y \neq 0$：

$$
\widehat\chi(y) = \frac{1}{\sqrt p}\sum_x \chi(x)\psi(xy)
\;\overset{(a)}{=}\; \frac{\chi(y)}{\sqrt p}\sum_x \chi(xy)\psi(xy)
\;\overset{(b)}{=}\; \frac{\chi(y)}{\sqrt p}\,\tau,
$$

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

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

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

(legendre-shift-algorithm)=
### 5.3 量子算法

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

1. **将 $f_s(x)$ 写入相位，制备移位特征态**。在均匀叠加 $\frac{1}{\sqrt p}\sum_x |x\rangle$ 上调用 oracle 并以标准技巧（先把 $\chi(x+s) \in \{-1, 0, +1\}$ 算入辅助寄存器，再施加相应相位，最后反算）给每个 $|x\rangle$ 乘上 $\chi(x + s)$。理想态为
$$
\frac{1}{\sqrt p}\sum_x \chi(x + s)|x\rangle.
$$
这里有一个技术细节：$x = -s$ 处 $\chi(0) = 0$，该基矢的振幅**缺失**（无法通过任何酉相位操作制造一个零振幅项的同时保持其余项为 $\pm 1$；实际实现中这一位只能任给一个相位或留空）。我们把它当作对理想态的一个小扰动，误差分析见下。
2. **做加法 QFT**（$\mathbb F_p$ 上的 $|x\rangle \mapsto \frac{1}{\sqrt p}\sum_y \psi(xy)|y\rangle$）。由平移定理，频域态为
$$
\sum_y \psi(-sy)\,\widehat\chi(y)\,|y\rangle
= \frac{\tau}{\sqrt p}\sum_{y \neq 0} \psi(-sy)\,\chi(y)\,|y\rangle,
$$
等号代入了 5.2 节的谱公式（$y = 0$ 项因 $\widehat\chi(0) = 0$ 自动消失）。
3. **相干消去已知的 $\widehat\chi(y)$ 相位**。分两部分：整体常数 $\tau/\sqrt p$ 是已知固定相位，直接以单比特相位门消去；$\chi(y)$ 部分用相位回传——相干地计算 $y$ 的 Legendre 符号（Euler 判别法即模幂运算，$\operatorname{poly}(\log p)$ 个门）并施加相应相位，与态中原有的 $\chi(y)$ 相消。剩余态为
$$
\frac{1}{\sqrt{p - 1}}\sum_{y \neq 0} \psi(-sy)|y\rangle
\;\approx\; \frac{1}{\sqrt p}\sum_{y} \psi(-sy)|y\rangle,
$$
后者正是 $\mathrm{QFT}\,|-s\rangle$（前者与后者的差别只是缺 $y = 0$ 一项，权重 $1/p$）。
4. **逆 QFT，将线性相位聚焦到 $|-s\rangle$**。测量得到 $-s$，即得 $s$。

**误差分析：单个零值为何只造成 $O(1/p)$ 误差**。两处“缺失振幅”——第 1 步 $x = -s$ 的基矢与第 3 步 $y = 0$ 的基矢——每一个在均匀叠加中的模方权重都恰为 $1/p$。把理想态记为 $|\Psi\rangle$、实际制备的态记为 $|\Psi'\rangle$，则两者相差至多两个模方各为 $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 符号相干计算为 $\operatorname{poly}(\log p)$。总量子运行时间 $\operatorname{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 节次指数通用算法与本节多项式特殊算法之间的真正分界。

(z8-worked-example)=
## 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}\Bigl(|0\rangle|x\rangle|f_0(x)\rangle + |1\rangle|x\rangle|f_1(x)\rangle\Bigr)
$$

（$\frac{1}{\sqrt{2 \cdot 8}} = \frac14$）。设测量函数值得到 $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\rangle + |1, 2\rangle}{\sqrt 2} = \frac{|0, u\rangle + |1, u - 3\rangle}{\sqrt 2}.
$$

**QFT 与相位**。$\mathbb Z_8$ 的特征标为 $\chi_y(x) = e^{2\pi i xy / 8}$，QFT 为 $|x\rangle \mapsto \frac{1}{\sqrt 8}\sum_{y=0}^{7} e^{2\pi i xy/8}|y\rangle$。作用后 $y$ 频率处的（未归一化）振幅为

$$
\chi_y(u)|0\rangle + \chi_y(u - 3)|1\rangle = \chi_y(u)\bigl(|0\rangle + \chi_y(-3)|1\rangle\bigr).
$$

每个 $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{\sqrt2}{2}(1 + i)$ |
| 2 | $e^{-3\pi i/2}$ | $i$ |
| 3 | $e^{-9\pi i/4} = e^{-\pi i/4}$ | $\frac{\sqrt2}{2}(1 - i)$ |
| 4 | $e^{-3\pi i} = e^{-\pi i}$ | $-1$ |

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

$$
\frac{|0\rangle + i\,|1\rangle}{\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 \bmod 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\rangle + |1,u-s\rangle}{\sqrt2}$；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【问题背景与经典复杂度】**（→ [0 节](#hidden-shift-motivation)）

1. 基础：写出隐藏平移问题的承诺条件，并用一句话说明它与 Simon/Shor 式周期寻找（求“哪些平移不改变函数”）在提问方式上的对偶关系。
2. 进阶：解释经典碰撞算法为何需要 $\Theta(\sqrt{|G|})$ 次查询才能以常数概率找到满足 $f_0(x) = f_1(x')$ 的一对输入，并说明这一复杂度关于 $\log|G|$ 是指数的。

> 提示：向两个 oracle 各查询 $k$ 次共得到 $k^2$ 个跨函数值对，每对相等的概率约为 $1/|G|$。

**练习 2【定义、稳定子与陪集不确定性】**（→ [1 节](#hidden-shift-definition)）

1. 基础：写出稳定子 $H = \{h \in G : f_0(x + h) = f_0(x),\ \forall x \in G\}$ 的定义，并逐条验证 $0 \in H$、对加法封闭、对取逆封闭。
2. 进阶：补全 Lemma 1 中未写出的一步：证明若 $f_0$ 的稳定子 $H$ 非平凡，则对任意满足承诺的 $s$，陪集 $s + H$ 中不同元素作为“答案”在黑盒模型下不可区分（即：对任意 $h \in H$，把 $s$ 换成 $s + h$ 后两个 oracle 完全不变）。

> 提示：把承诺条件 $f_1(x) = f_0(x + s)$ 中的 $s$ 换成 $s + h$，用 $h \in H$ 的定义逐项验证等式不变。

**练习 3【相位态的四步推导】**（→ [2 节](#phase-state-derivation)）

1. 基础：按顺序写出第 2 节四步（制备叠加、查询 oracle、测量函数值、QFT）每一步得到的态，并说明测量函数值后前两个寄存器为何坍缩到 $\frac{|0, u\rangle + |1, u - s\rangle}{\sqrt 2}$。
2. 进阶：按本课的 QFT 约定 $|x\rangle \mapsto \frac{1}{\sqrt{|G|}}\sum_y \chi_y(x)|y\rangle$，逐步推导第 2 节 $|\phi_y(s)\rangle$ 中相对相位是 $\chi_y(-s)$ 而非 $\chi_y(s)$，并说明若改用共轭约定的 QFT，结论应如何改写。

> 提示：用特征标的同态性质分解 $\chi_y(u - s)$；共轭约定相当于把每个 $\chi_y$ 换成 $\overline{\chi_y}$。

**练习 4【二面体 HSP 等价与次指数筛法】**（→ [3 节](#dihedral-hsp-equivalence)）

1. 基础：写出 $\operatorname{Dih}(G)$ 中元素的乘法规则 $(x, b)(y, c) = (x + (-1)^b y,\ b + c)$，并验证每个反射 $(t, 1)$ 都是二阶元。
2. 进阶：证明按第 3 节定义的 $F(x, 0) = f_0(x)$、$F(x, 1) = f_1(x)$ 在右陪集 $\{(x, 0),\ (x - s, 1)\}$ 上取值相等，且 $f_0$ injective 时不同陪集上的取值互不相同；再把 Kuperberg 筛法的 $\exp(O(\sqrt{\log|G|}))$ 与经典的 $\Theta(\sqrt{|G|})$ 都写成 $e^{(\cdot)}$ 形式，比较二者关于 $n = \log_2|G|$ 的指数。

> 提示：用 $(x, 0)(-s, 1) = (x - s, 1)$ 展开陪集；两个复杂度分别是 $e^{O(\sqrt n)}$ 与 $e^{\frac{1}{2} n \ln 2}$。

**练习 5【Simon 式线性代数解法】**（→ [4.1 节](#simon-linear-algebra)）

1. 基础：设 $n = 3$、$s = (1, 0, 1)$。对 $y = (1, 1, 0)$ 与 $y = (1, 0, 1)$ 分别计算 $y \cdot s$，写出选择位条件态是 $|+\rangle$ 还是 $|-\rangle$，并给出对应的线性方程 $y \cdot s = b$。
2. 进阶：在 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$ 维子空间的概率是 $2^k/2^n$。

**练习 6【bent 函数隐藏平移算法】**（→ [4.4 节](#bent-function-algorithm)）

1. 基础：按 4.3 节的归一化写出 Walsh–Hadamard 变换 $\widehat F(y) = \frac{1}{2^n}\sum_x F(x)(-1)^{x \cdot y}$ 的定义，并说明当 $F(x) = (-1)^{f(x)}$ 时 Parseval 恒等式给出 $\sum_y |\widehat F(y)|^2 = 1$。
2. 进阶：模仿 4.3 节的换元论证，在一般有限 Abel 群 $G$ 上证明 Fourier 平移定理：若 $f_s(x) = f_0(x + s)$，则 $\widehat f_s(y) = \chi_y(-s)\,\widehat f_0(y)$，并指出证明中用到特征标同态性质的具体步骤。
3. 进阶：据“所有 Walsh 系数模相等”与 Parseval 恒等式说明必有 $|\widehat F(y)| = 2^{-n/2}$；并结合 $2^n \widehat F(y) = \sum_x (-1)^{f(x) + x \cdot y}$ 必为整数这一观察，解释 bent 函数为何只可能存在于 $n$ 为偶数的情形。

> 提示：$2^n\widehat F(y)$ 是整数，模为 $2^{-n/2}$ 迫使它等于 $\pm 2^{n/2}$，而 $2^{n/2}$ 为整数当且仅当 $n$ 为偶数。

**练习 7【移位 Legendre 符号量子算法】**（→ [5.3 节](#legendre-shift-algorithm)）

1. 基础：对 $p = 7$，用 Euler 判别法 $\chi(x) = x^{(p-1)/2} = x^3 \bmod 7$ 计算 $\chi(1), \dots, \chi(6)$，验证二次剩余与非剩余各占一半，并据此说明 $\widehat\chi(0) = 0$。
2. 进阶：对 $y \neq 0$ 证明谱公式 $\widehat\chi(y) = \chi(y)\,\tau/\sqrt p$（其中 $\tau = \sum_x \chi(x)\psi(x)$ 为 Gauss 和），并说明 $|\tau| = \sqrt p$ 为何蕴含 Legendre 符号的加法谱在所有非零频率上模平坦。
3. 进阶：解释 Legendre oracle 的单个零值（$x = -s$ 处的缺失振幅）为何只造成 $O(1/p)$ 的成功概率损失；进一步说明若改为“把缺失项重新归一化”，实际态与理想态的内积平方为 $1 - 1/p$，结论为何不变。

> 提示：缺失基矢在均匀叠加中的模方恰为 $1/p$；对内积 $\sqrt{1 - 1/p}$ 与 $1$ 的差做一阶估计。

**练习 8【循环数组手算例子】**（→ [7 节](#z8-worked-example)）

1. 基础：在 7 节的例子（$G = \mathbb Z_8$、$s = 3$、测得 $u = 5$）中写出测量函数值后的二项态，并自行计算表格之外的 $y = 6$ 时选择位的相对相位与条件态。
2. 进阶：把同一问题改写到 $\mathbb Z_2^3$ 上并取 $s = (1, 1, 0)$：对 $y = (1, 0, 1)$ 与 $y = (1, 1, 1)$ 写出选择位条件态；再解释为何在 $\mathbb Z_2^3$ 上 $O(n)$ 份相位态即可解出 $s$，而在 $\mathbb Z_8$ 上单份相位态读不出 $s$。

> 提示：$\mathbb Z_2^3$ 上的特征标只取 $\pm 1$，相对相位即 $(-1)^{y \cdot s}$。

## 参考文献与 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)。