# 量子多项式插值：用矩曲线相位把查询数减半

经典上，次数至多 $d$ 的一元多项式有 $d+1$ 个系数，必须查询 $d+1$ 个不同点的函数值才能把它唯一恢复出来——这是代数基本事实，与计算能力无关。本课要讲的量子算法把这个阈值降到大约一半：约 $(d+1)/2$ 次量子查询就足以以常数成功率恢复全部系数，而且这个次数被证明是最优的。

这项工作的动机来自密码分析：Boneh 与 Zhandry 在研究"量子可访问"的消息认证码（MAC）与秘密共享方案时提出，如果攻击者可以对认证预言机做量子叠加查询，那么多项式型的认证方案是否还安全？这归结为"用尽量少的量子查询恢复一个隐藏多项式"这一纯粹的查询复杂度问题。Childs 等人（arXiv:1509.09271，Quantum Algorithm Zoo 第 360–361 条）给出了一元情形的最优算法与匹配的下界；Chen、Childs 与 Hung（arXiv:1701.03990，Zoo 第 387 条）随后把它推广到多变量多项式，并发现加速因子可以随变量数增长而超过 2。

整个算法的核心是一个称为 moment map（矩映射）的代数对象：

$$
Z(x,y)_j=\sum_{i=1}^k y_i x_i^j,\qquad j=0,1,\ldots,d.
$$

本课将按部就班地讲清楚三件事：moment map 如何从 phase kickback 中自然出现；为什么算法的成功概率**恰好**等于 $Z$ 的像的相对大小 $|R_k|/q^{d+1}$，而且任何 $k$ 查询算法都无法超过它；以及多变量情形的加速因子为何可以超过 2。

**前置知识**：本章默认读者熟悉有限域 $\mathbb F_q$ 的基本运算、相位反冲（phase kickback）技巧，以及有限 Abel 群上的量子傅里叶变换（见[量子傅里叶变换](../ch03-algo-basics/quantum-fourier-transform.md)）；本课会直接使用这些工具而不再重新推导。

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

