# 量子信号处理（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$ 是块编码的归一化常数），我们的目标是构造投影意义下的矩阵函数

$$\Pi\, P\!\left(\frac{\sigma_j}{\alpha}\right) \Pi,$$

其中 $P$ 是目标多项式，$\Pi$ 是到信号子空间的投影。

**经典方法的局限**：

- Trotter 分解：精度受限于分解阶数，无法精确实现多项式变换；
- LCHS（线性组合哈密顿量模拟）：依赖 Taylor 展开与后选择，成功概率随精度要求衰减；
- 奇异值分解加经典后处理：测量开销大。

QSP 提供了一种无需后选择、深度最优、误差精确可控的方案。

## 核心思想：单量子比特旋转序列

QSP 的核心观察极为简洁：一系列交替的单量子比特旋转，其整体效果等价于一个关于信号参数的多项式变换。

### 信号矩阵与相位矩阵

定义**信号矩阵**（signal matrix）

$$W(x) = \begin{pmatrix} x & i\sqrt{1-x^2} \\ i\sqrt{1-x^2} & x \end{pmatrix},\qquad x \in [-1,1],$$

与**相位矩阵**（phase matrix）

$$S(\phi) = e^{i\phi Z} = \begin{pmatrix} e^{i\phi} & 0 \\ 0 & e^{-i\phi} \end{pmatrix}.$$

$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)$）定义为

$$U_{\text{QSP}}(\vec{\Phi}; x) = S(\Phi_0)\cdot \prod_{k=1}^{d} \Big( W(x)\, S(\Phi_k) \Big),$$

即 $d$ 次"信号旋转"与 $d+1$ 次"处理器相位旋转"交替施加。

### QSP 多项式与矩阵形式

**定理（QSP 矩阵形式）**：对任意 $\vec{\Phi} \in \mathbb{R}^{d+1}$，存在多项式对 $(P, Q)$，使得

$$U_{\text{QSP}}(\vec{\Phi}; x) = \begin{pmatrix} P(x) & i\sqrt{1-x^2}\, Q(x) \\ i\sqrt{1-x^2}\, Q^{*}(x) & P^{*}(x) \end{pmatrix},$$

其中记号 $P^{*}(x) := \overline{P(\bar x)}$ 表示系数取复共轭的多项式（在实轴上即通常的复共轭函数）。多项式 $P$ 满足 $\deg P \le d$ 且奇偶性与 $d$ 相同；$Q$ 满足 $\deg Q \le d-1$ 且奇偶性与 $d-1$ 相同；并且 $U_{\text{QSP}}$ 的酉性等价于

$$|P(x)|^2 + (1-x^2)\,|Q(x)|^2 = 1, \qquad \forall x \in [-1,1].$$

注意矩阵的四个元素中，反对角上出现的正是 $\sqrt{1-x^2}$ 因子乘以 $Q(x)$ 与其共轭 $Q^{*}(x)$——这一结构对下文的推导至关重要。定理的证明（以及更强的逆命题）见"理论推导"一节。

**关键结论（可达集）**：多项式 $P$ 可以作为某个 $d$ 阶 QSP 序列的 $(0,0)$ 元素，当且仅当下列四个条件同时成立：

1. $\deg P \le d$，且 $P$ 的奇偶性与 $d$ 相同；
2. $|P(x)| \le 1$ 对一切 $x \in [-1,1]$ 成立；
3. $|P(1)| = |P(-1)| = 1$（端点条件）；
4. 若条件 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(\cos\theta) = \cos(n\theta), \quad T_0(x) = 1, \; T_1(x) = x, \; T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x)$$

第二类切比雪夫多项式：

$$U_n(\cos\theta) = \frac{\sin((n+1)\theta)}{\sin\theta}, \quad U_0(x) = 1, \; U_1(x) = 2x, \; U_{n+1}(x) = 2xU_n(x) - U_{n-1}(x)$$

关键性质：$|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$。我们断言

$$W(x)^d = \begin{pmatrix} T_d(x) & i\sqrt{1-x^2}\,U_{d-1}(x) \\ i\sqrt{1-x^2}\,U_{d-1}(x) & T_d(x) \end{pmatrix}.$$

对 $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)$ 使得：

$$\big[U_{\text{QSP}}(\vec{\Phi})\big]_{00} = P(x)$$

**方法一：代数方法（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)$，相位参数有显式解：全零相位

$$\Phi_0 = \Phi_1 = \cdots = \Phi_d = 0$$

