量子信号处理（Quantum Signal Processing, QSP）由 Guang Hao Low 和 Isaac Chuang 于 2017 年提出，是量子计算中最精确、最通用的矩阵函数逼近工具之一。它表明：对任意单量子比特旋转序列的精确分析，可以实现对量子信号（即酉算符的特征相位）的任意多项式变换，且电路深度达到信息论下界。

问题背景

在量子算法中，一个反复出现的需求是：给定酉算符 $U$（特征值 $e^{i\phi_k}$），构造一个新的酉算符 $V$，使得 $V$ 在 $U$ 的特征子空间上的作用对应于某个目标函数 $f(e^{i\phi})$。

具体来说，给定 $W = W(A)$（由 Qubitization 构造的量子行走酉算符，特征值 $e^{\pm i\theta_j}$，$\theta_j = \arccos(\sigma_j)$），目标是构造：

$$\Pi f(\sigma_j) \Pi$$

其中 $f$ 是目标多项式，$\Pi$ 是到特定子空间的投影。

经典方法的局限：

• Trotter 分解：精度受限于分解阶数，无法精确实现多项式变换
• LCHS（Taylor 展开）：需要后选择，成功概率随精度指数衰减
• 奇异值分解 + 经典后处理：测量开销大

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

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

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

QSP 序列的定义

令 $\omega = e^{i\phi}$（$\phi$ 为待变换的”信号”）。定义两组单量子比特旋转：

$$U_\phi = e^{i\phi Z} = \begin{pmatrix} e^{i\phi} & 0 \\ 0 & e^{-i\phi} \end{pmatrix}, \quad S = e^{i\theta Z} = \begin{pmatrix} e^{i\theta} & 0 \\ 0 & e^{-i\theta} \end{pmatrix}$$

$d$ 阶 QSP 序列（相位参数 $\vec{\Phi} = (\Phi_0, \Phi_1, \ldots, \Phi_d)$）：

$$U_{\text{QSP}}(\vec{\Phi}) = e^{i\Phi_0 Z} \cdot \prod_{k=1}^{d} \left( e^{i\phi Z} \cdot e^{i\Phi_k Z} \right)$$

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

QSP 多项式

定理（QSP 表示定理）：$U_{\text{QSP}}(\vec{\Phi})$ 在计算基 $\{|0\rangle, |1\rangle\}$ 上的矩阵元素为：

$$U_{\text{QSP}} = \begin{pmatrix} P(\cos\phi) + iQ(\cos\phi)\sin\phi & \cdots \\ \cdots & P(\cos\phi) - iQ(\cos\phi)\sin\phi \end{pmatrix}$$

其中 $P$ 是 $d$ 次实多项式（$d$ 为偶）或 $d-1$ 次（$d$ 为奇），$Q$ 是相应次数的多项式，满足：

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

换言之，$P$ 是单位模多项式（unitary polynomial）——其值始终位于单位圆上。

关键结论：对任意满足 $|P(x)| \le 1$ 的 $d$ 次多项式 $P$，存在相位参数 $\vec{\Phi}$ 使得 QSP 序列的 $(0,0)$ 元素恰好等于 $P(\cos\phi)$。

数学基础：切比雪夫多项式

QSP 的数学结构与切比雪夫多项式天然耦合。

切比雪夫多项式的定义

第一类切比雪夫多项式：

$$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$ 次。

QSP 与切比雪夫的关系

将 $U_\phi = e^{i\phi Z}$ 视为”信号旋转”，其在子空间 $\text{span}\{|0\rangle, |1\rangle\}$ 上的特征值为 $e^{\pm i\phi}$。QSP 序列 $U_{\text{QSP}}$ 的 $(0,0)$ 元素可以展开为：

$$[U_{\text{QSP}}]_{00} = \sum_{k=0}^{d} c_k e^{ik\phi} + \text{共轭项} = \sum_{k=0}^{d} c_k' T_k(\cos\phi) + i\sin\phi \sum_{k=0}^{d-1} d_k' U_k(\cos\phi)$$

其中 $c_k'$ 和 $d_k'$ 由相位参数 $\vec{\Phi}$ 决定。利用切比雪夫多项式的完备性，任意 $d$ 次多项式 $P(\cos\phi)$ 都可以通过适当选取 $\vec{\Phi}$ 来实现。

