Multivariate quantum signal processing with optimal query complexity

技术摘要：具有最优查询复杂度的多元量子信号处理

问题陈述
在量子操作中编码的多项式变换是量子算法（包括哈密顿量模拟、线性系统求解和振幅放大）的基础。虽然一元量子信号处理（QSP）允许实现查询复杂度与多项式次数呈线性关系的多项式变换，但将此扩展到多元输入仍然具有挑战性。现有的多元变换方法面临着一种权衡：它们要么只能实现受限的多项式族，要么通过组合单个单项式来实现一般多项式。后者的做法会导致查询成本随变量数量呈指数级增长，因为每个单项式都需要单独的信号查询。本研究解决的核心开放性问题是：是否可以在量子电路中高效地实现多元多项式变换，在支持一般多项式族的同时，实现针对每个变量的线性最优查询复杂度。

方法论
作者提出了一种能够实现显式归一化因子约束下的多元三角多项式的量子电路结构。其核心方法论涉及一种相干处理策略，旨在避免单项式逐个构建带来的指数级开销：

1. 基于频率的分解： 对于多元多项式 $P(x_1, \dots, x_N)$，电路将其中一个变量（例如 $x_N$）视为一元 QSP 序列的主要输入。其余变量（$x_1, \dots, x_{N-1}$）则按其频率分量进行组织。
2. 相干分支： 电路利用辅助寄存器以叠加态存储频率标签 $\mu$。这些标签的振幅由多项式分支的系数范数决定。
3. 共享查询： 电路在所有频率分支上同时对最后一个变量 $x_N$ 执行一元三角 QSP 序列。通过受控置换和共轭查询，将对应于其他变量的相位因子印刻在频率寄存器上。
4. 酉扩展： 对于对易酉算符 $U = (U_1, \dots, U_N)$，标量信号 $x_j$ 被替换为特征相位。电路使用受控 Oracle $C_0(U_j)$ 和 $C_1(U_j)$（受控-$U_j^\dagger$ 和 受控-$U_j$）。通过平衡正向和反向查询的数量，电路实现了酉算子的洛朗多项式，并在共享特征基底上同时应用变换。

主要贡献

1. 最优查询复杂度： 本文提出了一种电路，其中每个变量 $x_j$ 被查询的次数恰好为 $L_j$，其中 $L_j$ 是该变量对应的多项式次数。这达到了任何具有相同输入访问权限的电路的下界，证明了其查询复杂度是最优的。
2. 一般多项式类： 不同于受限于特定子集的以往方法，该构造实现了属于系数 $\ell_1$-范数有界类（以及分支的松弛上确界范数条件）内的每一个多元三角多项式。
3. 下界证明： 作者提供了严格的证明（命题 4 和 7），表明查询次数是一个必要的下界。该结论是通过信号门对结果多项式指数所施加的奇偶性和次数约束推导得出的。
4. 学习模型分析： 该电路被分析为一个参数化量子学习模型，具有固定的制备过程和可训练的旋转角度。作者推导了均匀初始化下的梯度方差下界，表明在特定的多项式缩放条件下，方差与查询深度和分支权重的平方根成反比，从而避免了“贫瘠高原”（梯度指数级消失）现象。

结果

• 标量信号： 定理 3 确立了对于 $N$ 个标量输入且次数为 $L = (L_1, \dots, L_N)$ 的情况，该电路使用恰好 $L_j$ 次对 $R_z(x_j)$ 的查询来模拟目标多项式。旋转门的数量与变量个数和次数呈多项式相关，具体受限于 $O((L+2)(L+1)^{N-1})$。
• 对易酉算符： 定理 5 将结果扩展到对易酉算符，实现了正向（$U_j$）和反向（$U_j^\dagger$）查询的最优查询计数，匹配了多项式的正向和负向方向次数。
• 梯度方差： 定理 9 和推论 10 表明，对于查询深度 $L_N \ge 2$，独立均匀初始化产生的梯度方差下界为 $\Omega(|a_\mu|^4 / \sqrt{L_N})$。只要分支权重不呈指数级衰减，该界限在数据态和维度上均保持一致。
• 监督学习： 定理 11 提供了监督平方损失下初始化梯度方差的界限，将其与目标均值以及目标与输入第一谱矩之间的相关性联系起来。

意义与主张
本文声称提供了第一个能够在指定类别的每一个多项式及任意变量数量下，达到查询复杂度理论下界的构造。通过在频率分量上相干地处理一个变量，该方法允许所有分量共享相同的信号查询，从而消除了以往基于单项式方法的指数级查询成本。

作者强调，其方法为开发多元量子算法和学习模型提供了一种可扩展且实用的解决方案。作者指出，虽然并发工作 [16] 通过解析传递函数处理非对易矩阵，但本文直接将多元多项式转化为具有所述多项式类最优查询复杂度的显式电路。研究结果表明，只要利用所提出的频率相干架构来处理多项式结构，处理多个信号所付出的每个信号的查询成本并不比处理单个信号更多。