即可，因为此时 $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{U}_{\vec{\Phi}} = \underbrace{e^{i\Phi_0\widetilde{Z}}}_{\text{相位旋转}} \cdot \underbrace{W'(A)}_{\text{信号}} \cdot \underbrace{e^{i\Phi_1\widetilde{Z}}}_{\text{相位旋转}} \cdot \underbrace{W'(A)}_{\text{信号}} \cdots \underbrace{e^{i\Phi_d\widetilde{Z}}}_{\text{相位旋转}}$$

其中 $\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 教程的转移矩阵恒等式推广到交错序列（同教程"理论推导"第四步），我们得到精确的算符恒等式

$$(\langle 0|^{\otimes m}\otimes I)\,\widetilde{U}_{\vec{\Phi}}\,(|0\rangle^{\otimes m}\otimes I) = P\!\left(\frac{A}{\alpha}\right) = \sum_j P\!\left(\frac{\sigma_j}{\alpha}\right) |u_j\rangle\langle v_j|,$$

即对每个奇异值 $\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)$，定义矩阵值函数

$$\mathcal{M}(P, Q) := \begin{pmatrix} P & isQ \\ isQ^{*} & P^{*} \end{pmatrix}.$$

### 引理 1：矩阵形式与封闭性

**引理 1**：(a) **乘积公式**。对任意两个多项式对，

$$\mathcal{M}(P_1, Q_1)\,\mathcal{M}(P_2, Q_2) = \mathcal{M}\big(P_1P_2 - s^2 Q_1Q_2^{*},\; P_1Q_2 + Q_1P_2^{*}\big).$$

(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)$ 元为

$$P_1P_2 + (isQ_1)(isQ_2^{*}) = P_1P_2 + i^2s^2Q_1Q_2^{*} = P_1P_2 - s^2Q_1Q_2^{*};$$

$(0,1)$ 元为

$$P_1\cdot isQ_2 + isQ_1\cdot P_2^{*} = is\,(P_1Q_2 + Q_1P_2^{*}).$$

再验证所得矩阵确有 $\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'(x) = e^{-i\Phi_d}\,x\,P(x) + e^{i\Phi_d}\,(1-x^2)\,Q(x), \qquad Q'(x) = -\,e^{-i\Phi_d}P(x) + e^{i\Phi_d}\,x\,Q(x),$$

则 $(P', Q')$ 是层数 $d-1$ 的可行对，且 $(P, Q)$ 与 $(P', Q')$ 之间满足正向递推

$$P(x) = e^{i\Phi_d}\Big(x\,P'(x) - (1-x^2)\,Q'(x)\Big), \qquad Q(x) = e^{-i\Phi_d}\Big(P'(x) + x\,Q'(x)\Big);$$

