量子信号处理（QSP）详解：精确多项式变换的量子引擎¶
量子信号处理（Quantum Signal Processing, QSP）由 Guang Hao Low 和 Isaac Chuang 于 2017 年提出，是量子计算中最精确、最通用的矩阵函数逼近工具之一。它的核心结论是：由"信号旋转"与"相位旋转"交替构成的单量子比特电路，其矩阵元素恰好是信号参数 \(x\) 的多项式；反之，任何满足幅值约束的多项式都能被这样的电路精确实现，且所需信号旋转次数等于多项式次数，达到信息论下界。
问题背景¶
在量子算法中，一个反复出现的需求是：给定酉算符 \(U\)（特征值 \(e^{i\phi_k}\)），构造一个新的酉算符 \(V\)，使得 \(V\) 在 \(U\) 的每个特征子空间上的作用对应于某个目标函数 \(f\)。
具体来说，给定 \(W = W(A)\)（由 Qubitization 构造的量子行走酉算符，特征值为 \(e^{\pm i\theta_j}\)，且 \(\cos\theta_j = \sigma_j/\alpha\)，其中 \(\sigma_j\) 是 \(A\) 的奇异值、\(\alpha\) 是块编码的归一化常数），我们的目标是构造投影意义下的矩阵函数
其中 \(P\) 是目标多项式，\(\Pi\) 是到信号子空间的投影。
经典方法的局限：
Trotter 分解：精度受限于分解阶数，无法精确实现多项式变换；
LCHS（线性组合哈密顿量模拟）：依赖 Taylor 展开与后选择，成功概率随精度要求衰减；
奇异值分解加经典后处理：测量开销大。
QSP 提供了一种无需后选择、深度最优、误差精确可控的方案。
核心思想：单量子比特旋转序列¶
QSP 的核心观察极为简洁：一系列交替的单量子比特旋转，其整体效果等价于一个关于信号参数的多项式变换。
信号矩阵与相位矩阵¶
定义信号矩阵（signal matrix）
与相位矩阵（phase matrix）
\(W(x)\) 是酉的：两行分别为 \((x,\, i\sqrt{1-x^2})\) 与 \((i\sqrt{1-x^2},\, x)\)，行内积为 \(x\cdot(-i\sqrt{1-x^2}) + i\sqrt{1-x^2}\cdot x = 0\)，行范数平方为 \(x^2 + (1-x^2) = 1\)。若令 \(x = \cos\phi\)，则 \(W(x) = \cos\phi\, I + i\sin\phi\, X = e^{i\phi X}\)，即信号参数 \(x\) 正是"信号旋转"特征相位的余弦。Low–Chuang（2017）的原始约定（信号取 \(e^{i\phi Z}\)、处理器取 \(X\) 旋转）与本节约定相差一个整体的 Hadamard 基变换，两种约定下的可达多项式集合一致；本文采用与 QSVT 文献一致的 \(X\)-信号、\(Z\)-处理器约定。
QSP 序列的定义¶
\(d\) 阶 QSP 序列（相位参数 \(\vec{\Phi} = (\Phi_0, \Phi_1, \ldots, \Phi_d)\)）定义为
即 \(d\) 次"信号旋转"与 \(d+1\) 次"处理器相位旋转"交替施加。
QSP 多项式与矩阵形式¶
定理（QSP 矩阵形式）：对任意 \(\vec{\Phi} \in \mathbb{R}^{d+1}\)，存在多项式对 \((P, Q)\)，使得
其中记号 \(P^{*}(x) := \overline{P(\bar x)}\) 表示系数取复共轭的多项式（在实轴上即通常的复共轭函数）。多项式 \(P\) 满足 \(\deg P \le d\) 且奇偶性与 \(d\) 相同；\(Q\) 满足 \(\deg Q \le d-1\) 且奇偶性与 \(d-1\) 相同；并且 \(U_{\text{QSP}}\) 的酉性等价于
注意矩阵的四个元素中，反对角上出现的正是 \(\sqrt{1-x^2}\) 因子乘以 \(Q(x)\) 与其共轭 \(Q^{*}(x)\)——这一结构对下文的推导至关重要。定理的证明（以及更强的逆命题）见"理论推导"一节。
关键结论（可达集）：多项式 \(P\) 可以作为某个 \(d\) 阶 QSP 序列的 \((0,0)\) 元素，当且仅当下列四个条件同时成立：
\(\deg P \le d\)，且 \(P\) 的奇偶性与 \(d\) 相同；
\(|P(x)| \le 1\) 对一切 \(x \in [-1,1]\) 成立；
\(|P(1)| = |P(-1)| = 1\)（端点条件）；
若条件 3 不满足，则 \(P\) 需要改用双投影子形式的 QSVT 实现（见下）。
端点条件的必要性有一行证明：\(W(1) = I\)、\(W(-1) = -I\)，于是 \(U_{\text{QSP}}(\vec\Phi; 1) = S(\sum_{k=0}^d\Phi_k)\)、\(U_{\text{QSP}}(\vec\Phi; -1) = (-1)^d S(\sum_{k=0}^d\Phi_k)\)，两者都是对角酉阵，其 \((0,0)\) 元素的模长必为 \(1\)。实践中常见的目标自动满足端点条件：例如哈密顿量模拟的目标 \(e^{-i\tau x}\) 在 \(x = \pm1\) 处模长为 \(1\)。对不满足端点条件的目标（如归一化后的求逆多项式 \(1/(\kappa x)\)），应使用 QSVT 的双投影子形式，那里信号空间没有退化的端点，可达集仅为条件 1 与 2。
数学基础：切比雪夫多项式¶
QSP 的数学结构与切比雪夫多项式（Chebyshev polynomial）天然耦合。
切比雪夫多项式的定义¶
第一类切比雪夫多项式：
第二类切比雪夫多项式：
关键性质：\(|T_n(x)| \le 1\)（\(x \in [-1, 1]\)），且 \(T_n\) 在 \([-1, 1]\) 上恰好振荡 \(n\) 次、在 \(n+1\) 个极值点达到 \(\pm 1\)。
两条乘积恒等式¶
下文推导会用到两条把 \(T_n\) 与 \(U_n\) 联系起来的恒等式，我们先用三角加法公式验证。对 \(n \ge 2\)，令 \(x = \cos\theta\)：
恒等式 A：\(T_n(x) = x\,T_{n-1}(x) - (1-x^2)\,U_{n-2}(x)\)。
验证：右端 \(= \cos\theta\cos((n-1)\theta) - \sin^2\theta\,\dfrac{\sin((n-1)\theta)}{\sin\theta} = \cos\theta\cos((n-1)\theta) - \sin\theta\sin((n-1)\theta)\)，由余弦差公式 \(\cos(a+b) = \cos a\cos b - \sin a\sin b\)，这恰为 \(\cos(n\theta) = T_n(\cos\theta)\)。
恒等式 B：\(U_{n-1}(x) = T_{n-1}(x) + x\,U_{n-2}(x)\)。
验证：右端 \(= \cos((n-1)\theta) + \cos\theta\,\dfrac{\sin((n-1)\theta)}{\sin\theta} = \dfrac{\cos((n-1)\theta)\sin\theta + \cos\theta\sin((n-1)\theta)}{\sin\theta}\)，由正弦和公式 \(\sin(a+b) = \sin a\cos b + \cos a\sin b\)，分子为 \(\sin(n\theta)\)，故右端 \(= \dfrac{\sin(n\theta)}{\sin\theta} = U_{n-1}(\cos\theta)\)。
QSP 与切比雪夫的关系¶
最直接的例子是全零相位 \(\vec\Phi = \vec 0\)：此时 \(U_{\text{QSP}} = W(x)^d\)。我们断言
对 \(d\) 归纳：\(d = 1\) 时 \(W = \begin{pmatrix} x & i\sqrt{1-x^2}\\ i\sqrt{1-x^2} & x\end{pmatrix}\)，而 \(T_1 = x\)、\(U_0 = 1\)，成立。设 \(d-1\) 时成立，则 \(W^d = W^{d-1}\cdot W\)，用下文引理 1 的乘积公式（取 \((P_1,Q_1) = (T_{d-1},U_{d-2})\)、\((P_2,Q_2) = (x,1)\)）得新的 \(P = xT_{d-1} - (1-x^2)U_{d-2}\)、\(Q = T_{d-1} + xU_{d-2}\)，由恒等式 A、B 分别等于 \(T_d\) 与 \(U_{d-1}\)，归纳完成。
这个例子同时给出了切比雪夫恒等式 \(T_d^2 + (1-x^2)U_{d-1}^2 = 1\) 的酉性证明（与定理的约束条件一致），并说明切比雪夫多项式是 QSP 最"自然"的基：一般的可行多项式 \(P\)（次数 \(\le d\)、奇偶性与 \(d\) 相同）都可展开为 \(\sum_{k \le d,\; k \equiv d \!\!\pmod 2} a_k T_k\)，QSP 相位的功能就是把这组系数"编织"进电路。
算法步骤详解¶
第一步：确定目标多项式¶
根据应用确定目标多项式 \(P(x)\)（必要时先归一化使 \(|P|\le 1\)）：
哈密顿量模拟：\(P(x) = e^{-i\tau x}\) 的切比雪夫逼近，\(\tau = \alpha t\)；
矩阵求逆：\(P(x) \approx 1/(\kappa x)\)（\(x \in [1/\kappa, 1]\)，已含 \(1/\kappa\) 归一化）；
量子搜索：\(P\) 在目标信号 \(x = \sigma_{\text{target}}\) 附近取值接近 \(1\)、其余处接近 \(0\) 的"峰形"多项式。
若目标不具备确定奇偶性（如 \(e^{-i\tau x}\)），把它拆成偶部与奇部（\(\cos\tau x\) 与 \(-i\sin\tau x\)），分别用两条 QSP 序列实现，再用一个附加辅助比特做线性组合，代价只增加常数因子。
第二步：多项式到相位参数的转换¶
给定 \(d\) 次多项式 \(P(x)\)，求相位参数 \(\vec{\Phi} = (\Phi_0, \Phi_1, \ldots, \Phi_d)\) 使得：
方法一：代数方法（Haah, 2019）
将 \(P(x)\) 表示为切比雪夫展开 \(P(x) = \sum_k a_k T_k(x)\)。Haah 给出了从系数 \(\{a_k\}\) 直接计算 \(\vec{\Phi}\) 的解析算法，复杂度 \(O(d^2)\)。
方法二：迭代优化
利用 \(U_{\text{QSP}}\) 对 \(\vec{\Phi}\) 的可微性，通过梯度下降或 Levenberg–Marquardt 迭代求解。优点是通用性好，缺点是可能陷入局部最优。
方法三：直接构造（对特殊多项式）
对切比雪夫多项式 \(T_d(x)\)，相位参数有显式解：全零相位
即可，因为此时 \(U_{\text{QSP}} = W(x)^d\)，由上一节的结论其 \((0,0)\) 元恰好为 \(T_d(x)\)（互补多项式为 \(Q = U_{d-1}\)）。更一般地，由引理 1 的共轭公式 \(S(\phi_1)\,\mathcal{M}(P,Q)\,S(\phi_2) = \mathcal{M}\big(Pe^{i(\phi_1+\phi_2)},\, Qe^{i(\phi_1-\phi_2)}\big)\)，任何"\(W\) 的幂乘两端相位"型的多项式都有闭式解。
第三步：构造量子电路¶
将 QSP 序列转化为量子门电路。在实际量子算法中，"信号旋转" \(W(x)\) 对应于一次 Qubitization 行走算符 \(W'(A) = U_A R_0\) 的调用：在它的每个二维不变平面上，\(W'(A)\) 的作用等价于信号矩阵（Qubitization 教程"理论推导"第四步给出了精确的基变换对应）。
电路结构：
其中 \(\widetilde{Z} = R_0 = 2|0\rangle\langle0|^{\otimes m} - I\) 是块编码辅助寄存器上的反射算子，它在每个不变平面上恰好表现为单量子比特的 \(Z\)（Qubitization 教程已逐项验证）。\(e^{i\Phi_k\widetilde Z} = \cos\Phi_k\, I + i\sin\Phi_k\, R_0\) 由一次多控相位旋转实现，代价 \(O(m)\) 个门；\(W'(A)\) 的代价由块编码决定（对 \(L\) 项泡利 LCU 为 \(O(Ln + C_{\text{PREP}})\)）。总深度为 \(O(d)\) 次 \(W'(A)\) 调用。
第四步：在目标子空间上提取结果¶
QSP 作用在辅助量子比特与系统量子比特的联合空间上。把 Qubitization 教程的转移矩阵恒等式推广到交错序列（同教程"理论推导"第四步），我们得到精确的算符恒等式
即对每个奇异值 \(\sigma_j\)，\(P(\sigma_j/\alpha)\) 被自动施加——量子并行性同时处理所有奇异值，无需任何后选择。
理论推导¶
本节给出 QSP 表示定理的完整证明。证明的主干是三条引理：引理 1 建立矩阵形式（正向：相位 \(\to\) 多项式）；引理 2 是"剥层引理"，给出相邻两层可行多项式对之间的显式递推（反向：多项式 \(\to\) 相位）；引理 3 保证伴随多项式存在。三者拼起来即得完整的表示定理。
记号与函数类¶
全文记 \(s := \sqrt{1-x^2}\)，并对每个多项式 \(P(x) = \sum_k p_kx^k\) 记 \(P^{*}(x) := \overline{P(\bar x)} = \sum_k \overline{p_k}\,x^k\)（\(P\) 是实系数多项式时 \(P^* = P\)）。
定义（可行对）：称多项式对 \((P, Q)\) 是层数 \(d\) 的可行对，如果：
(i) \(\deg P \le d\)，且 \(P\) 的每一项次数与 \(d\) 同奇偶；
(ii) \(\deg Q \le d-1\)，且 \(Q\) 的每一项次数与 \(d-1\) 同奇偶；
(iii) \(|P(x)|^2 + (1-x^2)|Q(x)|^2 = 1\) 对一切 \(x \in [-1,1]\) 成立。
对每个多项式对 \((P,Q)\)，定义矩阵值函数
引理 1：矩阵形式与封闭性¶
引理 1：(a) 乘积公式。对任意两个多项式对，
(b) 特殊因子。\(W(x) = \mathcal{M}(x, 1)\)，\(S(\phi) = \mathcal{M}(e^{i\phi}, 0)\)。
(c) 酉性。\(\mathcal{M}(P,Q)\)（在每个固定的 \(x\) 处）是酉矩阵，当且仅当 \(|P|^2 + s^2|Q|^2 = 1\)。
证明：(a) 逐项做矩阵乘法。\((0,0)\) 元为
\((0,1)\) 元为
再验证所得矩阵确有 \(\mathcal M\) 的形状：\((1,1)\) 元 \(= isQ_1^{*}\cdot isQ_2 + P_1^{*}P_2^{*} = (P_1P_2 - s^2Q_1Q_2^{*})^{*}\) ✓（对第一项逐系数取共轭即得）；\((1,0)\) 元 \(= isQ_1^{*}P_2 + P_1^{*}\cdot isQ_2^{*} = is(P_1Q_2 + Q_1P_2^{*})^{*}\) ✓。
(b) 直接对照定义：\(\mathcal M(x,1) = \begin{pmatrix}x & is\\ is & x\end{pmatrix} = W(x)\)；\(\mathcal M(e^{i\phi},0) = \mathrm{diag}(e^{i\phi}, e^{-i\phi}) = S(\phi)\)。
(c) 两行 \((P,\, isQ)\) 与 \((isQ^{*},\, P^{*})\) 的内积为 \(P\cdot(isQ^{*})^{*} + isQ\cdot(P^{*})^{*} = -isPQ + isQP = 0\)，故行正交；行范数平方为 \(|P|^2 + s^2|Q|^2\)，等于 \(1\) 当且仅当 (iii) 成立。\(\blacksquare\)
次数与奇偶性的记账：若 \((P_1,Q_1)\)、\((P_2,Q_2)\) 分别满足层数 \(d_1\)、\(d_2\) 的次数与奇偶性约束 (i)(ii)，则由乘积公式，\(P_1P_2\) 的每项次数 \(\equiv d_1 + d_2 \pmod 2\)、次数 \(\le d_1+d_2\)；\(s^2Q_1Q_2^{*} = (1-x^2)Q_1Q_2^{*}\) 的每项次数 \(\equiv 2 + (d_1-1)+(d_2-1) \equiv d_1+d_2 \pmod 2\)、次数 \(\le d_1+d_2\)；\(P_1Q_2 + Q_1P_2^{*}\) 每项次数 \(\equiv d_1+d_2-1\)、次数 \(\le d_1+d_2-1\)。故乘积满足层数 \(d_1+d_2\) 的约束。
推论（QSP 矩阵形式）：\(U_{\text{QSP}}(\vec\Phi;x) = \mathcal M(e^{i\Phi_0},0)\prod_{k=1}^d\mathcal M(xe^{i\Phi_k},\, e^{-i\Phi_k})\)，其中每个因子 \(\mathcal M(xe^{i\Phi_k}, e^{-i\Phi_k})\) 满足层数 1 的约束（\(WS(\Phi_k)\) 的显式展开，直接相乘即可验证：\(WS(\Phi) = \begin{pmatrix} xe^{i\Phi} & ise^{-i\Phi} \\ ise^{i\Phi} & xe^{-i\Phi}\end{pmatrix}\)）。由上述记账，\(U_{\text{QSP}} = \mathcal M(P,Q)\) 且 \((P,Q)\) 满足层数 \(d\) 的 (i)(ii)；又 \(U_{\text{QSP}}\) 是酉矩阵之积、酉，由 (c) 得 (iii)。这正是"QSP 多项式与矩阵形式"一节的定理。
引理 2：剥层（降次）引理¶
引理 2：设 \((P, Q)\) 是层数 \(d \ge 1\) 的可行对，且 \(\deg P = d\)。记 \(p_d\)、\(q_{d-1}\) 分别为 \(P\)、\(Q\) 的最高次系数。则：
(a) \(\deg Q = d-1\) 且 \(|p_d| = |q_{d-1}| \ne 0\)；
(b) 取相位 \(\Phi_d\) 满足 \(e^{2i\Phi_d} = p_d / q_{d-1}\)，并定义
则 \((P', Q')\) 是层数 \(d-1\) 的可行对，且 \((P, Q)\) 与 \((P', Q')\) 之间满足正向递推
(c) 若 \(\deg P \le d - 2\)（由奇偶性此时 \(\deg P \le d-2\) 与 \(\deg Q \le d-3\) 自动一致），则 \((P,Q)\) 本身就是层数 \(d-2\) 的可行对。
证明：(a) 把约束 (iii) 的左端展开为多项式：\(|P|^2 = P P^{*}\) 的最高次项为 \(|p_d|^2x^{2d}\)；\((1-x^2)|Q|^2 = -(q_{d-1}q_{d-1}^{*})x^{2d} + \cdots\)（若 \(\deg Q \le d-2\) 则此项不存在）。右端是常数 \(1\)，故 \(x^{2d}\) 系数必须为零：\(|p_d|^2 - |q_{d-1}|^2 = 0\)。若 \(q_{d-1} = 0\) 则 \(p_d = 0\)，与 \(\deg P = d\) 矛盾，故两者皆非零且模相等。
(b) 分三步验证。
第一步（逆映射的正确性）：把 \(P', Q'\) 的定义式代入正向递推的右端。对 \(P\)：
对 \(Q\)：
两式说明 \(\binom{P}{Q} = A\binom{P'}{Q'}\) 的系数矩阵 \(A = \begin{pmatrix} e^{i\Phi}x & -e^{i\Phi}(1-x^2)\\ e^{-i\Phi} & e^{-i\Phi}x \end{pmatrix}\) 与定义式给出的逆矩阵互逆——也可直接验证 \(\det A = x^2 + (1-x^2) = 1\)。
第二步（约束保持）：对任意 \(x \in [-1,1]\)，记 \(c = e^{2i\Phi_d}\)、\(\rho := \mathrm{Re}\big(c\,\overline{P(x)}\,Q(x)\big)\)。展开（利用 \(\overline{e^{-i\Phi}P}\cdot e^{i\Phi}Q = e^{2i\Phi}\overline{P}Q\)）：
于是
末步用了 \((P,Q)\) 的可行性。注意交叉项 \(2x(1-x^2)\rho\) 与 \(-2x(1-x^2)\rho\) 恰好相消——这一步对任何相位 \(\Phi_d\) 都成立，相位的选取只影响次数。
第三步（次数与奇偶性）：\(P'\) 的两个加项 \(xP\) 与 \((1-x^2)Q\) 的次数都 \(\le d+1\)，且每项次数 \(\equiv d+1 \equiv d-1 \pmod 2\)，故 \(P'\) 有正确的奇偶性。其 \(x^{d+1}\) 系数为
（末步用了 \(e^{2i\Phi_d} = p_d/q_{d-1}\)，故 \(p_d - e^{2i\Phi_d}q_{d-1} = p_d - p_d = 0\)）。消去 \(x^{d+1}\) 后，\(x^{d}\) 项被奇偶性排除，故 \(\deg P' \le d-1\)。同理 \(Q'\) 的两个加项 \(P\) 与 \(xQ\) 每项次数 \(\equiv d \equiv d-2 \pmod 2\)，其 \(x^d\) 系数为
（同一个条件），故 \(\deg Q' \le d-1\)；再由奇偶性 \(\equiv d-2 \pmod 2\) 排除 \(x^{d-1}\) 项，得 \(\deg Q' \le d-2\)。三步合并即得 (b)。
(c) 层数 \(d\) 与层数 \(d-2\) 的奇偶性约束模 \(2\) 完全相同，次数约束在 \(\deg P\le d-2\)、\(\deg Q \le d-3\) 下自动满足后者，约束 (iii) 不变。\(\blacksquare\)
引理 2 的直观含义是：从可行对 \((P,Q)\) 中"剥去"最外层信号旋转 \(W\) 与相位旋转 \(S(\Phi_d)\)（即引理 1 乘积公式中乘去因子 \(\mathcal M(xe^{i\Phi_d}, e^{-i\Phi_d})\)），剩下的仍是可行对，且层数恰降一层；相位的选取由"最高次系数配平"\(e^{2i\Phi_d} = p_d/q_{d-1}\) 唯一确定到 \(\pi\) 的整数倍。
引理 3：伴随多项式的存在性¶
引理 3：设 \(P\) 是奇偶性与 \(d\) 相同、\(\deg P \le d\) 的复系数多项式，满足 \(|P(x)| \le 1\)（\(x\in[-1,1]\)）且 \(|P(\pm1)| = 1\)。则存在奇偶性与 \(d-1\) 相同、\(\deg Q \le d-1\) 的多项式 \(Q\)，使 \((P, Q)\) 是层数 \(d\) 的可行对。
证明思路（本引理的完整证明需要经典的 Fejér–Riesz 谱分解定理，这里给出精确的归约步骤）：
定义 \(g(x) := 1 - P(x)P^{*}(x)\)。它是次数 \(\le 2d\)、偶奇偶性的多项式，在 \([-1,1]\) 上 \(g \ge 0\)，且由端点条件 \(g(\pm1) = 0\)，故 \(g\) 被 \((1-x^2)\) 整除：\(g = (1-x^2)h\)，其中 \(h \ge 0\) 于 \([-1,1]\)、\(\deg h \le 2d-2\)。
作变量代换 \(x = \cos\theta\)、\(z = e^{i\theta}\)，则 \(h(\cos\theta)\) 是关于 \(z\) 的次数 \(\le 2d-2\) 的非负三角多项式。由 Fejér–Riesz 定理，存在次数 \(\le 2d-2\) 的多项式 \(r(z)\) 使 \(h(\cos\theta) = |r(e^{i\theta})|^2\)。
利用 \(h\) 的偶奇偶性与 Laurent 展开中只含 \(z^{\pm(d-1)}, z^{\pm(d-3)}, \ldots\) 型频率的结构，可把 \(r\) 对称化并重新组装出一个次数 \(\le d-1\)、奇偶性与 \(d-1\) 相同的多项式 \(Q\)，使 \(|Q(\cos\theta)|^2 = h(\cos\theta)\)，从而 \((1-x^2)|Q|^2 = g\)，即 \((P,Q)\) 可行。
其中第 3 步是对称化整理的标准簿记工作，逐项对比 \(z\) 的幂次即可完成。\(\blacksquare\)
定理：QSP 表示定理¶
定理：多项式 \(P\) 满足"关键结论"一节的条件 1–3（奇偶性、\(\deg P \le d\)、\(|P|\le 1\)、\(|P(\pm1)| = 1\)）当且仅当存在相位 \(\vec\Phi \in \mathbb{R}^{d+1}\) 使 \([U_{\text{QSP}}(\vec\Phi)]_{00} = P(x)\)。且此时互补元素为 \([U_{\text{QSP}}]_{01} = i\sqrt{1-x^2}\,Q(x)\)，\((P,Q)\) 是可行对。
证明：（必要性方向即引理 1 的推论，已证。）下证存在性，分两步。
第一步（多项式到可行对）：由引理 3，存在 \(Q\) 使 \((P,Q)\) 是层数 \(d\) 的可行对。
第二步（可行对到相位，对层数归纳）：我们证明命题 \(\mathrm{H}(n)\)："每个层数 \(n\) 的可行对都可由长度 \(n\) 的 QSP 序列实现，即存在 \(\vec\Phi\) 使 \(U_{\text{QSP}}(\vec\Phi) = \mathcal M(P,Q)\)。"
基础（\(n = 0\)）：可行对满足 \(\deg Q \le -1\)（即 \(Q = 0\)）与 \(|P| = 1\)，故 \(P\) 是模 \(1\) 的常数，\(P = e^{i\Phi_0}\)。取 \(U_{\text{QSP}} = S(\Phi_0) = \mathcal M(e^{i\Phi_0}, 0) = \mathcal M(P, Q)\)，成立。
归纳步：设 \(\mathrm H(0),\ldots,\mathrm H(n-1)\) 成立，\((P,Q)\) 是层数 \(n\) 的可行对。
情形一：\(\deg P = n\)。由引理 2，存在 \(\Phi_n\) 与层数 \(n-1\) 的可行对 \((P',Q')\) 满足正向递推。由 \(\mathrm H(n-1)\)，存在 \((\Phi_0,\ldots,\Phi_{n-1})\) 使 \(S(\Phi_0)\prod_{k=1}^{n-1}WS(\Phi_k) = \mathcal M(P',Q')\)。再乘上最后一个因子并两次使用引理 1 的乘积公式（\(WS(\Phi) = \mathcal M(xe^{i\Phi}, e^{-i\Phi})\)，且 \(\mathcal M(P',Q')\mathcal M(xe^{i\Phi_n}, e^{-i\Phi_n})\) 的 \((0,0)\)、\((0,1)\) 元分别为 \(e^{i\Phi_n}(xP' - s^2Q')\) 与 \(is\,e^{-i\Phi_n}(P' + xQ')\)）：
末代入了引理 2 的正向递推（\(s^2 = 1-x^2\)）。故 \(\mathrm H(n)\) 成立。
情形二：\(\deg P \le n - 2\)。由引理 2(c)，\((P,Q)\) 是层数 \(n-2\) 的可行对，由 \(\mathrm H(n-2)\) 得长度 \(n-2\) 的序列。若需要长度恰为 \(n\)，补两个零相位因子 \(WS(0)\)：用引理 1 的乘积公式计算
即补两个零相位只引入一个全局符号 \(-1\)，用 \(\Phi_0 \to \Phi_0 + \pi\) 抵消即可（\(S(\Phi_0+\pi) = -S(\Phi_0)\)）。故 \(\mathrm H(n)\) 成立。
归纳完成，\(\mathrm H(d)\) 结合第一步即得定理。\(\blacksquare\)
作为对照，归纳的每一层剥除中 \(P\)、\(Q\) 的递推就是引理 2 中的四条公式：反向（由高层数到低层数）用 \(P' = e^{-i\Phi}xP + e^{i\Phi}(1-x^2)Q\) 与 \(Q' = -e^{-i\Phi}P + e^{i\Phi}xQ\)，正向（由低层数装配到高层数）用 \(P = e^{i\Phi}(xP' - (1-x^2)Q')\) 与 \(Q = e^{-i\Phi}(P' + xQ')\)；其中引理 2 的陈述与证明给出约束保持与降次，引理 1 的乘积公式给出电路层面的对应。
相位解的离散性¶
命题：给定可行对 \((P,Q)\)，满足它的相位向量在模 \(2\pi\) 意义下只有有限多个。
对低层数可直接验证：\(d=0\) 时 \(\Phi_0 = \arg P\) 唯一；\(d=1\) 时由 \(U_{\text{QSP}} = S(\Phi_0)WS(\Phi_1)\) 的显式展开，\(P = xe^{i(\Phi_0+\Phi_1)}\)、\(Q = e^{i(\Phi_0-\Phi_1)}\)，两个线性方程 \(\Phi_0+\Phi_1 = \arg p_1\)、\(\Phi_0 - \Phi_1 = \arg q_0\) 在模 \(2\pi\) 下有唯一解。一般层数下，归纳的每一层中剥除相位由 \(e^{2i\Phi} = p_n/q_{n-1}\) 确定，只有两个模 \(2\pi\) 的解（相差 \(\pi\)），且由引理 2 的证明可知相差 \(\pi\) 的两个选择给出恰好相差全局符号 \(-1\) 的低层序列，可被末端相位吸收——因此解集合是离散有限的。若只给定 \(P\) 而不指定 \(Q\)，引理 3 的谱分解本身也有有限的符号型选择。Haah（2019）的算法从 \(P\) 的切比雪夫系数出发，以 \(O(d^2)\) 复杂度返回其中一组确定的解，避免了迭代优化的局部极小问题。
逼近精度¶
命题一（Lipschitz 函数，Jackson 定理）：设 \(f:[-1,1]\to\mathbb C\) 的连续模为 \(\omega_f(\delta) = \sup_{|x-y|\le\delta}|f(x)-f(y)|\)。经典 Jackson 定理断言，存在次数 \(\le d\) 的多项式 \(P_d\) 使
（\(C\) 为绝对常数）。特别地，Lipschitz 常数为 \(L\) 的函数满足 \(\omega_f(\delta) \le L\delta\)，于是达到精度 \(\varepsilon\) 需要 \(d = O(L/\varepsilon)\)——注意对 \(\varepsilon\) 是多项式依赖，而非对数依赖；这是仅有光滑性假设时的本质代价。
命题二（整函数，Bernstein 椭圆）：设 \(f\) 在含 \([-1,1]\) 的 Bernstein 椭圆（Bernstein ellipse）\(E_\rho\)（参数 \(\rho > 1\)，参数化为 \(z = (w + w^{-1})/2\)，\(|w| = \rho\)）上解析，切比雪夫系数为 \(c_k\)，\(M := \max_{z\in E_\rho}|f(z)|\)。由柯西积分估计可得 \(|c_k| \le 2M\rho^{-k}\)，于是截断误差为
推论（哈密顿量模拟的次数）：取 \(f(x) = e^{-i\tau x}\)（\(\tau = \alpha t > 0\)）。在 \(E_\rho\) 上，\(|f(z)| = e^{\tau\,\mathrm{Im}\,z}\)，而 \(\mathrm{Im}\,z = \tfrac{1}{2}(\rho - \rho^{-1})\sin\varphi \le \tfrac{1}{2}(\rho-\rho^{-1})\)（\(w = \rho e^{i\varphi}\)），故 \(M = e^{\tau(\rho-\rho^{-1})/2}\)。选 \(\rho = d/\tau\)（设 \(d \ge 2\tau > \tau\)），代入：
令 \(d = c\tau\)，主部为 \(\tau\big[\tfrac{c}{2} - c\ln c\big] + \tau\ln c\)；取 \(c = e\) 得主部 \(\tau(\tfrac{e}{2} - e + 1) < 0\)，即误差随 \(\tau\) 指数衰减；再增大 \(d\) 每增加 \(1\) 使指数至少下降 \(\ln(d/\tau) - \tfrac12 > 0\)。因此
次切比雪夫截断即可达到精度 \(\varepsilon\)，且截断多项式自动满足 \(|P|\le 1\) 与端点条件（\(|e^{-i\tau(\pm1)}| = 1\)）。这与 Low–Chuang（2017）的最优哈密顿量模拟复杂度一致：模拟时间越长、精度越高，次数线性地、对数地增长。\(e^{-i\tau x}\) 无确定奇偶性，按"第一步"末尾所述拆成 \(\cos\tau x\)（偶）与 \(-i\sin\tau x\)（奇）两支实现。
具体例子¶
例子一：Grover 搜索¶
Grover 搜索的目标是找到标记态 \(|w\rangle\)。在 QSP 框架中，把 Grover 迭代写为两个反射的乘积 \(W = (I - 2|w\rangle\langle w|)(I - 2|s\rangle\langle s|)\)（\(|s\rangle\) 为均匀叠加态）。它在平面 \(\mathrm{span}\{|w\rangle, |w^\perp\rangle\}\) 上是旋转，每次转过 \(2\arcsin(1/\sqrt N)\)，特征值 \(e^{\pm i\theta}\)（\(\cos\theta = 1 - 2/N\)，与 \(\theta = 2\arccos\sqrt{1/N}\) 给出同一对特征值）。
目标多项式 \(P\) 取为在信号 \(x_{\text{target}}\)（对应 \(\theta\)）处接近 \(1\)、其余处接近 \(0\) 的峰形多项式。由振幅放大的标准计数，把初态振幅 \(\sim 1/\sqrt N\) 转到 \(1\) 需要旋转次数
QSP 以此深度的相位序列复现 \(O(\sqrt N)\) 搜索，并带有严格可控的误差界。
例子二：哈密顿量模拟¶
对 \(H = \sum_k \alpha_k H_k\)（\(H_k\) 为泡利字符串），模拟 \(e^{-iHt}\)：
构造 \(H\) 的 LCU 块编码，归一化常数 \(\lambda = \|\vec\alpha\|_1\)；Qubitization 行走 \(W'(H)\) 的不变平面参数满足 \(\cos\theta_j = E_j/\lambda\)；
目标函数为 \(x \mapsto e^{-i\tau x}\)（\(\tau = \lambda t\)；它不是多项式，需要逼近）；
由"逼近精度"一节的命题二，取 \(d = O(\tau + \log(1/\varepsilon))\) 次切比雪夫截断 \(P_d \approx e^{-i\tau x}\)，再拆偶、奇两支；
用 Haah 算法或迭代法求相位 \(\vec\Phi\)，构造 QSP 电路。
精确成立的是算符恒等式 \((\langle0|^{\otimes m}\otimes I)\widetilde U_{\vec\Phi}(|0\rangle^{\otimes m}\otimes I) = P(H/\lambda)\)，逼近误差只来自第 3 步的多项式截断。总门数为 \(O(d)\) 次 \(W'(H)\) 调用，即 \(O\big((\lambda t + \log(1/\varepsilon))\cdot(L n + C_{\text{PREP}})\big)\)；若块编码的归一化常数能压到 \(\alpha \approx \|H\|\)，则相应地 \(d = O(\|H\|t + \log(1/\varepsilon))\)。
例子三：矩阵求逆¶
对 \(A^{-1}\)（\(\|A\| \le \alpha\)，\(\kappa = \alpha/\sigma_{\min}\)）：
目标函数 \(1/x\) 在 \(x \to 0\) 时无界，且不满足端点条件，故先做归一化与截断：
并实现归一化版本 \(\frac{1}{\kappa}P_{\text{trunc}}\)（保证 \(|P| \le 1\)，经 QSVT 双投影子形式实现）。用 \(d = O(\kappa \log(\kappa/\varepsilon))\) 次多项式逼近（在截断的过渡带处需平滑处理，这贡献了 \(\log\kappa\) 因子），QSP 给出 \(O(\kappa \log(\kappa/\varepsilon))\) 次 \(W'(A)\) 调用的矩阵求逆算法；输出的成功幅度由归一化因子 \(1/\kappa\) 决定，可用振幅放大补足。
复杂度总结¶
应用 |
QSP 阶数 \(d\) |
总门数 |
|---|---|---|
\(e^{-iHt}\)（哈密顿量模拟） |
\(O(\alpha t + \log(1/\varepsilon))\) |
\(O(d \cdot (L n + C_{\text{PREP}}))\) |
\(A^{-1}\)（矩阵求逆） |
\(O(\kappa \log(\kappa/\varepsilon))\) |
\(O(d \cdot C_{U_A})\) |
\(f(A)\)（通用矩阵函数） |
\(O(\text{deg}(f_{\text{approx}}))\) |
\(O(d \cdot C_{U_A})\) |
Grover 搜索 |
\(O(\sqrt{N})\) |
\(O(\sqrt{N})\) |
表中 \(\alpha\) 为块编码归一化常数（LCU 情形为 \(\lambda = \|\vec\alpha\|_1 \ge \|H\|\)），\(C_{U_A}\) 为单次块编码调用的门数。所有情况均无需后选择，深度达到信息论下界（至多相差 \(\text{poly}\log\) 因子）。
与 Trotter 和 LCHS 的对比¶
特性 |
Trotter |
LCHS |
QSP |
|---|---|---|---|
后选择 |
无 |
有 |
无 |
误差界 |
渐近估计 |
可证明 |
精确可控 |
深度 |
\(O(r \cdot L)\) |
\(O(d \cdot L \cdot e^{|\alpha|t})\) |
\(O(d \cdot L)\) |
\(d\) 与精度 \(\varepsilon\) 的关系 |
\(O(1/\varepsilon^{1/2p})\) |
\(O(\log(1/\varepsilon))\) |
\(O(\log(1/\varepsilon))\) |
实现难度 |
低 |
中 |
高（需相位求解） |
QSP 的主要劣势在于相位参数 \(\vec{\Phi}\) 的求解——虽然 Haah 的 \(O(d^2)\) 算法已足够高效，但在实际工程实现中仍是技术挑战。
近期进展¶
年份 |
贡献 |
内容 |
|---|---|---|
2017 |
Low & Chuang |
QSP 原始论文，证明最优哈密顿量模拟 |
2019 |
Haah |
相位参数的显式 \(O(d^2)\) 求解算法 |
2019 |
Gilyén et al. |
QSVT：将 QSP 从 1D 推广到任意矩阵 |
2021 |
Martyn et al. |
Grand Unification：QSP 与 QSVT 的等价性 |
2022 |
Dong et al. |
量子信号处理的高效经典模拟 |
总结¶
QSP 是量子算法设计中最优雅的工具之一。它把复杂的矩阵变换归约为单量子比特旋转序列的精确分析：引理 1 的封闭性给出电路与多项式对的对应，引理 2 的剥层递推把相位求解变成逐层的代数配平，引理 3 的谱分解保证可行对存在，三者合起来实现了理论上最优的深度-精度权衡。理解 QSP 不仅有助于设计高效的量子算法，也揭示了量子计算与经典逼近理论之间深刻的数学联系。
参考文献：
Low, G. H., & Chuang, I. L. (2017). Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118(1), 010501.
Haah, J. (2019). Product decomposition of periodic functions in quantum signal processing. Quantum, 3, 190.
Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019). Quantum singular value transformation and beyond. STOC 2019.
Martyn, J. M., Rossi, Z. M., Tan, A. K., & Chuang, I. L. (2021). Grand unification of quantum algorithms. PRX Quantum, 2(4), 040203.
返回目录：量子计算算法教程系列