算法步骤详解

第一步：确定目标多项式

根据应用确定目标多项式 $P(x)$：

• 哈密顿量模拟：$P(x) = e^{-i\arccos(x) \cdot t}$ 的截断切比雪夫逼近
• 矩阵求逆：$P(x) = 1/x$ 的多项式逼近
• 量子搜索：$P(x) = 1$（在 $x = \cos\theta_{\text{target}}$ 处），$P(x) = 0$（其他地方）

第二步：多项式到相位参数的转换

给定 $d$ 次多项式 $P(x)$，求相位参数 $\vec{\Phi} = (\Phi_0, \Phi_1, \ldots, \Phi_d)$ 使得：

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

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

$$\Phi_k = \begin{cases} 0 & k = 0, n \\ \pi/2 & 0 < k < n \end{cases}$$

对应电路为 $e^{i\phi Z} \cdot e^{i(\pi/2) Z} \cdot e^{i\phi Z} \cdots$，效果恰好为 $T_n(\cos\phi) = \cos(n\phi)$。

第三步：构造量子电路

将 QSP 序列转化为量子门电路。在实际量子算法中，“信号旋转” $e^{i\phi Z}$ 对应于一次 Qubitization 酉算符 $W(A)$ 的作用（因为 $W(A)$ 的特征值正是 $e^{\pm i\theta_j}$，$\theta_j = \arccos(\sigma_j)$）。

电路结构：

$$U_{\text{QSP}} = \underbrace{e^{i\Phi_0 Z}}_{\text{单比特门}} \cdot \underbrace{W(A)}_{\text{信号}} \cdot \underbrace{e^{i\Phi_1 Z}}_{\text{单比特门}} \cdot \underbrace{W(A)}_{\text{信号}} \cdots \underbrace{e^{i\Phi_d Z}}_{\text{单比特门}}$$

注意：$e^{i\Phi_k Z}$ 是在辅助量子比特上的单比特旋转，门代价 $O(1)$。$W(A)$ 是量子行走酉算符，代价 $O(\text{poly}(n))$。总深度为 $O(d)$ 次 $W(A)$ 调用。

第四步：在目标子空间上提取结果

QSP 作用在辅助量子比特 + 系统量子比特的联合空间上。在目标子空间（辅助比特投影到 $|0\rangle$）上：

$$\langle 0| U_{\text{QSP}} |0\rangle = P(\cos\phi) = P(\sigma_j)$$

对每个奇异值 $\sigma_j$，$P(\sigma_j)$ 被自动”施加”——量子并行性同时处理所有奇异值。

理论推导

QSP 表示定理的证明

定理：对任意 $d$ 次多项式 $P(x)$ 满足 $|P(x)| \le 1$（$x \in [-1, 1]$），且 $P$ 具有确定的奇偶性（$P(-x) = (-1)^d P(x)$），存在相位序列 $\vec{\Phi} = (\Phi_0, \ldots, \Phi_d)$ 使得：

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

证明（归纳法）：

基础（$d = 0$）：$P(x) = c$（常数），$|c| \le 1$。取 $\Phi_0 = \arccos(c)$，则 $e^{i\Phi_0 Z}$ 的 $(0,0)$ 元素为 $e^{i\Phi_0} = c + i\sqrt{1-c^2}$，实部为 $c$。取纯相位 $e^{i\Phi_0}$ 即可。

归纳步：设对 $d-1$ 次多项式结论成立。对 $d$ 次 $P(x)$，构造：

$$\tilde{P}(x) = \frac{P(x) - e^{i\Phi_0} T_d(x)}{1 - e^{2i\Phi_0}} \cdot (\text{适当因子})$$

通过选择 $\Phi_0$ 使 $\tilde{P}$ 的次数降低到 $d-1$，再对 $\tilde{P}$ 应用归纳假设。

关键引理：$T_d(x)$ 在 $[-1, 1]$ 上的震荡幅度恰好为 $1$（$|T_d(x)| \le 1$），且在 $d+1$ 个点达到 $\pm 1$，因此总存在 $\Phi_0$ 使得”消去”最高次项后的余项仍满足单位模条件。$\blacksquare$

逼近精度

