量子多项式插值

经典上，次数至多 $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,j=0,1,\dots ,d.$$

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

前置知识：本词条默认读者熟悉有限域 ${\mathbb{F}}_q$ 的基本运算、相位反冲（phase kickback）技巧，以及有限 Abel 群上的量子傅里叶变换（见量子傅里叶变换）；本词条会直接使用这些工具而不再重新推导。

1. 问题设定与经典基线

1.1 插值问题

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

$$f(X)=c_0+c_{1}X+\cdots +c_d{X}^d\in {\mathbb{F}}_q[X],$$

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

$$O_f|x,z⟩=|x,z+f(x)⟩,x,z\in {\mathbb{F}}_q.$$

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

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

$$c=(c_0,c_1,\dots ,c_d)\in {\mathbb{F}}_q^{d+1}.$$

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

1.2 经典算法：Vandermonde 方程

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

$$\underset{=:V\text{（Vandermonde 矩阵）}}{\underbrace{\left(\begin{array}{ccccc}1& x_0& x_0^2& \cdots & x_0^d\\ 1& x_1& x_1^2& \cdots & x_1^d\\ ⋮& & & & ⋮\\ 1& x_d& x_d^2& \cdots & x_d^d\end{array}\right)}}\left(\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_d\end{array}\right)=\left(\begin{array}{c}f(x_0)\\ f(x_1)\\ ⋮\\ f(x_d)\end{array}\right).$$

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

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

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

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

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

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

反过来，$d$ 次查询为什么必然不够？关键观察是：$d$ 个点值留下的不是”信息不足所以算得慢”，而是原则上不唯一。设已查询 $x_1,\dots ,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 \ne 0$ 时 $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,\text{即}k\approx \frac{d+1}{2}.$$

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

2. 从求值 Oracle 到相位 Oracle

2.1 有限域上的加法特征

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

