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

经典上，次数至多 \(d\) 的一元多项式有 \(d+1\) 个系数，必须查询 \(d+1\) 个不同点才能恢复。量子查询可同时把多个函数值写入一个关于全部系数的相位态，最优阈值降到约 \((d+1)/2\) 次。本课推导 moment map

\[ Z(x,y)_j=\sum_i y_i x_i^j \]

如何出现，为什么算法成功率恰好等于其像的相对大小，并说明多变量情形的加速因子为何可超过 2。

1. 问题与经典下界

设 \(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. \]

目标是输出系数向量 \(c=(c_0,\ldots,c_d)\)。经典查询 \(d+1\) 个不同点得到 Vandermonde 方程

\[ Vc=(f(x_0),\ldots,f(x_d))^T, \]

\(V\) 可逆，故 \(d+1\) 次充分。少一次时仍有一个自由系数，对随机 \(f\) 即使允许有界错误也不能唯一确定，所以同样必要。

2. 一次 value query 等价于相位 query

令域迹 \(\operatorname{Tr}:\mathbb F_q\to\mathbb F_p\)，加法特征

\[ e(z)=\exp(2\pi i\operatorname{Tr}(z)/p). \]

把答案寄存器置于 Fourier 基态，标准 phase kickback 给出

\[ |x,y\rangle \longmapsto e(yf(x))|x,y\rangle. \]

\(k\) 个并行相位查询对 \(x,y\in\mathbb F_q^k\) 产生总相位

\[ e\!\left(\sum_{i=1}^k y_i f(x_i)\right). \]

展开 \(f\)：

\[ \sum_i y_if(x_i) =\sum_{j=0}^d c_j \left(\sum_i y_ix_i^j\right) =c\cdot Z(x,y), \]

其中

\[ Z(x,y)= \left(\sum_i y_i, \sum_i y_ix_i,\ldots, \sum_i y_ix_i^d\right). \]

一次量子查询不再只是给出一个点值，而是贡献一条带权 moment curve 向量 \((1,x,x^2,\ldots,x^d)\)。

3. 算法如何构造“截断 Fourier 态”

记 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)\)，这些代表构成 \(T_k\)，使 \(Z:T_k\to R_k\) 为双射。制备 \(T_k\) 上均匀叠加、做 \(k\) 次相位查询，再可逆计算 \(Z\)，得到

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

若 \(R_k\) 是整个系数空间，这正是 \(|c\rangle\) 的 Fourier 变换；一般它只是截断版本。对其做 \(\mathbb F_q^{d+1}\) 逆 QFT，测得正确 \(c\) 的概率为

\[ \left| \frac1{\sqrt{|R_k|q^{d+1}}} \sum_{z\in R_k}1 \right|^2 =\frac{|R_k|}{q^{d+1}}. \]

更强的是：任意 \(k\) 查询量子算法的最大成功概率也不超过这个数。原因是所有可能输出态都落在由 \(R_k\) 标签张成的 \(|R_k|\) 维子空间，而待区分多项式共有 \(q^{d+1}\) 个；这是一个秩/维数下界。

4. 最优查询阈值

当 \(d\) 为奇数并取

\[ k=\frac{d+1}{2}, \]

若 \(x_i\) 互异且 \(y_i\ne0\)，Vandermonde 线性无关性说明同一 \(z\) 的好原像只相差 \(k!\) 个排列。因此

\[ \frac{|R_k|}{q^{d+1}} =\frac1{k!}\bigl(1-O(1/q)\bigr), \]

对固定 \(d\) 是常数成功率，并达到已知下界。

当 \(d\) 为偶数，取

\[ k=\frac d2+1 \]

后，二阶矩分析表明几乎每个 \(z\) 都有原像：

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

对奇数 \(d\) 若也希望成功率趋近 1，可把 \(f\) 看作最高次系数为 0 的 \(d+1\) 次多项式并再增加一次查询。总之，有界错误阈值约为经典查询数的一半，精确取整和成功率取决于 \(d\) 的奇偶性。

5. 能否真正高效实现 \(T_k\)？

查询算法形式上要求均匀制备代表集 \(T_k\) 并可逆求 moment map 原像。对固定 \(d\)，可把 \(Z(x,y)=z\) 化为一个低次多项式方程和 Vandermonde 线性系统，从而用 \(\operatorname{poly}(\log q,d)\) 门实现，成功率只损失可忽略量。高成功率版本对 \(d\) 的常数可能包含 \(k!\)，所以“固定次数”是重要参数承诺。

该模型允许对消息点的量子叠加查询。因此它对量子可访问的 MAC 或秘密共享攻击有意义，但不能自动套到只允许经典请求--响应的协议接口。

6. 多变量推广

\(n\) 变量总次数至多 \(d\) 的单项式数为

\[ M=\binom{n+d}{d}. \]

经典需要 \(M\) 次查询。多变量 moment map 用多重指标 \(\alpha\)：

\[ Z(x,y)_\alpha =\sum_{i=1}^k y_i x_i^\alpha, \qquad |\alpha|\le d. \]

对 \(\mathbb C\)，除少数低次例外，约

\[ \left\lceil\frac M{n+1}\right\rceil \]

次查询可成功率 1；\(\mathbb R\) 约需其两倍；有限域上已证明接近

\[ \left\lceil\frac d{n+d}M\right\rceil \]

次在大 \(q\) 时高成功。因此多变量加速因子可随 \(n\) 增长，而不只是一元情形的 2。

7. 小结与习题

  • phase query 把 \(k\) 个函数值合成关于全体系数的线性相位。

  • moment map 的像 \(R_k\) 决定可区分输出空间，最优成功率恰为 \(|R_k|/q^{d+1}\)。

  • 约一半经典查询即可有界错误恢复一元多项式；奇偶次数决定取整与高成功阈值。

  • 多变量问题的查询优势可达变量数级，但门复杂度仍依赖求解 moment 方程。

  1. 对 \(d=1,k=1\) 写出 \(Z(x,y)=(y,yx)\)，计算哪些 \(z\) 没有原像。

  2. 证明 \(d+1\) 个不同点的 Vandermonde 矩阵可逆。

  3. 从截断 Fourier 态推导测得 \(c\) 的概率。

  4. 对 \(n=2,d=2\) 计算 \(M\) 及三种域上的查询上界。

参考文献与 Zoo 覆盖