定理：设目标函数 $f: [-1, 1] \to \mathbb{C}$ 满足 $|f(x)| \le 1$，且 Lipschitz 常数为 $L$。则存在 $d = O(L + \log(1/\varepsilon))$ 次多项式 $P$ 满足：

$$\max_{x \in [-1, 1]} |f(x) - P(x)| \le \varepsilon$$

且 $P$ 可以精确实现为 $d$ 阶 QSP 序列。

对解析函数 $f$，Jackson 定理给出更精确的界：

$$d = O\left(\frac{1}{\varepsilon} \cdot \text{polylog}\left(\frac{1}{\varepsilon}\right)\right)$$

对 $f(x) = e^{-i\lambda \arccos(x)}$（哈密顿量模拟），Jackson 定理给出 $d = O(|\lambda| + \log(1/\varepsilon))$。

相位参数求解的唯一性

定理（Haah, 2019）：对给定 $d$ 次多项式 $P(x)$，满足 $|P(x)| \le 1$ 的约束下，相位参数 $\vec{\Phi}$ 在离散对称群 $Z_2^{d+1}$ 的作用下唯一。即 $\vec{\Phi}$ 的解是离散的、有限多的。

Haah 给出了从 $P$ 的切比雪夫系数直接计算 $\vec{\Phi}$ 的 $O(d^2)$ 算法，避免了迭代优化。

具体例子

例子一：Grover 搜索

Grover 搜索的目标是找到标记态 $|w\rangle$。在 QSP 框架中：

• 信号酉算符：$U = H^n Z_0 H^n$（在计算基上的反射）与 $I - 2|w\rangle\langle w|$ 的组合
• 实际上，$W(A) = (I - 2|w\rangle\langle w|)(I - 2|0\rangle\langle 0|)$，特征值为 $e^{\pm i\theta}$，$\theta = 2\arccos(\sqrt{1/N})$

目标多项式：$P(\cos\theta) = 1$（在 $\theta = 2\arccos(\sqrt{1/N})$ 处），近似为在 $\sigma = \cos\theta$ 处的高幅度峰。

取 $d \approx \pi\sqrt{N}/2$，QSP 给出 $O(\sqrt{N})$ 搜索——完全复现 Grover 的复杂度，但具有更严格的误差界。

例子二：哈密顿量模拟

对哈密顿量 $H = \sum_k \alpha_k H_k$，$\|H\| \le 1$，模拟 $e^{-iHt}$：

1. 构造 $W(H)$（Qubitization），特征值 $e^{\pm i\theta_j}$，$\theta_j = \arccos(E_j)$
2. 目标多项式 $P(\cos\theta) = e^{-i\theta t}$（注意：不是多项式，需逼近）
3. 用 Jackson 定理或 Remez 算法找到 $d$ 次多项式 $P_d$ 逼近 $e^{-i\arccos(x) \cdot t}$
4. $d = O(t + \log(1/\varepsilon))$
5. 求相位参数 $\vec{\Phi}$，构造 QSP 电路

总门数：$O(d)$ 次 $W(H)$ 调用 $= O((t + \log(1/\varepsilon)) \cdot L \cdot n)$，其中 $L$ 为哈密顿量项数，$n$ 为量子比特数。

例子三：矩阵求逆

对 $A^{-1}$（$\|A\| \le 1$，$\kappa = 1/\sigma_{\min}$）：

目标多项式 $P(x) = 1/x$，但 $|P(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}$$

用 $d = O(\kappa \log(\kappa/\varepsilon))$ 次多项式逼近，QSP 给出 $O(\kappa \log(\kappa/\varepsilon))$ 次 $W(A)$ 调用的矩阵求逆算法。

复杂度总结

所有情况均无需后选择，深度达到信息论下界（至多相差 $\text{poly}\log$ 因子）。

与 Trotter 和 LCHS 的对比

QSP 的主要劣势在于相位参数 $\vec{\Phi}$ 的求解——虽然 Haah 的 $O(d^2)$ 算法已足够高效，但在实际工程实现中仍是技术挑战。

近期进展

总结

QSP 是量子算法设计中最优雅的工具之一。它将复杂的矩阵变换归约为单量子比特旋转序列的精确分析，实现了理论上最优的深度-精度权衡。理解 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.