$$\mathrm{Tr}:{\mathbb{F}}_q\to {\mathbb{F}}_p,\mathrm{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$，有 $\mathrm{Tr}(a+b)=\mathrm{Tr}(a)+\mathrm{Tr}(b)$ 且 $\mathrm{Tr}(\lambda a)=\lambda \mathrm{Tr}(a)$。这由 Freshman’s dream（特征 $p$ 域中 $(u+v{)}^p=u^p+v^p$）推出。
• 非退化性：$\mathrm{Tr}$ 不恒为零，事实上它取遍 ${\mathbb{F}}_p$ 中每个值恰好 $q/p$ 次。

由此定义标准的加法特征

$$e(z)=\exp \left(\frac{2\pi i\mathrm{Tr}(z)}{p}\right),z\in {\mathbb{F}}_q.$$

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

$$e(a+b)=e(a)e(b)\forall a,b\in {\mathbb{F}}_q.$$

本词条反复使用的基本恒等式是特征正交关系：对任意 $u\in {\mathbb{F}}_q$，

$$\frac{1}{q}\sum _{y\in {\mathbb{F}}_q}e(yu)=\{\begin{array}{ll}1,& u=0,\\ 0,& u\ne 0.\end{array}$$

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

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

现在把答案寄存器制备在”Fourier 基态”上。对每个 $y\in {\mathbb{F}}_q$ 定义

$$|{\chi }_y⟩=\frac{1}{\sqrt{q}}\sum _{w\in {\mathbb{F}}_q}e(-yw)|w⟩.$$

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

$$O_f|x⟩|{\chi }_y⟩=\frac{1}{\sqrt{q}}\sum _{w}e(-yw)|x,w+f(x)⟩.$$

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

$$e(-yw)=e(-y(w^{\prime }-f(x)))=e(-y{w}^{\prime })e(yf(x)),$$

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

$$O_f|x⟩|{\chi }_y⟩=e(yf(x))\frac{1}{\sqrt{q}}\sum _{w^{\prime }}e(-y{w}^{\prime })|x,w^{\prime }⟩=e(yf(x))|x⟩|{\chi }_y⟩.$$

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

$$|x,y⟩⟼e(yf(x))|x,y⟩.$$

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

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

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

$$\underset{i=1}{\overset{k}{⨂}}|x_i,y_i⟩⟼\prod _{i=1}^{k}e(y_{i}f(x_i))\underset{i=1}{\overset{k}{⨂}}|x_i,y_i⟩=e\left(\sum _{i=1}^k{y}_{i}f(x_i)\right)\underset{i=1}{\overset{k}{⨂}}|x_i,y_i⟩,$$

其中最后一步再次用了特征乘性：${\prod }_{i}e(a_i)=e({\sum }_i{a}_i)$。

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

3. 矩曲线与 moment map

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

$$\sum _{i=1}^k{y}_{i}f(x_i)=\sum _{i=1}^k{y}_i\sum _{j=0}^d{c}_j{x}_i^j=\sum _{j=0}^d{c}_j\left(\sum _{i=1}^k{y}_i{x}_i^j\right).$$

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

$$Z:{\mathbb{F}}_q^k\times {\mathbb{F}}_q^k⟶{\mathbb{F}}_q^{d+1},Z(x,y)=\left(\sum _{i=1}^k{y}_i,\sum _{i=1}^k{y}_i{x}_i,\dots ,\sum _{i=1}^k{y}_i{x}_i^d\right),$$

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

$$\sum _{i=1}^k{y}_{i}f(x_i)=c\cdot Z(x,y).$$

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

$$|x,y⟩⟼e(c\cdot Z(x,y))|x,y⟩.$$

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

• 当 $y$ 固定、$x$ 变化时，向量 $(1,x,x^2,\dots ,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^{\prime },y^{\prime })$ 只要满足 $Z(x,y)=Z(x^{\prime },y^{\prime })$，就给出完全相同的相位，是绝对不可区分的。算法的全部信息瓶颈都由 $Z$ 的像决定——这是第 4 节成功率公式与最优性证明的共同根源。

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$ 上的均匀叠加态

$$\frac{1}{\sqrt{|T_k|}}\sum _{(x,y)\in T_k}|x,y⟩.$$

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

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

$$\frac{1}{\sqrt{|T_k|}}\sum _{(x,y)\in T_k}e(c\cdot Z(x,y))|x,y⟩.$$

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

$$|{\hat{c}}_{R_k}⟩=\frac{1}{\sqrt{|R_k|}}\sum _{z\in R_k}e(c\cdot z)|z⟩.$$

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

$$\mathrm{QFT}|c⟩=\frac{1}{\sqrt{q^{d+1}}}\sum _{z\in {\mathbb{F}}_q^{d+1}}e(c\cdot z)|z⟩.$$

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

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

对 $|{\hat{c}}_{R_k}⟩$ 施加 ${\mathbb{F}}_q^{d+1}$ 上的逆 QFT。由 QFT 的线性性与其在计算基上的定义，

$${\mathrm{QFT}}^{-1}|z⟩=\frac{1}{\sqrt{q^{d+1}}}\sum _{c^{\prime }\in {\mathbb{F}}_q^{d+1}}e(-c^{\prime }\cdot z)|c^{\prime }⟩,$$

所以

$${\mathrm{QFT}}^{-1}|{\hat{c}}_{R_k}⟩=\frac{1}{\sqrt{|R_k|q^{d+1}}}\sum _{c^{\prime }\in {\mathbb{F}}_q^{d+1}}\left(\sum _{z\in R_k}e((c-c^{\prime })\cdot z)\right)|c^{\prime }⟩,$$

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

$$\text{振幅}(c)=\frac{1}{\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}}}.$$

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

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

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

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

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⟩=\sum _{x,y}{\alpha }_{x,y}e(c\cdot Z(x,y))|x,y,w_{x,y}⟩,$$