1. **[插值问题与经典基线](#interpolation-classical-baseline)**——能写出 value oracle 模型与插值目标，并用 Vandermonde 方程和相容候选构造论证经典查询数恰为 $d+1$ 次。
2. **[加法特征与相位反冲](#additive-char-phase-kickback)**——能由域迹定义加法特征并验证其正交关系，再通过换元推导 Fourier 基态上一次 value query 等价于一次相位查询。
3. **[矩曲线与 moment map](#moment-map)**——能把 $k$ 次查询的总相位指数整理成内积 $c\cdot Z(x,y)$，并解释 $Z$ 值相同的查询历史为何不可区分。
4. **[截断 Fourier 态与成功率](#truncated-fourier-state)**——能写出制备截断 Fourier 态的三步算法，并推导测得正确系数的概率恰好等于 $|R_k|/q^{d+1}$。
5. **[最优性的维数论证](#optimality-dimension-argument)**——能证明任意 $k$ 查询算法的全部输出态落在至多 $|R_k|$ 维的子空间内，从而成功概率不超过 $|R_k|/q^{d+1}$。
6. **[奇数次数的最优阈值](#odd-degree-threshold)**——能用 Hankel 分解 $H=VDV^T$ 证明好原像至多相差一个排列，并计数得出 $k=\frac{d+1}{2}$ 时的常数成功率。
7. **[偶数次数与 padding 统一](#even-degree-padding)**——能解释二阶矩方法如何给出 $1-O(1/q)$ 的成功率，并用 padding 技巧统一奇偶两种次数的查询阈值。
8. **[多变量推广与加速因子](#multivariate-speedup)**——能计算单项式个数 $M=\binom{n+d}{d}$ 并写出多变量 moment map，比较三种域上的查询阈值与随 $n$ 增长的加速因子。

:::

(interpolation-classical-baseline)=
## 1. 问题设定与经典基线

### 1.1 插值问题

取有限域 $\mathbb F_q$，其中 $q=p^m$ 是素数幂，并设 $q>d$（保证域中有足够多的不同点）。未知的隐藏多项式为

$$
f(X)=c_0+c_1X+\cdots+c_dX^d\in\mathbb F_q[X],
$$

它被装在一个 **value oracle（求值预言机）** 里：

$$
O_f|x,z\rangle=|x,\,z+f(x)\rangle,\qquad x,z\in\mathbb F_q.
$$

这是标准的可逆求值接口：第一个寄存器输入点 $x$，第二个寄存器把函数值**加**进 $z$（加法在 $\mathbb F_q$ 中进行）。注意这里允许以 $x$ 的量子叠加作为输入——这正是"量子查询"与"经典查询"的本质区别，后文第 6 节会回到这一模型假设的适用边界。

目标是：用尽量少的对 $O_f$ 的调用，输出完整的系数向量

$$
c=(c_0,c_1,\ldots,c_d)\in\mathbb F_q^{d+1}.
$$

我们关心的首要资源是**查询次数**（query complexity），即调用 $O_f$ 的次数；门复杂度的问题放到第 6 节单独讨论。

### 1.2 经典算法：Vandermonde 方程

经典做法是把插值化为线性代数。任取 $d+1$ 个互不相同的点 $x_0,x_1,\ldots,x_d$，逐点查询得到函数值 $f(x_i)$。由于 $f(x_i)=\sum_{j=0}^{d}c_jx_i^j$，这 $d+1$ 个等式可以写成矩阵形式

$$
\underbrace{\begin{pmatrix}
1 & x_0 & x_0^2 & \cdots & x_0^{d}\\
1 & x_1 & x_1^2 & \cdots & x_1^{d}\\
\vdots & & & & \vdots\\
1 & x_d & x_d^2 & \cdots & x_d^{d}
\end{pmatrix}}_{=:\,V\ \text{（Vandermonde 矩阵）}}
\begin{pmatrix}c_0\\ c_1\\ \vdots\\ c_d\end{pmatrix}
=
\begin{pmatrix}f(x_0)\\ f(x_1)\\ \vdots\\ f(x_d)\end{pmatrix}.
$$

Vandermonde 矩阵的行列式有显式公式（作为习题请读者证明）：

$$
\det V=\prod_{0\le i<j\le d}(x_j-x_i).
$$

因为我们取的 $x_i$ 互不相同，右端每个因子都非零，所以 $\det V\ne0$，即 $V$ 可逆。于是

$$
c=V^{-1}\bigl(f(x_0),\ldots,f(x_d)\bigr)^T,
$$

$d+1$ 次经典查询**充分**。

### 1.3 经典下界：少一次查询为什么不行

反过来，$d$ 次查询为什么必然不够？关键观察是：$d$ 个点值留下的不是"信息不足所以算得慢"，而是**原则上不唯一**。设已查询 $x_1,\ldots,x_d$ 这 $d$ 个点。构造

$$
P(X)=\prod_{i=1}^{d}(X-x_i),
$$

这是一个次数恰为 $d$ 的非零多项式，且在所有已查询点上取值为 $0$。于是对任意 $\lambda\in\mathbb F_q$，多项式

$$
f_\lambda(X)=f(X)+\lambda P(X)
$$

与 $f$ 在全部 $d$ 个已查询点上取值完全相同，但次数仍不超过 $d$，且当 $\lambda\ne0$ 时 $f_\lambda\ne f$。也就是说，$d$ 次查询的答案与 $q$ 个不同的候选多项式全部相容，这些候选之间无论用什么经典后处理都无法区分。

这一点对有界错误模型同样成立：若隐藏多项式是从全部 $q^{d+1}$ 个多项式中均匀随机选取的，那么给定 $d$ 个点值之后，剩余 $q$ 个相容候选仍然等可能，任何策略猜中正确系数的概率至多为 $1/q$——当 $q$ 增大时趋于 $0$。因此 $d+1$ 次经典查询是**充分且必要**的（精确地说，有界错误恢复需要 $d+1$ 次）。

经典基线就此确定：$\Theta(d)$ 次查询，常数因子为 $1$。量子算法的目标是把常数因子压到 $1/2$。

### 1.4 为什么量子查询可能省一半？

在进入正式构造之前，先给一个计数层面的直觉——它将在第 5 节被 moment map 严格化。

一次经典查询返回一个域元素 $f(x)\in\mathbb F_q$，即"一份"信息；要确定 $d+1$ 个系数就需要 $d+1$ 份。量子查询的出路在于：我们可以把答案寄存器制备在 Fourier 基态上，通过相位反冲把函数值变成**相位**。一次相位查询涉及两个寄存器——查询点 $x$ 与 Fourier 频率 $y$——共 $2$ 个域元素的自由度。粗略地说，$k$ 次量子查询造出的态由 $2k$ 个域元素"标记"，要让它携带足以区分 $q^{d+1}$ 个候选多项式的信息，自然猜测阈值是

$$
2k\approx d+1,\qquad\text{即}\qquad k\approx\frac{d+1}{2}.
$$

下面几节逐步把这个量纲分析变成定理：第 2 节说明量子查询如何把函数值转成相位；第 3 节说明这些相位如何只通过 moment map $Z(x,y)$ 依赖于系数；第 4 节给出算法并证明其成功率恰为 $|R_k|/q^{d+1}$；第 5 节估计 $|R_k|$ 的大小，定出最优阈值。

(additive-char-phase-kickback)=
## 2. 从求值 Oracle 到相位 Oracle

### 2.1 有限域上的加法特征

要把 $\mathbb F_q$ 上的函数值写成复数相位，需要加法特征（additive character）。设 $q=p^m$，$p$ 为素数。**域迹（field trace）** 定义为

$$
\operatorname{Tr}:\mathbb F_q\to\mathbb F_p,\qquad
\operatorname{Tr}(z)=z+z^p+z^{p^2}+\cdots+z^{p^{m-1}}.
$$

对本课而言只需要它的两条性质（均可由定义直接验证）：

- **$\mathbb F_p$-线性**：对 $a,b\in\mathbb F_q$ 与 $\lambda\in\mathbb F_p$，有 $\operatorname{Tr}(a+b)=\operatorname{Tr}(a)+\operatorname{Tr}(b)$ 且 $\operatorname{Tr}(\lambda a)=\lambda\operatorname{Tr}(a)$。这由 Freshman's dream（特征 $p$ 域中 $(u+v)^p=u^p+v^p$）推出。
- **非退化性**：$\operatorname{Tr}$ 不恒为零，事实上它取遍 $\mathbb F_p$ 中每个值恰好 $q/p$ 次。

由此定义标准的加法特征

$$
e(z)=\exp\!\left(\frac{2\pi i\,\operatorname{Tr}(z)}{p}\right),\qquad z\in\mathbb F_q.
$$

由于 $\operatorname{Tr}(z)\in\mathbb F_p\cong\mathbb Z/p\mathbb Z$，指数中的 $\operatorname{Tr}(z)/p$ 只依赖于 $\operatorname{Tr}(z)$ 模 $p$ 的剩余类，定义是良好的。由迹的加性立刻得到特征的乘性：

$$
e(a+b)=e(a)\,e(b)\qquad\forall a,b\in\mathbb F_q.
$$

本课反复使用的基本恒等式是**特征正交关系**：对任意 $u\in\mathbb F_q$，

$$
\frac1q\sum_{y\in\mathbb F_q}e(yu)=
\begin{cases}1,&u=0,\\0,&u\ne0.\end{cases}
$$

验证：$u=0$ 时每项都是 $e(0)=1$，和为 $q$。$u\ne0$ 时，乘法 $y\mapsto yu$ 是 $\mathbb F_q$ 的置换，故 $\sum_y e(yu)=\sum_{y'}e(y')$；而非退化性保证 $e(\cdot)$ 取遍 $p$ 次单位根各 $q/p$ 次，每个周期内单位根之和为 $0$，故总和为 $0$。当 $q=p$ 为素数时，$\operatorname{Tr}$ 就是恒等映射，$e(z)=e^{2\pi iz/p}$ 退化为读者在 QFT 一课中见过的普通复指数；一般情形只是多了一层迹映射。

### 2.2 相位反冲：一次 value query 等价于一次相位 query

现在把答案寄存器制备在"Fourier 基态"上。对每个 $y\in\mathbb F_q$ 定义

$$
|\chi_y\rangle=\frac1{\sqrt q}\sum_{w\in\mathbb F_q}e(-yw)\,|w\rangle.
$$

对计算基态 $|x\rangle|\chi_y\rangle$ 施加 value oracle $O_f$。按定义 $O_f|x,w\rangle=|x,w+f(x)\rangle$，由线性性：

$$
O_f|x\rangle|\chi_y\rangle
=\frac1{\sqrt q}\sum_{w}e(-yw)\,|x,\,w+f(x)\rangle.
$$

做换元 $w'=w+f(x)$（对固定的 $f(x)$，这是 $\mathbb F_q$ 上的双射，所以求和范围不变），则 $w=w'-f(x)$，代入相位：

$$
e(-yw)=e\bigl(-y(w'-f(x))\bigr)=e(-yw')\,e\bigl(yf(x)\bigr),
$$

第二步用了特征的乘性 $e(a+b)=e(a)e(b)$。注意 $e(yf(x))$ 不含求和指标 $w'$，可以提到求和号外：

$$
O_f|x\rangle|\chi_y\rangle
=e\bigl(yf(x)\bigr)\,\frac1{\sqrt q}\sum_{w'}e(-yw')\,|x,w'\rangle
=e\bigl(yf(x)\bigr)\,|x\rangle|\chi_y\rangle.
$$

答案寄存器原封不动地回到 $|\chi_y\rangle$，唯一的痕迹是相位 $e(yf(x))$。这就是相位反冲：对处于 Fourier 基态的答案寄存器而言，一次 value query 等价于一次 **phase query（相位查询）**

$$
|x,y\rangle\longmapsto e\bigl(yf(x)\bigr)\,|x,y\rangle.
$$

相位反冲在本站多课中出现过（Deutsch–Jozsa、Simon、相位估计），这里的唯一新意是相位由有限域加法特征 $e$ 承载，而不是 $\mathbb Z_2$ 上的 $(-1)$ 或 $\mathbb Z_N$ 上的 $e^{2\pi i\cdot/N}$。

### 2.3 $k$ 次并行查询的总相位

取两组各 $k$ 个域元素 $x=(x_1,\ldots,x_k),\,y=(y_1,\ldots,y_k)\in\mathbb F_q^k$，对 $k$ 对寄存器各做一次相位查询。由于每次查询只贡献一个相乘的相位，$k$ 次查询的总效果是

$$
\bigotimes_{i=1}^k|x_i,y_i\rangle
\longmapsto
\prod_{i=1}^k e\bigl(y_if(x_i)\bigr)\,\bigotimes_{i=1}^k|x_i,y_i\rangle
=
e\!\left(\sum_{i=1}^k y_if(x_i)\right)\bigotimes_{i=1}^k|x_i,y_i\rangle,
$$

其中最后一步再次用了特征乘性：$\prod_i e(a_i)=e(\sum_i a_i)$。

请特别注意这个总相位的结构：$\sum_i y_if(x_i)$ 是关于 $f$ **逐点求值后再线性组合**的量。一次经典查询只固定一个点值，而 $k$ 次量子相位查询把 $k$ 个点值**压缩进一个相位**——当然，代价是它混在了一起。下一步的代数展开将表明，这种"混合"恰好按系数向量 $c$ 整齐地重新组织。

(moment-map)=
## 3. 矩曲线与 moment map

把 $f(x_i)=\sum_{j=0}^{d}c_jx_i^j$ 代入上节的总相位指数，交换两个求和的次序：

$$
\sum_{i=1}^k y_if(x_i)
=\sum_{i=1}^k y_i\sum_{j=0}^{d}c_jx_i^j
=\sum_{j=0}^{d}c_j\left(\sum_{i=1}^k y_ix_i^j\right).
$$

括号里的量只依赖于查询寄存器 $(x,y)$，而与多项式无关；$c_j$ 只依赖于多项式。定义 **moment map（矩映射）**

$$
Z:\mathbb F_q^k\times\mathbb F_q^k\longrightarrow\mathbb F_q^{d+1},\qquad
Z(x,y)=\left(\sum_{i=1}^k y_i,\;\sum_{i=1}^k y_ix_i,\;\ldots,\;\sum_{i=1}^k y_ix_i^d\right),
$$

即第 $j$ 个分量为 $Z(x,y)_j=\sum_i y_ix_i^j$，那么上面的展开恰好写成内积

$$
\sum_{i=1}^k y_if(x_i)=c\cdot Z(x,y).
$$

于是 $k$ 次相位查询的总效果可以写成一个极其紧凑的形式：

$$
|x,y\rangle\longmapsto e\bigl(c\cdot Z(x,y)\bigr)\,|x,y\rangle.
$$

这个等式是整篇教程的枢纽，值得停下来解读：

- 当 $y$ 固定、$x$ 变化时，向量 $(1,x,x^2,\ldots,x^d)$ 扫出 $\mathbb F_q^{d+1}$ 中的一条 **moment curve（矩曲线）**——代数几何中最经典的曲线之一。$Z(x,y)$ 就是 $k$ 条带权 $y_i$ 的矩曲线向量之和，这也是 "moment map" 名称的由来。
- 一次量子查询不再只是"给出 $f$ 在某点的值"，而是贡献一条带权的矩曲线向量。多项式的系数向量 $c$ 从**不单独**出现——它只通过与 $Z(x,y)$ 的内积出现在相位里。
- 因此，对算法而言，两个查询历史 $(x,y)$ 与 $(x',y')$ 只要满足 $Z(x,y)=Z(x',y')$，就给出完全相同的相位，是绝对不可区分的。算法的全部信息瓶颈都由 $Z$ 的像决定——这是第 4 节成功率公式与最优性证明的共同根源。

(truncated-fourier-state)=
## 4. 算法：制备"截断 Fourier 态"

### 4.1 从均匀叠加到标记态

记 moment map 的像为

$$
R_k=\{Z(x,y):x,y\in\mathbb F_q^k\}\subseteq\mathbb F_q^{d+1}.
$$

对像中每个 $z\in R_k$，**规范地**（即用一个固定的、可逆计算的选择规则）挑出一个原像 $(x,y)$ 满足 $Z(x,y)=z$。所有这些代表组成的集合记为 $T_k$；按构造，限制映射 $Z:T_k\to R_k$ 是双射，特别地 $|T_k|=|R_k|$。

算法分三步：

**第一步：均匀制备。** 制备 $T_k$ 上的均匀叠加态

$$
\frac1{\sqrt{|T_k|}}\sum_{(x,y)\in T_k}|x,y\rangle.
$$

这一步的可行性问题（如何均匀采样代表元）不是平凡的，我们放到第 6 节讨论；本节的查询复杂度分析先假设它可以完成。

**第二步：相位查询。** 做 $k$ 次并行相位查询。由上节的结论，每一对 $(x_i,y_i)$ 贡献相位 $e(y_if(x_i))$，总相位为 $e(c\cdot Z(x,y))$：

$$
\frac1{\sqrt{|T_k|}}\sum_{(x,y)\in T_k}e\bigl(c\cdot Z(x,y)\bigr)\,|x,y\rangle.
$$

**第三步：可逆计算 $Z$。** 在辅助寄存器中计算 $Z(x,y)$（这是纯经典的、可逆的算术：$k(d+1)$ 次域上乘法与加法），然后利用 $Z:T_k\to R_k$ 的双射性做逆运算把 $(x,y)$ 寄存器**擦掉**（uncompute）。由于 $Z$ 限制在 $T_k$ 上是双射，这个"计算—换存—逆计算"的过程是合法的可逆操作，净效果是

$$
|\widehat c_{R_k}\rangle
=\frac1{\sqrt{|R_k|}}\sum_{z\in R_k}e(c\cdot z)\,|z\rangle.
$$

现在端详这个态。回忆 $\mathbb F_q^{d+1}$ 上的量子傅里叶变换把计算基态 $|c\rangle$ 映为

$$
\mathrm{QFT}\,|c\rangle=\frac1{\sqrt{q^{d+1}}}\sum_{z\in\mathbb F_q^{d+1}}e(c\cdot z)\,|z\rangle.
$$

两式对比：我们制备的态与 $\mathrm{QFT}|c\rangle$ 的唯一区别是求和范围从整个 $\mathbb F_q^{d+1}$ **截断**到了像集 $R_k$（相应地，归一化因子从 $\sqrt{q^{d+1}}$ 变为 $\sqrt{|R_k|}$）。因此称 $|\widehat c_{R_k}\rangle$ 为 $c$ 的**截断 Fourier 态（truncated Fourier state）**。若 $R_k$ 恰好是整个系数空间，它就是 $\mathrm{QFT}|c\rangle$ 本身，做一次逆 QFT 即以概率 $1$ 测得 $c$；一般情况下它只是截断版本，测量成功概率由截断掉的"缺口"大小决定——下面把这个直觉算成精确等式。

### 4.2 成功率恰好等于像的相对大小

对 $|\widehat c_{R_k}\rangle$ 施加 $\mathbb F_q^{d+1}$ 上的逆 QFT。由 QFT 的线性性与其在计算基上的定义，

$$
\mathrm{QFT}^{-1}|z\rangle=\frac1{\sqrt{q^{d+1}}}\sum_{c'\in\mathbb F_q^{d+1}}e(-c'\cdot z)\,|c'\rangle,
$$

所以

$$
\mathrm{QFT}^{-1}|\widehat c_{R_k}\rangle
=\frac1{\sqrt{|R_k|\,q^{d+1}}}\sum_{c'\in\mathbb F_q^{d+1}}\left(\sum_{z\in R_k}e\bigl((c-c')\cdot z\bigr)\right)|c'\rangle,
$$

这里把两个特征合并用到了 $e(a)e(-b)=e(a-b)$（乘性加上 $e(-b)=e(b)^{-1}$）。测量得到正确答案 $c'=c$ 的振幅是上式中 $c'=c$ 项的系数；此时相位 $e(0\cdot z)=e(0)=1$，内层求和退化为逐项 $1$ 相加：

$$
\text{振幅}(c)
=\frac1{\sqrt{|R_k|\,q^{d+1}}}\sum_{z\in R_k}1
=\frac{|R_k|}{\sqrt{|R_k|\,q^{d+1}}}
=\sqrt{\frac{|R_k|}{q^{d+1}}}.
$$

取模平方，得到本课的核心公式：

$$
\Pr[\text{测得正确的 }c]=\frac{|R_k|}{q^{d+1}}.
$$

也就是说：**成功概率恰好等于 moment map 的像在整个系数空间中所占的比例**。这是一个干净而强的结论——它把"算法分析"完全转化为"估计一个代数映射的像的大小"这一纯组合问题。第 5 节的全部工作就是估计 $|R_k|$。

（顺带一提，对 $c'\ne c$ 的分量，内层和 $\sum_{z\in R_k}e((c-c')\cdot z)$ 一般不会抵消为零——因为求和只跑在 $R_k$ 而不是全空间上，特征正交关系用不上。这些泄漏到错误答案上的振幅正是成功率损失的去向；上面的计算表明"正确"那一项的振幅只由 $|R_k|$ 决定。）

(optimality-dimension-argument)=
### 4.3 最优性：任何 $k$ 查询算法都不能做得更好

上面的公式给出的是**这个**算法的成功率。更强的事实是：$\frac{|R_k|}{q^{d+1}}$ 同时是**任意** $k$ 查询量子算法成功概率的上界。这就是"最优"二字的含义。证明思想是一个秩/维数论证，我们把它写成几个清楚的步骤。

**第一步：任意 $k$ 查询算法的末态形如"以 $Z$ 为标签的叠加"。** 考虑任意一个与 $O_f$ 交互 $k$ 次的量子算法：查询之间可以插入任意不依赖 $f$ 的酉变换，工作寄存器可以任意大。对第 $i$ 次查询，把此时第一、二寄存器的状态按计算基展开；经过相位反冲，每个基分量 $(x^{(i)},y^{(i)})$ 获得相位 $e(y^{(i)}f(x^{(i)}))$。归纳地把 $k$ 次查询的相位累积起来，末态必然具有形式

$$
|\psi_c\rangle=\sum_{x,y}\alpha_{x,y}\,e\bigl(c\cdot Z(x,y)\bigr)\,|x,y,w_{x,y}\rangle,
$$

其中振幅 $\alpha_{x,y}$ 与工作寄存器内容 $w_{x,y}$ 都**不依赖** $c$（它们只由查询之间那些与 $f$ 无关的酉决定），求和跑遍所有可能出现的查询历史 $(x,y)\in\mathbb F_q^{2k}$。这正是第 3 节观察的推而广之：$c$ 只通过与 $Z(x,y)$ 的内积进入相位。

**第二步：所有末态落在同一个低维子空间内。** 按 $Z$ 的取值把求和分组：对每个 $z\in R_k$，令

$$
|\beta_z\rangle=\sum_{(x,y):\,Z(x,y)=z}\alpha_{x,y}\,|x,y,w_{x,y}\rangle
\qquad(\text{未归一化}),
$$

则

$$
|\psi_c\rangle=\sum_{z\in R_k}e(c\cdot z)\,|\beta_z\rangle.
$$

右端是 $|R_k|$ 个固定向量 $|\beta_z\rangle$ 的线性组合，系数随 $c$ 变化。因此，**全部 $q^{d+1}$ 个候选末态** $\{|\psi_c\rangle\}$ 都落在子空间

$$
\mathcal H'=\operatorname{span}\{|\beta_z\rangle:z\in R_k\}
$$

内，而 $\dim\mathcal H'\le|R_k|$。注意这个子空间本身不依赖于 $c$。

**第三步：维数限制转化为成功概率限制。** 设算法最后用某个 POVM $\{E_c\}_{c\in\mathbb F_q^{d+1}}$（$\sum_cE_c=I$，$E_c\succeq0$）输出对系数的猜测。对均匀随机的隐藏多项式，平均成功概率为

$$
\bar p=\frac1{q^{d+1}}\sum_c\langle\psi_c|E_c|\psi_c\rangle
=\frac1{q^{d+1}}\sum_c\operatorname{Tr}\bigl(E_c\,|\psi_c\rangle\langle\psi_c|\bigr).
$$

由于 $|\psi_c\rangle$ 是 $\mathcal H'$ 中的单位向量，算子不等式 $|\psi_c\rangle\langle\psi_c|\preceq\Pi_{\mathcal H'}$ 成立（$\Pi_{\mathcal H'}$ 是到 $\mathcal H'$ 的正交投影：对任意向量 $|\phi\rangle$，$\langle\phi|\psi_c\rangle\langle\psi_c|\phi\rangle=|\langle\psi_c|\phi\rangle|^2\le\langle\phi|\Pi_{\mathcal H'}|\phi\rangle$， Cauchy–Schwarz 的直接推论）。代入求和：

$$
\sum_c\operatorname{Tr}\bigl(E_c|\psi_c\rangle\langle\psi_c|\bigr)
\le\sum_c\operatorname{Tr}\bigl(E_c\Pi_{\mathcal H'}\bigr)
=\operatorname{Tr}\Bigl(\Pi_{\mathcal H'}\underbrace{\sum_cE_c}_{=\,I}\Bigr)
=\operatorname{Tr}\Pi_{\mathcal H'}
=\dim\mathcal H'\le|R_k|.
$$

于是

$$
\bar p\le\frac{|R_k|}{q^{d+1}}.
$$

**结论。** 待区分的多项式共有 $q^{d+1}$ 个，而 $k$ 次查询能造出的所有输出态挤在一个至多 $|R_k|$ 维的子空间里；维数不足时必然有候选无法被可靠区分。我们的算法达到了这个上界（第 4.2 节），因此多项式插值问题的量子查询复杂度被**精确**刻画为：最小的使 $|R_k|/q^{d+1}$ 达到常数的 $k$。剩下的问题是纯粹的代数计数：$|R_k|$ 到底多大？

## 5. 最优查询阈值

本节回答：$k$ 取多大时 $|R_k|$ 占满（或占满常数比例的）$\mathbb F_q^{d+1}$？答案按 $d$ 的奇偶性分两种情形。

(odd-degree-threshold)=
### 5.1 奇数 $d$：$k=\frac{d+1}{2}$ 次查询达到常数成功率

设 $d$ 为奇数，取

$$
k=\frac{d+1}{2},\qquad\text{即 }d=2k-1.
$$

此时查询历史的总自由度 $2k$ 恰好等于系数个数 $d+1$，是"量纲恰好平衡"的点。我们要说明：对"好的"查询历史，moment map 几乎是 $k!$ 对 $1$ 的。

**定义（好原像）。** 称 $(x,y)\in\mathbb F_q^{2k}$ 是**好的（good）**，如果 $x_1,\ldots,x_k$ 互不相同且 $y_1,\ldots,y_k$ 全部非零。

**引理（好原像的唯一性，至多差一个排列）。** 设 $(x,y)$ 与 $(x',y')$ 都是好的，且 $Z(x,y)=Z(x',y')$。那么存在置换 $\sigma\in S_k$ 使 $x'_i=x_{\sigma(i)}$、$y'_i=y_{\sigma(i)}$。换句话说，同一个像 $z$ 的好原像之间只相差分量的重排。

**证明。** 记 $z=Z(x,y)=(z_0,z_1,\ldots,z_{2k-1})$。考虑由 $z$ 的连续分量排成的 $k\times k$ Hankel 矩阵

$$
H=\bigl(z_{a+b}\bigr)_{0\le a,b\le k-1}.
$$

（矩阵元最大下标为 $(k-1)+(k-1)=2k-2\le2k-1=d$，所以 $H$ 完全由 $z$ 决定。）关键观察是 $H$ 有精确的分解

$$
H=VDV^{T},\qquad V_{a,i}=x_i^{\,a}\ (0\le a\le k-1),\qquad D=\operatorname{diag}(y_1,\ldots,y_k).
$$

验证：$(VDV^T)_{a,b}=\sum_i V_{a,i}D_{ii}V_{b,i}=\sum_i x_i^a\,y_i\,x_i^b=\sum_iy_ix_i^{a+b}=z_{a+b}=H_{a,b}$。$V$ 正是 $x_1,\ldots,x_k$ 的 Vandermonde 矩阵（前 $k$ 列），由第 1.2 节的行列式公式，$x_i$ 互异给出 $\det V=\prod_{i<j}(x_j-x_i)\ne0$；$y_i$ 全非零给出 $D$ 可逆。故 $H$ 可逆。

现在从 $z$ 反解 $\{x_i\}$。寻找系数 $q_0,\ldots,q_{k-1}\in\mathbb F_q$ 使线性系统

$$
\sum_{b=0}^{k-1}H_{a,b}\,q_b=-z_{a+k},\qquad a=0,1,\ldots,k-1
$$

成立（右端下标最大为 $(k-1)+k=2k-1=d$，仍在 $z$ 的范围内）。$H$ 可逆保证解**存在唯一**。定义多项式

$$
Q(t)=t^k+q_{k-1}t^{k-1}+\cdots+q_1t+q_0.
$$

把 $H$ 的分解代入方程左端：

$$
\sum_b z_{a+b}q_b+z_{a+k}
=\sum_{i}y_ix_i^a\left(\sum_b x_i^b q_b+x_i^k\right)
=\sum_i y_i\,x_i^a\,Q(x_i)=0,\qquad a=0,\ldots,k-1.
$$

令 $w_i=y_iQ(x_i)$，上式即 $\sum_i w_i x_i^a=0$ 对 $a=0,\ldots,k-1$ 成立——写成矩阵即 $Vw=0$。$V$ 可逆，故 $w=0$；又 $y_i\ne0$，所以

$$
Q(x_i)=0,\qquad i=1,\ldots,k.
$$

即 $x_1,\ldots,x_k$ 恰好是首一 $k$ 次多项式 $Q$ 的全部 $k$ 个根。但 $Q$ 的系数由 $z$ 通过上述线性系统**唯一**决定，所以集合 $\{x_1,\ldots,x_k\}=\{x'_1,\ldots,x'_k\}$（作为带根的重数相同的集合，而根互异故为集合相等）。于是存在置换 $\sigma$ 使 $x'_i=x_{\sigma(i)}$。最后，$y$ 由线性系统 $\sum_i y_i x_i^j=z_j$（$j=0,\ldots,k-1$）唯一解出——这还是 Vandermonde 系统，$V$ 可逆故解唯一——所以 $y'_i=y_{\sigma(i)}$。Q.E.D.

**计数。** 由引理，每个有原像的 $z$ 至多对应 $k!$ 个好原像（一个置换轨道；由于 $x_i$ 互异，$k!$ 个置换给出 $k!$ 个**不同**的好原像，所以恰为 $k!$ 个，只要至少存在一个好原像）。而好原像的总数是

$$
N_{\text{good}}
=\underbrace{q(q-1)\cdots(q-k+1)}_{x_i\text{ 互异：依次有 }q,q-1,\ldots\text{ 种选法}}\cdot\underbrace{(q-1)^k}_{y_i\ne0}.
$$

对固定的 $k$，把两项分别展开：

$$
q(q-1)\cdots(q-k+1)=q^k\prod_{i=0}^{k-1}\Bigl(1-\frac i q\Bigr)=q^k\bigl(1-O(1/q)\bigr),
$$

$$
(q-1)^k=q^k\Bigl(1-\frac1q\Bigr)^k=q^k\bigl(1-O(1/q)\bigr),
$$

两式相乘得

$$
N_{\text{good}}=q^{2k}\bigl(1-O(1/q)\bigr)=q^{d+1}\bigl(1-O(1/q)\bigr),
$$

最后一步用了 $2k=d+1$。由于每个像点至多被 $k!$ 个好原像覆盖，

$$
|R_k|\ge\frac{N_{\text{good}}}{k!}=\frac{q^{d+1}}{k!}\bigl(1-O(1/q)\bigr).
$$

代回第 4.2 节的成功概率公式：

$$
\Pr[\text{成功}]=\frac{|R_k|}{q^{d+1}}\ge\frac1{k!}\bigl(1-O(1/q)\bigr).
$$

对**固定**的次数 $d$（从而 $k$ 与 $k!$ 都是常数），这是一个不随 $q$ 衰减的正常数成功率：重复 $O(1)$ 次即可把成功概率提升到任意接近 $1$。结合第 4.3 节的匹配上界，$k=\frac{d+1}{2}$ 就是奇数次数情形的**最优查询阈值**——恰为经典查询数 $d+1$ 的一半。（精细的分析还表明 $|R_k|/q^{d+1}=\frac1{k!}(1-O(1/q))$，即上式在渐近意义下是等式而非仅仅下界；对本课的目的，常数成功率已达下界要求。）

(even-degree-padding)=
### 5.2 偶数 $d$：$k=\frac d2+1$ 次查询达到高成功率

设 $d$ 为偶数，$d=2k-2$，即取

$$
k=\frac d2+1.
$$

此时 $2k=d+2>d+1$，查询历史的自由度比未知数多了一个。直觉上，"输入空间" $\mathbb F_q^{2k}$ 比"输出空间" $\mathbb F_q^{d+1}$ 大了 $q$ 倍，像集应当几乎占满整个输出空间。事实正是如此，但证明不再能用第 5.1 节的唯一性论证——请读者回看引理的证明：那时 Hankel 矩阵是 $k\times k$ 且右端用到 $z_{a+k}$（最大下标 $2k-1=d$）；现在 $d=2k-2$，同样的方程组缺少最后一行数据，$Q$ 不再被唯一确定，"好原像差一个排列"的结论失效。

替代工具是**二阶矩方法（second moment method）**，思想如下。对每个 $z\in\mathbb F_q^{d+1}$，记 $N(z)=|Z^{-1}(z)|$ 为原像个数。显然

$$
\sum_z N(z)=q^{2k}
$$

（每个 $(x,y)$ 恰被计一次），所以 $N(z)$ 在输出空间上的平均值为 $\mu=q^{2k}/q^{d+1}=q$，相当大。如果能进一步控制二阶矩，即说明

$$
\sum_z N(z)^2=q^{4k-(d+1)}\bigl(1+O(1/q)\bigr),
$$

（含义：原像个数的涨落主要来自对角项，即 $N(z)$ 围绕其均值集中），那么由 Chebyshev 不等式，$N(z)=0$ 的 $z$（即没有原像的"缺口"）至多占 $O(1/q)$ 的比例，从而

$$
\frac{|R_k|}{q^{d+1}}=1-O(1/q).
$$

二阶矩的估计需要对 $\sum_zN(z)^2$ 展开后逐类计数满足 $Z(x,y)=Z(x',y')$ 的四元组 $(x,y,x',y')$，其主体由"$(x',y')$ 是 $(x,y)$ 的置换"的对角项贡献，其余项被 Vandermonde 型论证压成 $O(1/q)$ 的相对误差；具体组合细节超出本课范围，我们引用原文结论。于是偶数次数时，$\frac d2+1$ 次查询直接给出**趋近于 $1$** 的成功概率（当 $q$ 大时）。

### 5.3 奇偶性的统一：padding 技巧与阈值总结

对奇数 $d$，若也希望成功率趋近 $1$（而非 $1/k!$ 的常数），有一个简单的补救：**把 $f$ 看作最高次系数为 $0$ 的 $d+1$ 次多项式**。$d+1$ 是偶数，套用第 5.2 节的结果，用

$$
\frac{d+1}{2}+1=\frac{d+3}{2}
$$

次查询即可以 $1-O(1/q)$ 的成功率恢复"扩充实"系数向量 $(c_0,\ldots,c_d,0)$，从而得到 $c$。代价仅仅是多一次查询。

总结最优阈值：

| 次数 $d$ | 目标 | 最优查询数 $k$ | 成功概率 |
|---|---|---|---|
| 奇数 | 常数成功率 | $\frac{d+1}{2}$ | $\ge\frac1{k!}(1-O(1/q))$，常数 |
| 奇数 | 高成功率 | $\frac{d+3}{2}$（padding 到 $d+1$） | $1-O(1/q)$ |
| 偶数 | 高成功率 | $\frac d2+1$ | $1-O(1/q)$ |

三种情形的有界错误查询阈值都约为经典查询数 $d+1$ 的**一半**，精确的取整方式与成功率由 $d$ 的奇偶性决定；且由第 4.3 节，这些次数都是最优的。

### 5.4 小例子：$d=1$，$k=1$ 的完整计算

最小的非平凡情形把上面的每一步都演算一遍。$d=1$（奇数），$k=\frac{d+1}{2}=1$。隐藏多项式是线性的：$f(X)=c_0+c_1X$。经典需要 $2$ 次查询，量子声称 $1$ 次即有常数成功率。

**moment map。** $k=1$ 时

$$
Z(x,y)=\bigl(y,\;yx\bigr)\in\mathbb F_q^2.
$$

**像集。** 逐一分析 $z=(z_0,z_1)\in\mathbb F_q^2$ 何时有原像：

- 若 $z_0\ne0$：取 $y=z_0$、$x=z_1/z_0$（$z_0$ 非零故可逆），则 $Z(x,y)=(z_0,z_0\cdot z_1/z_0)=(z_0,z_1)$。每个这样的 $z$ 恰有**一个**原像。这类 $z$ 共 $q(q-1)$ 个（$z_0$ 有 $q-1$ 种取法，$z_1$ 任意）。
- 若 $z_0=0$：由第一分量 $y=0$，此时第二分量 $z_1=yx=0$ 被强制为零。所以 $z=(0,0)$ 有 $q$ 个原像（$y=0$，$x$ 任意），而 $z=(0,z_1)$（$z_1\ne0$）**没有原像**。

因此

$$
|R_1|=q(q-1)+1=q^2-q+1,
$$

成功概率为

$$
\Pr[\text{成功}]=\frac{|R_1|}{q^2}=\frac{q^2-q+1}{q^2}=1-\frac1q+\frac1{q^2}.
$$

**与第 5.1 节公式对照。** $k=1$ 时 $k!=1$，一般公式给出 $\frac1{1!}(1-O(1/q))=1-O(1/q)$；我们的精确计算 $1-\frac1q+\frac1{q^2}$ 与之完全吻合。这里还有个小细节：$d=1$ 时缺口的来源不是"多个原像"而是"$y=0$ 浪费掉的查询"——$x$ 任意而 $y=0$ 的 $q$ 个坏查询历史全部坍缩到 $z=(0,0)$ 一个像点上。

**取 $q=3$ 具体列出。** $\mathbb F_3=\{0,1,2\}$，全部 $9$ 个查询历史：

| $y$ | $x=0$ | $x=1$ | $x=2$ |
|---|---|---|---|
| $0$ | $(0,0)$ | $(0,0)$ | $(0,0)$ |
| $1$ | $(1,0)$ | $(1,1)$ | $(1,2)$ |
| $2$ | $(2,0)$ | $(2,2)$ | $(2,1)$ |

像集 $R_1=\mathbb F_3^2\setminus\{(0,1),(0,2)\}$，共 $7$ 个点，成功概率 $7/9$——一次量子查询即有近八成的把握读出 $(c_0,c_1)$，而经典上一次查询（一个点值 $f(x)$）留下的候选直线仍有 $q$ 条，猜中概率只有 $1/3$。

## 6. 门复杂度与模型适用性

到此为止我们讨论的都是**查询复杂度**：算法访问 $O_f$ 的次数。但一个算法要真正"高效"，还必须能用多项式规模的量子线路实现。本节交代两个保留条款。

**能否真正高效实现 $T_k$？** 第 4.1 节的第一步要求均匀制备代表集 $T_k$ 上的叠加，第三步要求可逆地求 moment map 的原像（即给定 $z$ 解出规范代表 $(x,y)$）。对**固定**的 $d$，这是可以做到的：求解 $Z(x,y)=z$ 可以化为一个低次多项式方程（第 5.1 节的 $Q(t)$，次数 $k$）加上一个 Vandermonde 线性系统（解出 $y$），而求根与解线性系统在有限域上都有 $\operatorname{poly}(k,\log q)$ 的经典算法，从而可以用 $\operatorname{poly}(\log q,d)$ 个量子门可逆地实现；均匀制备的偏差只给成功率带来可忽略的损失。

但必须诚实指出两点。其一，以上效率都是对**固定次数 $d$** 而言的：隐藏常数可能包含 $k!$ 这类随 $d$ 迅速增长的因子（例如好原像的计数与成功率中的 $1/k!$，以及求根算法的复杂度），所以"固定次数"是一个重要的参数承诺——当 $d$ 本身趋于无穷时，门复杂度是否仍为 $\operatorname{poly}(d,\log q)$ 需要另行论证。其二，查询复杂度结论与门复杂度结论是分开的：前者最优性已被第 4.3 节证明，后者依赖上述构造。

**模型的适用边界。** 本课整个分析建立在"攻击者可以对求值接口做**量子叠加**查询"的假设上：$O_f$ 接受 $x$ 寄存器的叠加态并相干地返回结果。这个模型对量子可访问的 MAC 或秘密共享方案的攻击是有意义的——例如认证标签由隐藏多项式逐点计算、且实现该计算的设备可能被置于相干查询的场景。但它**不能**自动套用到只允许经典请求—响应交互的协议接口上：如果协议的实现环境强制每次查询都是经典的（例如远端服务器只接受经典输入），相位反冲无从发生，全部结论失效。评估这类攻击的现实性时，必须先确认目标接口是否真的允许叠加查询。

(multivariate-speedup)=
## 7. 多变量推广

最后说明为什么把问题推广到多变量后，量子加速因子可以**超过 2**。

### 7.1 单项式计数

设 $f\in\mathbb F_q[X_1,\ldots,X_n]$ 是 $n$ 元、总次数至多 $d$ 的多项式。它的系数个数等于满足

$$
\alpha_1+\alpha_2+\cdots+\alpha_n\le d,\qquad \alpha_i\ge0
$$

的非负整数向量（多重指标）$\alpha=(\alpha_1,\ldots,\alpha_n)$ 的个数，记为 $M$。引入松弛变量 $\alpha_{n+1}=d-\sum_i\alpha_i\ge0$，约束变为

$$
\alpha_1+\cdots+\alpha_n+\alpha_{n+1}=d.
$$

由"星与棒"（stars and bars）计数：把 $d$ 个不可分的球放进 $n+1$ 个盒子的方案数为

$$
M=\binom{n+d}{d}.
$$

（具体地：$d$ 个星与 $n$ 根棒排成一列共 $\binom{n+d}{n}=\binom{n+d}{d}$ 种排法，第 $i$ 盒中的球数即 $\alpha_i$，$\alpha_{n+1}$ 由总和约束自动确定。）经典上，$M$ 个系数需要 $M$ 个独立的点值，可以证明一般位置（generic position）上的 $M$ 个点给出可逆的多变量 Vandermonde 系统，且少于 $M$ 个点必留自由度（与第 1.3 节同样的论证）。因此经典查询数为 $M$。

### 7.2 多变量 moment map

相位反冲的推导逐字照搬到多变量：$k$ 次相位查询的总相位为 $e(\sum_i y_i f(x_i))$，其中现在 $x_i\in\mathbb F_q^n$ 是向量。展开 $f(x_i)=\sum_{|\alpha|\le d}c_\alpha x_i^\alpha$（这里 $x^\alpha:=x_1^{\alpha_1}\cdots x_n^{\alpha_n}$ 是单项式的标准缩写）并交换求和次序，得到多变量 moment map

$$
Z:\mathbb F_q^{kn}\times\mathbb F_q^k\longrightarrow\mathbb F_q^{M},\qquad
Z(x,y)_\alpha=\sum_{i=1}^k y_i\,x_i^\alpha,\qquad |\alpha|\le d.
$$

与一元情形完全平行：每个查询点贡献一条 $n$ 维带权矩曲线向量 $(x_i^\alpha)_{|\alpha|\le d}$，系数向量只通过 $c\cdot Z(x,y)$ 出现，第 4 节的算法、成功率公式 $|R_k|/q^M$ 与第 4.3 节的最优性论证全部原样成立（把 $q^{d+1}$ 换成 $q^M$）。唯一的差别在于 $|R_k|$ 的计数几何。

### 7.3 三种域上的阈值与加速因子

**自由度计数给出的一目了然的启发。** 每个查询点 $x_i$ 有 $n$ 个坐标，加上权重 $y_i$，一次查询贡献 $n+1$ 个域元素的自由度；$k$ 次查询共 $k(n+1)$ 个自由度，要覆盖 $M$ 个系数，自然要求

$$
k(n+1)\gtrsim M,\qquad\text{即}\qquad k\gtrsim\frac{M}{n+1}.
$$

对复数域 $\mathbb C$，代数几何中关于矩曲线张成的 secant 簇（secant variety）的经典结果把这个量纲估计基本实现：除少数低次例外情形，约

$$
k=\left\lceil\frac{M}{n+1}\right\rceil
$$

次查询即可达到成功率 $1$。实数域 $\mathbb R$ 上由于维度论证损失（实代数簇的拓扑性质使典型秩翻倍），约需其两倍。有限域 $\mathbb F_q$ 上没有现成的 secant 簇理论可用，Chen–Childs–Hung 通过直接的组合计数证明了接近

$$
k=\left\lceil\frac{d}{n+d}\,M\right\rceil
$$

次查询在大 $q$ 时给出高成功率。注意有限域的系数 $\frac{d}{n+d}$ 比 $\mathbb C$ 情形的 $\frac1{n+1}$ 大（$\frac{d}{n+d}\ge\frac1{n+1}$ 当且仅当 $d(n+1)\ge n+d$，即 $(d-1)n\ge0$），即有限域上的已知界弱于复数域；两者的差距正是代数几何工具缺失之处，仍是开放方向。

**加速因子。** 以有限域的结果为例，量子与经典查询数之比为

$$
\frac{M}{\lceil dM/(n+d)\rceil}\approx\frac{n+d}{d}=1+\frac nd.
$$

一元情形 $n=1$ 时它等于 $\frac{1+d}{d}\approx2$，与前面几节一致；但当 $n$ 增大时，加速因子 $\approx n/d$ 随变量数**线性增长**，而不只是一元情形的因子 2。例如固定 $d=2$、令 $n$ 增大，经典需要 $M=\binom{n+2}{2}\approx n^2/2$ 次查询，量子只需约 $\frac{2}{n+2}M\approx n$ 次——加速比本身趋于 $n/2$。直观地说，查询点本身携带 $n$ 个坐标的信息，变量越多，单次量子查询"免费"携带的矩曲线信息越丰富。

同样保留第 6 节的告诫：查询数的优势要变成实际算法，仍需能高效求解相应的多变量 moment 方程；高成功率版本的常数同样可能依赖 $d$。

## 8. 本课小结

- 相位反冲把一次 value query 变成一次 phase query；$k$ 次并行查询把 $k$ 个函数值合成一个关于全体系数的线性相位 $e(c\cdot Z(x,y))$，系数向量只通过 moment map 进入。
- 算法的净产物是"截断 Fourier 态" $|\widehat c_{R_k}\rangle$；对其做逆 QFT，测得正确系数的概率**恰好**等于 moment map 像的相对大小 $|R_k|/q^{d+1}$。同一个量也是任意 $k$ 查询算法成功概率的上界（所有输出态挤在 $|R_k|$ 维子空间内的维数论证），所以阈值问题完全化为对 $|R_k|$ 的计数。
- 奇数 $d$ 取 $k=\frac{d+1}{2}$：Hankel 矩阵分解 $H=VDV^T$ 保证好原像至多差一个排列，计数给出常数成功率 $\frac1{k!}(1-O(1/q))$；偶数 $d$ 取 $k=\frac d2+1$，二阶矩分析给出高成功率 $1-O(1/q)$；奇数 $d$ 要同级别的成功率可用 padding 多加一次查询。总之，有界错误阈值约为经典查询数的一半，并已被证明最优。
- 门复杂度上，固定 $d$ 时可用 $\operatorname{poly}(\log q,d)$ 门实现，但常数可能含 $k!$，"固定次数"是重要的参数承诺；模型要求量子叠加查询，适用于量子可访问的 MAC/秘密共享攻击，不能自动套到纯经典接口。
- 多变量推广中单项式数 $M=\binom{n+d}{d}$，查询阈值约为 $M/(n+1)$（$\mathbb C$）到 $\lceil dM/(n+d)\rceil$（$\mathbb F_q$），加速因子可随变量数 $n$ 增长，远超一元情形的 2。

## 练习题

**练习 1【插值问题与经典基线】**（→ [第 1 节](#interpolation-classical-baseline)）

1. 设 $q=5$、$d=2$，取插值点 $x_0=0$、$x_1=1$、$x_2=3$：写出对应的 $3\times3$ Vandermonde 矩阵，用行列式公式在 $\mathbb F_5$ 中计算 $\det V$，并说明矩阵可逆。
2. 证明 Vandermonde 行列式公式 $\det(x_i^{j})_{0\le i,j\le d}=\prod_{i<j}(x_j-x_i)$。
3. 复述经典下界论证：设已查询 $d$ 个互不相同的点，用 $P(X)=\prod_{i=1}^d(X-x_i)$ 构造出 $q$ 个与全部观测相容的不同候选多项式，并解释为什么任何经典策略猜中系数的概率至多 $1/q$。

> 提示：第 2 题把行列式看作 $x_d$ 的多项式，用代入法找出它的全部根。

**练习 2【加法特征与相位反冲】**（→ [第 2 节](#additive-char-phase-kickback)）

1. 取素域 $q=5$，此时 $e(z)=e^{2\pi iz/5}$：计算 $e(2)\,e(4)$ 并把结果化成 $e(\cdot)$ 的形式；再分别验证 $\frac15\sum_{y\in\mathbb F_5}e(yu)$ 在 $u=0$ 与 $u=1$ 处的取值。
2. 设 $q=4=2^2$：写出域迹 $\operatorname{Tr}(z)=z+z^2$，说明 $e(z)=\exp\!\bigl(2\pi i\operatorname{Tr}(z)/2\bigr)$ 的取值只可能是哪些复数，并对照素域情形说明为什么一般的 $q=p^m$ 必须经过迹映射来定义加法特征。
3. 补全第 2.2 节的换元推导：从 $O_f|x\rangle|\chi_y\rangle=\frac1{\sqrt q}\sum_{w}e(-yw)\,|x,\,w+f(x)\rangle$ 出发得到 $e(yf(x))\,|x\rangle|\chi_y\rangle$，标明每一步用到的性质（换元是双射、特征乘性、与求和指标无关的因子提出求和号）。

> 提示：第 3 题换元 $w'=w+f(x)$ 后，相位因子 $e(yf(x))$ 不含求和指标 $w'$。

**练习 3【矩曲线与 moment map】**（→ [第 3 节](#moment-map)）

1. 在 $\mathbb F_5$ 上取 $k=2$、$(x_1,x_2)=(1,2)$、$(y_1,y_2)=(3,4)$、$d=1$：计算 $Z(x,y)$ 的两个分量。
2. 对一般的 $f(X)=\sum_{j=0}^{d}c_jX^j$ 验证恒等式 $\sum_{i=1}^k y_if(x_i)=c\cdot Z(x,y)$，完整写出交换求和次序的每一步。
3. 说明满足 $Z(x,y)=Z(x',y')$ 的两个查询历史为什么对一切次数至多 $d$ 的多项式给出相同的总相位，并解释这一"信息瓶颈"如何同时导出第 4.2 节的成功率公式与第 4.3 节的最优性上界。

> 提示：第 3 题注意 $k$ 次查询的总相位只通过 $e(c\cdot Z(x,y))$ 依赖于系数。

**练习 4【截断 Fourier 态与成功率】**（→ [第 4 节](#truncated-fourier-state)）

1. 写出截断 Fourier 态 $|\widehat c_{R_k}\rangle$ 的定义式，指出它与 $\mathrm{QFT}|c\rangle$ 的唯一区别，并计算 $R_k=\mathbb F_q^{d+1}$ 时的成功概率。
2. 从截断 Fourier 态 $|\widehat c_{R_k}\rangle$ 出发，补全第 4.2 节推导的每一步，证明测得正确 $c$ 的概率为 $|R_k|/q^{d+1}$；并说明为什么对 $c'\ne c$ 不能直接断言振幅为零。
3. 设 $\theta=|R_k|/q^{d+1}$ 为正常数：计算独立重复 $r$ 次至少成功一次的概率，把"成功率提升到 $1-\varepsilon$"所需的重复次数写成 $\theta$ 与 $\varepsilon$ 的表达式，并说明它与正文"重复 $O(1)$ 次即可"的论断一致。

> 提示：第 2 题对 $c'=c$ 的项，内层和退化为 $\sum_{z\in R_k}1$；第 3 题解不等式 $(1-\theta)^r\le\varepsilon$。

**练习 5【最优性的维数论证】**（→ [4.3 节](#optimality-dimension-argument)）

1. 写出任意 $k$ 查询量子算法末态的一般形式 $|\psi_c\rangle=\sum_{x,y}\alpha_{x,y}\,e(c\cdot Z(x,y))\,|x,y,w_{x,y}\rangle$，并解释为什么振幅 $\alpha_{x,y}$ 与工作寄存器内容 $w_{x,y}$ 都不依赖于未知系数 $c$。
2. 证明：全部 $q^{d+1}$ 个候选末态都落在同一个维数至多 $|R_k|$ 的子空间 $\mathcal H'=\operatorname{span}\{|\beta_z\rangle:z\in R_k\}$ 内，并由此完成平均成功概率 $\bar p\le|R_k|/q^{d+1}$ 的维数计数。

> 提示：第 2 题对任意 $|\phi\rangle$ 用 Cauchy–Schwarz 比较 $|\langle\psi_c|\phi\rangle|^2$ 与 $\langle\phi|\Pi_{\mathcal H'}|\phi\rangle$，再对 POVM 用 $\sum_cE_c=I$。

**练习 6【奇数次数的最优阈值】**（→ [5.1 节](#odd-degree-threshold)）

1. 对 $d=1$、$k=1$，写出 $Z(x,y)=(y,yx)$，并完整计算 $\mathbb F_q$ 上哪些 $z$ 没有原像、各有几个原像（对照第 5.4 节）；验证 $|R_1|=q^2-q+1$。
2. 对 $k=2$、$d=3$ 具体写出第 5.1 节的 Hankel 矩阵 $H$ 与分解 $H=VDV^T$，验证 $(VDV^T)_{a,b}=z_{a+b}$，并说明为什么 $x_1\ne x_2$ 与 $y_1y_2\ne0$ 共同保证 $H$ 可逆。
3. 推导好原像的总数 $N_{\text{good}}=q(q-1)\cdots(q-k+1)\cdot(q-1)^k$，并由"每个像至多被 $k!$ 个好原像覆盖"得出 $|R_k|\ge\frac{q^{d+1}}{k!}\bigl(1-O(1/q)\bigr)$；说明为什么 $k!$ 个置换给出 $k!$ 个互不相同的好原像。

> 提示：第 2 题中 $\det V=x_2-x_1$，故 $\det H=(\det V)^2\,y_1y_2$。

**练习 7【偶数次数与 padding 统一】**（→ [5.2 节](#even-degree-padding)）

1. 解释为什么第 5.1 节"好原像至多相差一个排列"的唯一性论证在偶数 $d=2k-2$ 时失效：Hankel 线性系统缺少哪一行数据、多项式 $Q$ 为何不再被 $z$ 唯一确定。
2. 对 $d=3$ 与 $d=4$ 分别写出"常数成功率"与"高成功率"目标下的最优查询数与对应的成功概率，并核对它们都约为经典查询数 $d+1$ 的一半。
3. 解释第 5.3 节的 padding 技巧：为什么把奇数次的 $f$ 看作"最高次系数为 0 的 $d+1$ 次多项式"后，偶数情形的结论可以直接套用？这样做查询数和成功概率各是多少？

> 提示：第 3 题注意 $d+1$ 是偶数，直接套用第 5.2 节的结果。

**练习 8【多变量推广与加速因子】**（→ [第 7 节](#multivariate-speedup)）

1. 对 $n=2$、$d=2$ 列出全部单项式，验证系数个数 $M=\binom{n+d}{d}=6$，并写出多变量 moment map 的分量定义 $Z(x,y)_\alpha=\sum_{i=1}^k y_ix_i^\alpha$（$|\alpha|\le d$）。
2. 对 $n=2$、$d=2$，分别计算 $\mathbb C$、$\mathbb R$、$\mathbb F_q$ 三种域上的查询数上界与相对经典的加速因子。
3. 解释为什么 $n$ 元情形下单次量子查询携带 $n+1$ 个域元素的自由度，从而加速因子约为 $1+\frac nd$ 并随变量数增长；以固定 $d=2$、$n$ 增大为例，比较经典查询数 $M=\binom{n+2}{2}\approx\frac{n^2}{2}$ 与量子查询数约 $n$。

> 提示：第 2 题依次用 $\lceil M/(n+1)\rceil$、它的两倍、$\lceil dM/(n+d)\rceil$。

## 参考文献与 Zoo 覆盖

- Zoo 360--361：Boneh--Zhandry 与 Andrew Childs 等，[Optimal Quantum Algorithm for Polynomial Interpolation](https://arxiv.org/abs/1509.09271).
- Zoo 387：Jianxin Chen、Andrew Childs 与 Shih-Han Hung, [Quantum Algorithm for Multivariate Polynomial Interpolation](https://arxiv.org/abs/1701.03990).
- Zoo 89、390--392：隐藏平移、character evaluation、含噪有理函数重构与高次幂 oracle 下的插值/恒等测试推广。