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

经典上，次数至多 $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 覆盖

- 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 下的插值/恒等测试推广。