其中振幅 ${\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⟩=\sum _{(x,y):Z(x,y)=z}{\alpha }_{x,y}|x,y,w_{x,y}⟩(\text{未归一化}),$$

则

$$|{\psi }_c⟩=\sum _{z\in R_k}e(c\cdot z)|{\beta }_z⟩.$$

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

$${\mathcal{H}}^{\prime }=\mathrm{span}\{|{\beta }_z⟩:z\in R_k\}$$

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

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

$$\bar{p}=\frac{1}{q^{d+1}}\sum _c⟨{\psi }_c|E_c|{\psi }_c⟩=\frac{1}{q^{d+1}}\sum _c\mathrm{Tr}(E_c|{\psi }_c⟩⟨{\psi }_c|).$$

由于 $|{\psi }_c⟩$ 是 ${\mathcal{H}}^{\prime }$ 中的单位向量，算子不等式 $|{\psi }_c⟩⟨{\psi }_c|⪯{\Pi }_{{\mathcal{H}}^{\prime }}$ 成立（${\Pi }_{{\mathcal{H}}^{\prime }}$ 是到 ${\mathcal{H}}^{\prime }$ 的正交投影：对任意向量 $|\varphi ⟩$，$⟨\varphi |{\psi }_c⟩⟨{\psi }_c|\varphi ⟩=|⟨{\psi }_c|\varphi ⟩{|}^2\le ⟨\varphi |{\Pi }_{{\mathcal{H}}^{\prime }}|\varphi ⟩$， Cauchy–Schwarz 的直接推论）。代入求和：

$$\sum _c\mathrm{Tr}(E_c|{\psi }_c⟩⟨{\psi }_c|)\le \sum _c\mathrm{Tr}\left(E_c{\Pi }_{{\mathcal{H}}^{\prime }}\right)=\mathrm{Tr}\left({\Pi }_{{\mathcal{H}}^{\prime }}\underset{=I}{\underbrace{\sum _c{E}_c}}\right)=\mathrm{Tr}{\Pi }_{{\mathcal{H}}^{\prime }}=\dim {\mathcal{H}}^{\prime }\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$ 的奇偶性分两种情形。

5.1 奇数 $d$：$k=\frac{d+1}{2}$ 次查询达到常数成功率

设 $d$ 为奇数，取

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

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

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

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

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

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

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

$$H=VD{V}^T,V_{a,i}=x_i^a(0\le a\le k-1),D=\mathrm{diag}(y_1,\dots ,y_k).$$

验证：$(VD{V}^T{)}_{a,b}={\sum }_i{V}_{a,i}{D}_{ii}{V}_{b,i}={\sum }_i{x}_i^a{y}_i{x}_i^b={\sum }_i{y}_i{x}_i^{a+b}=z_{a+b}=H_{a,b}$。$V$ 正是 $x_1,\dots ,x_k$ 的 Vandermonde 矩阵（前 $k$ 列），由第 1.2 节的行列式公式，$x_i$ 互异给出 $\det V={\prod }_{i<j}(x_j-x_i)\ne 0$；$y_i$ 全非零给出 $D$ 可逆。故 $H$ 可逆。

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

$$\sum _{b=0}^{k-1}{H}_{a,b}{q}_b=-z_{a+k},a=0,1,\dots ,k-1$$

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

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

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

$$\sum _b{z}_{a+b}{q}_b+z_{a+k}=\sum _i{y}_i{x}_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,a=0,\dots ,k-1.$$

令 $w_i=y_{i}Q(x_i)$，上式即 ${\sum }_i{w}_i{x}_i^a=0$ 对 $a=0,\dots ,k-1$ 成立——写成矩阵即 $Vw=0$。$V$ 可逆，故 $w=0$；又 $y_i\ne 0$，所以

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

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

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

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

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

$$q(q-1)\cdots (q-k+1)=q^k\prod _{i=0}^{k-1}(1-\frac{i}{q})=q^k(1-O(1/q)),$$ $$(q-1{)}^k=q^k(1-\frac{1}{q}{)}^k=q^k(1-O(1/q)),$$

两式相乘得

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

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

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

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

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

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

5.2 偶数 $d$：$k=\frac{d}{2}+1$ 次查询达到高成功率

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

$$k=\frac{d}{2}+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)}(1+O(1/q)),$$

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

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

二阶矩的估计需要对 ${\sum }_{z}N(z{)}^2$ 展开后逐类计数满足 $Z(x,y)=Z(x^{\prime },y^{\prime })$ 的四元组 $(x,y,x^{\prime },y^{\prime })$，其主体由”$(x^{\prime },y^{\prime })$ 是 $(x,y)$ 的置换”的对角项贡献，其余项被 Vandermonde 型论证压成 $O(1/q)$ 的相对误差；具体组合细节超出本词条范围，我们引用原文结论。于是偶数次数时，$\frac{d}{2}+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,\dots ,c_d,0)$，从而得到 $c$。代价仅仅是多一次查询。

总结最优阈值：

次数 $d$	目标	最优查询数 $k$	成功概率
奇数	常数成功率	$\frac{d+1}{2}$	$\ge \frac{1}{k!}(1-O(1/q))$，常数
奇数	高成功率	$\frac{d+3}{2}$（padding 到 $d+1$）	$1-O(1/q)$
偶数	高成功率	$\frac{d}{2}+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_{1}X$。经典需要 $2$ 次查询，量子声称 $1$ 次即有常数成功率。

moment map。 $k=1$ 时

$$Z(x,y)=(y,yx)\in {\mathbb{F}}_q^2.$$

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

• 若 $z_0\ne 0$：取 $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\ne 0$）没有原像。

因此

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

成功概率为

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

