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

经典上，次数至多 \(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 群上的量子傅里叶变换（见量子傅里叶变换）；本课会直接使用这些工具而不再重新推导。

本课知识点

  1. 插值问题与经典基线——能写出 value oracle 模型与插值目标，并用 Vandermonde 方程和相容候选构造论证经典查询数恰为 \(d+1\) 次。

  2. 加法特征与相位反冲——能由域迹定义加法特征并验证其正交关系，再通过换元推导 Fourier 基态上一次 value query 等价于一次相位查询。

  3. 矩曲线与 moment map——能把 \(k\) 次查询的总相位指数整理成内积 \(c\cdot Z(x,y)\)，并解释 \(Z\) 值相同的查询历史为何不可区分。

  4. 截断 Fourier 态与成功率——能写出制备截断 Fourier 态的三步算法，并推导测得正确系数的概率恰好等于 \(|R_k|/q^{d+1}\)。

  5. 最优性的维数论证——能证明任意 \(k\) 查询算法的全部输出态落在至多 \(|R_k|\) 维的子空间内，从而成功概率不超过 \(|R_k|/q^{d+1}\)。

  6. 奇数次数的最优阈值——能用 Hankel 分解 \(H=VDV^T\) 证明好原像至多相差一个排列，并计数得出 \(k=\frac{d+1}{2}\) 时的常数成功率。

  7. 偶数次数与 padding 统一——能解释二阶矩方法如何给出 \(1-O(1/q)\) 的成功率，并用 padding 技巧统一奇偶两种次数的查询阈值。

  8. 多变量推广与加速因子——能计算单项式个数 \(M=\binom{n+d}{d}\) 并写出多变量 moment map，比较三种域上的查询阈值与随 \(n\) 增长的加速因子。

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\) 个等式可以写成矩阵形式

\[\begin{split} \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}. \end{split}\]

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|\) 的大小，定出最优阈值。

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

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

验证：\(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\) 整齐地重新组织。

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 节成功率公式与最优性证明的共同根源。

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|\) 决定。）

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\) 的奇偶性分两种情形。

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))\)，即上式在渐近意义下是等式而非仅仅下界；对本课的目的，常数成功率已达下界要求。）

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 或秘密共享方案的攻击是有意义的——例如认证标签由隐藏多项式逐点计算、且实现该计算的设备可能被置于相干查询的场景。但它不能自动套用到只允许经典请求—响应交互的协议接口上：如果协议的实现环境强制每次查询都是经典的（例如远端服务器只接受经典输入），相位反冲无从发生，全部结论失效。评估这类攻击的现实性时，必须先确认目标接口是否真的允许叠加查询。

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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 覆盖