(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$：

$$e^{i\Phi_d}\Big(xP' - (1-x^2)Q'\Big) = e^{i\Phi_d}\Big[x\big(e^{-i\Phi_d}xP + e^{i\Phi_d}(1-x^2)Q\big) - (1-x^2)\big({-}e^{-i\Phi_d}P + e^{i\Phi_d}xQ\big)\Big]$$
$$= e^{i\Phi_d}\Big[e^{-i\Phi_d}\big(x^2 + (1-x^2)\big)P + e^{i\Phi_d}\big(x(1-x^2) - x(1-x^2)\big)Q\Big] = P;$$

对 $Q$：

$$e^{-i\Phi_d}\Big(P' + xQ'\Big) = e^{-i\Phi_d}\Big[e^{-i\Phi_d}xP + e^{i\Phi_d}(1-x^2)Q + x\big({-}e^{-i\Phi_d}P + e^{i\Phi_d}xQ\big)\Big] = e^{-i\Phi_d}\cdot e^{i\Phi_d}\big[(1-x^2) + x^2\big]Q = 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'|^2 = \big|xP + e^{2i\Phi}(1-x^2)Q\big|^2 = x^2|P|^2 + (1-x^2)^2|Q|^2 + 2x(1-x^2)\,\rho,$$

$$|Q'|^2 = \big|xQ - e^{-2i\Phi}P\big|^2 = x^2|Q|^2 + |P|^2 - 2x\,\rho.$$

于是

$$|P'|^2 + (1-x^2)|Q'|^2 = x^2|P|^2 + (1-x^2)^2|Q|^2 + 2x(1-x^2)\rho + (1-x^2)\big[x^2|Q|^2 + |P|^2 - 2x\rho\big]$$
$$= \big[x^2 + (1-x^2)\big]|P|^2 + \big[(1-x^2)^2 + x^2(1-x^2)\big]|Q|^2 + 0 = |P|^2 + (1-x^2)|Q|^2 = 1,$$

末步用了 $(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^{-i\Phi_d}p_d - e^{i\Phi_d}q_{d-1} = e^{-i\Phi_d}\big(p_d - e^{2i\Phi_d}q_{d-1}\big) = 0$$

（末步用了 $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$ 系数为

$$-e^{-i\Phi_d}p_d + e^{i\Phi_d}q_{d-1} = 0$$

（同一个条件），故 $\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 谱分解定理，这里给出精确的归约步骤）：

1. 定义 $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$。
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$。
3. 利用 $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')$）：

$$S(\Phi_0)\prod_{k=1}^{n}WS(\Phi_k) = \mathcal M\Big(e^{i\Phi_n}(xP' - s^2Q'),\; e^{-i\Phi_n}(P' + xQ')\Big) = \mathcal M(P, Q),$$

末代入了引理 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 的乘积公式计算

$$\big[WS(0)\big]^2 = \mathcal M(ix, -i)^2 = \mathcal M\big((ix)^2 - s^2(-i)(i),\; (ix)(-i) + (-i)(ix)^{*}\big) = \mathcal M(-x^2 - s^2,\; x - x) = \mathcal M(-1, 0) = -I,$$

即补两个零相位只引入一个全局符号 $-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$ 使

$$\|f - P_d\|_{\infty} \le C\,\omega_f(1/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 - P_d\|_\infty \le \sum_{k>d}|c_k| \le \frac{2M\rho^{-d}}{1 - \rho^{-1}} = \frac{2M\,\rho^{1-d}}{\rho - 1}.$$

**推论（哈密顿量模拟的次数）**：取 $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$），代入：

$$\ln\|f - P_d\|_\infty \le \ln 2 + \frac{\tau}{2}\Big(\frac{d}{\tau} - \frac{\tau}{d}\Big) - (d-1)\ln\frac{d}{\tau} - \ln\Big(\frac{d}{\tau} - 1\Big) = \ln 2 + \frac{d}{2} - \frac{\tau^2}{2d} - (d-1)\ln\frac{d}{\tau} - \ln\Big(\frac{d}{\tau}-1\Big).$$

令 $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$。因此

$$d = O\big(\tau + \log(1/\varepsilon)\big)$$

次切比雪夫截断即可达到精度 $\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$ 需要旋转次数

$$d \approx \frac{\pi}{4}\sqrt{N},$$

QSP 以此深度的相位序列复现 $O(\sqrt N)$ 搜索，并带有严格可控的误差界。

### 例子二：哈密顿量模拟

对 $H = \sum_k \alpha_k H_k$（$H_k$ 为泡利字符串），模拟 $e^{-iHt}$：

1. 构造 $H$ 的 LCU 块编码，归一化常数 $\lambda = \|\vec\alpha\|_1$；Qubitization 行走 $W'(H)$ 的不变平面参数满足 $\cos\theta_j = E_j/\lambda$；
2. 目标函数为 $x \mapsto e^{-i\tau x}$（$\tau = \lambda t$；它不是多项式，需要逼近）；
3. 由"逼近精度"一节的命题二，取 $d = O(\tau + \log(1/\varepsilon))$ 次切比雪夫截断 $P_d \approx e^{-i\tau x}$，再拆偶、奇两支；
4. 用 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$ 时无界，且不满足端点条件，故先做归一化与截断：

$$P_{\text{trunc}}(x) = \begin{cases} 1/x & |x| \ge 1/\kappa \\ \kappa \cdot \text{sign}(x) & |x| < 1/\kappa \end{cases}$$

并实现归一化版本 $\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 不仅有助于设计高效的量子算法，也揭示了量子计算与经典逼近理论之间深刻的数学联系。

---

**参考文献：**

1. Low, G. H., & Chuang, I. L. (2017). *Optimal Hamiltonian simulation by quantum signal processing.* Physical Review Letters, 118(1), 010501.
2. Haah, J. (2019). *Product decomposition of periodic functions in quantum signal processing.* Quantum, 3, 190.
3. Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019). *Quantum singular value transformation and beyond.* STOC 2019.
4. Martyn, J. M., Rossi, Z. M., Tan, A. K., & Chuang, I. L. (2021). *Grand unification of quantum algorithms.* PRX Quantum, 2(4), 040203.
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)