与第 5.1 节公式对照。 $k=1$ 时 $k!=1$，一般公式给出 $\frac{1}{1!}(1-O(1/q))=1-O(1/q)$；我们的精确计算 $1-\frac{1}{q}+\frac{1}{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$），而求根与解线性系统在有限域上都有 $\mathrm{poly}(k,\log q)$ 的经典算法，从而可以用 $\mathrm{poly}(\log q,d)$ 个量子门可逆地实现；均匀制备的偏差只给成功率带来可忽略的损失。

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

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

7. 多变量推广

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

7.1 单项式计数

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

$${\alpha }_1+{\alpha }_2+\cdots +{\alpha }_n\le d,{\alpha }_i\ge 0$$

的非负整数向量（多重指标）$\alpha =({\alpha }_1,\dots ,{\alpha }_n)$ 的个数，记为 $M$。引入松弛变量 ${\alpha }_{n+1}=d-{\sum }_i{\alpha }_i\ge 0$，约束变为

$${\alpha }_1+\cdots +{\alpha }_n+{\alpha }_{n+1}=d.$$

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

$$M=\left(\genfrac{}{}{0ex}{}{n+d}{d}\right).$$

（具体地：$d$ 个星与 $n$ 根棒排成一列共 $\left(\genfrac{}{}{0ex}{}{n+d}{n}\right)=\left(\genfrac{}{}{0ex}{}{n+d}{d}\right)$ 种排法，第 $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⟶{\mathbb{F}}_q^M,Z(x,y{)}_{\alpha }=\sum _{i=1}^k{y}_i{x}_i^{\alpha },|\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,\text{即}k\gtrsim \frac{M}{n+1}.$$

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

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

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

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

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

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

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

一元情形 $n=1$ 时它等于 $\frac{1+d}{d}\approx 2$，与前面几节一致；但当 $n$ 增大时，加速因子 $\approx n/d$ 随变量数线性增长，而不只是一元情形的因子 2。例如固定 $d=2$、令 $n$ 增大，经典需要 $M=\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)\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 态” $|{\hat{c}}_{R_k}⟩$；对其做逆 QFT，测得正确系数的概率恰好等于 moment map 像的相对大小 $|R_k|/q^{d+1}$。同一个量也是任意 $k$ 查询算法成功概率的上界（所有输出态挤在 $|R_k|$ 维子空间内的维数论证），所以阈值问题完全化为对 $|R_k|$ 的计数。
• 奇数 $d$ 取 $k=\frac{d+1}{2}$：Hankel 矩阵分解 $H=VD{V}^T$ 保证好原像至多差一个排列，计数给出常数成功率 $\frac{1}{k!}(1-O(1/q))$；偶数 $d$ 取 $k=\frac{d}{2}+1$，二阶矩分析给出高成功率 $1-O(1/q)$；奇数 $d$ 要同级别的成功率可用 padding 多加一次查询。总之，有界错误阈值约为经典查询数的一半，并已被证明最优。
• 门复杂度上，固定 $d$ 时可用 $\mathrm{poly}(\log q,d)$ 门实现，但常数可能含 $k!$，“固定次数”是重要的参数承诺；模型要求量子叠加查询，适用于量子可访问的 MAC/秘密共享攻击，不能自动套到纯经典接口。
• 多变量推广中单项式数 $M=\left(\genfrac{}{}{0ex}{}{n+d}{d}\right)$，查询阈值约为 $M/(n+1)$（$\mathbb{C}$）到 $\lceil dM/(n+d)\rceil$（${\mathbb{F}}_q$），加速因子可随变量数 $n$ 增长，远超一元情形的 2。

习题。

1. 对 $d=1$、$k=1$，写出 $Z(x,y)=(y,yx)$，并完整计算 ${\mathbb{F}}_q$ 上哪些 $z$ 没有原像、各有几个原像（对照第 5.4 节）；验证 $|R_1|=q^2-q+1$。
2. 证明 Vandermonde 行列式公式 $\det (x_i^j{)}_{0\le i,j\le d}={\prod }_{i<j}(x_j-x_i)$。（提示：把行列式看作 $x_d$ 的多项式，用代入法找出它的全部根。）
3. 从截断 Fourier 态 $|{\hat{c}}_{R_k}⟩$ 出发，补全第 4.2 节推导的每一步，证明测得正确 $c$ 的概率为 $|R_k|/q^{d+1}$；并说明为什么对 $c^{\prime }\ne c$ 不能直接断言振幅为零。
4. 对 $k=2$、$d=3$ 具体写出第 5.1 节的 Hankel 矩阵 $H$ 与分解 $H=VD{V}^T$，验证 $(VD{V}^T{)}_{a,b}=z_{a+b}$，并说明为什么 $x_1\ne x_2$ 与 $y_1{y}_2\ne 0$ 共同保证 $H$ 可逆。
5. 解释第 5.3 节的 padding 技巧：为什么把奇数次的 $f$ 看作”最高次系数为 0 的 $d+1$ 次多项式”后，偶数情形的结论可以直接套用？这样做查询数和成功概率各是多少？
6. 对 $n=2$、$d=2$，计算单项式数 $M$，并分别算出一元推广到 $\mathbb{C}$、$\mathbb{R}$、${\mathbb{F}}_q$ 三种域上的查询上界与相对经典的加速因子。

参考文献与 Zoo 覆盖

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

---

参考资料

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