量子奇异值变换（QSVT）详解：量子算法的大统一框架¶

量子奇异值变换（Quantum Singular Value Transformation, QSVT）由 András Gilyén、Yuan Su、Guang Hao Low 和 Nathan Wiebe 于 2019 年提出，是量子计算领域近年来最重要的理论突破之一。它将 Grover 搜索、哈密顿量模拟、量子行走、矩阵求逆等看似独立的量子算法统一到同一个数学框架下——对矩阵奇异值的多项式变换。

本教程在 QSP 教程与 Qubitization 教程的基础上展开，并沿用全章统一的约定：信号矩阵取 $X$ 型旋转 $W(x)$、处理器取相位旋转 $S(\phi) = e^{i\phi Z}$、块编码辅助寄存器上的反射记作 $R_0 = 2|0\rangle\langle 0|^{\otimes m} - I$。QSVT 回答的问题是：能否把 QSP 的单量子比特多项式变换"并行地"施加到一个任意矩阵的所有奇异值上？答案是肯定的，而且构造可以逐步展开：我们把块编码的酉算符限制到一族二维不变子空间上，它在每个这样的子空间上的行为恰好是一个信号矩阵；于是整条 QSVT 电路逐块地化作一条 QSP 序列，QSP 的全部结论即可原封不动地搬运过来。

问题背景：量子算法的碎片化¶

在 QSVT 之前，量子算法的设计呈现高度碎片化：

算法	核心技术	目标
Grover	振幅放大	搜索标记元素
Shor	QFT + 周期查找	因数分解
HHL	QPE + 受控旋转	线性方程组
Trotter	乘积公式	哈密顿量模拟
LCHS	LCU + 后选择	哈密顿量模拟
Qubitization	量子行走	哈密顿量模拟

这些算法各自有不同的推导方法和分析工具，缺乏统一视角。QSVT 的核心贡献在于：将所有这些算法统一为"对矩阵奇异值施加多项式变换"这一单一操作。只要一个算法的目标可以被写成矩阵谱（奇异值）上的多项式，它就有深度最优的 QSVT 实现，而不同算法之间的差别只是多项式与相位参数的差别。

核心思想：从 QSP 到 QSVT¶

回顾：QSP 的一维版本¶

按 QSP 教程的约定，信号矩阵与处理器分别为

\[\begin{split}W(x) = \begin{pmatrix} x & i\sqrt{1-x^2} \\ i\sqrt{1-x^2} & x \end{pmatrix},\qquad S(\phi) = e^{i\phi Z} = \begin{pmatrix} e^{i\phi} & 0 \\ 0 & e^{-i\phi} \end{pmatrix},\end{split}\]

$d$ 阶 QSP 序列定义为

\[U_{\text{QSP}}(\vec\Psi; x) = S(\Psi_0)\cdot \prod_{k=1}^{d} \big( W(x)\, S(\Psi_k) \Big),\]

其 $(0,0)$ 元素是 $x$ 的次数至多 $d$ 的多项式 $P(x)$，且 $P$ 的奇偶性与 $d$ 一致。反过来，任何满足次数与奇偶性约束、$|P(x)|\le 1$（$x\in[-1,1]$）且 $|P(\pm1)| = 1$ 的多项式，都存在相位 $\vec\Psi$ 使其被精确实现（证明见 QSP 教程"理论推导"一节）。QSP 的全部能力就封装在这条交替序列里。

推广到矩阵：投影酉算符¶

QSVT 的关键洞见是：块编码天然给出一个"夹在两个投影之间的酉算符"。设 $\Pi$ 与 $\tilde\Pi$ 是同一个 Hilbert 空间上的两个正交投影（projector），$U$ 是酉算符，我们定义投影酉算符（projected unitary）

\[A := \tilde\Pi\, U\, \Pi,\]

即 $U$ 的"左上角块"：输入限制在 $\mathrm{im}\,\Pi$ 中、输出只保留 $\mathrm{im}\,\tilde\Pi$ 中的分量。对归一化常数为 $\alpha$ 的块编码 $U_A$，取 $\Pi = \tilde\Pi = |0\rangle\langle 0|^{\otimes m}\otimes I_s$（辅助寄存器处于 $|0\rangle$、系统寄存器任意），就得到 $\tilde\Pi U_A \Pi = A/\alpha$。允许 $\Pi\ne\tilde\Pi$ 的一般形式（例如把非方阵矩阵嵌入"输入""输出"两个不同的子空间）会带来额外的自由度，我们将在理论推导中看到它并不增加任何困难。

QSVT 使用的相位门是围绕这两个投影的反射旋转。定义

\[Z_\Pi := 2\Pi - I,\qquad Z_{\tilde\Pi} := 2\tilde\Pi - I,\]

则 $e^{i\phi Z_\Pi}$ 在 $\mathrm{im}\,\Pi$ 上乘 $e^{i\phi}$、在 $\ker\Pi$ 上乘 $e^{-i\phi}$，是一个"多控相位旋转"。在块编码情形 $Z_\Pi = R_0\otimes I_s$ 恰是 Qubitization 教程中的反射算子，按该教程的分解由 $O(m)$ 个门实现。

QSVT 电路¶

给定相位向量 $\vec\Phi = (\Phi_0,\Phi_1,\ldots,\Phi_d)$，QSVT 电路是"$U$ 与 $U^\dagger$ 交替、间隙插入相位门"的序列。电路按时间从右向左读（最右边的门最先作用在输入态上），输入子空间为 $\mathrm{im}\,\Pi$：

$d$ 为奇数时（输出子空间为 $\mathrm{im}\,\tilde\Pi$，使用 $(d+1)/2$ 次 $U$ 与 $(d-1)/2$ 次 $U^\dagger$）：

\[U_{\vec\Phi} = e^{i\Phi_0 Z_{\tilde\Pi}}\;U\,e^{i\Phi_1 Z_\Pi}\,U^\dagger\,e^{i\Phi_2 Z_{\tilde\Pi}}\;U\,e^{i\Phi_3 Z_\Pi}\,U^\dagger\;\cdots\;U\,e^{i\Phi_d Z_\Pi};\]

$d$ 为偶数时（输入输出都在 $\mathrm{im}\,\Pi$ 一侧，使用 $d/2$ 次 $U$ 与 $d/2$ 次 $U^\dagger$）：

\[U_{\vec\Phi} = e^{i\Phi_0 Z_\Pi}\;U^\dagger\,e^{i\Phi_1 Z_{\tilde\Pi}}\,U\,e^{i\Phi_2 Z_\Pi}\;\cdots\;U^\dagger\,e^{i\Phi_{d-1} Z_{\tilde\Pi}}\,U\,e^{i\Phi_d Z_\Pi}.\]

例如 $d=3$ 时电路为 $e^{i\Phi_0 Z_{\tilde\Pi}}\,U\,e^{i\Phi_1 Z_\Pi}\,U^\dagger\,e^{i\Phi_2 Z_{\tilde\Pi}}\,U\,e^{i\Phi_3 Z_\Pi}$，$d=2$ 时为 $e^{i\Phi_0 Z_\Pi}\,U^\dagger\,e^{i\Phi_1 Z_{\tilde\Pi}}\,U\,e^{i\Phi_2 Z_\Pi}$。相位门类型的选择规则很简单：电路每作用一次 $U$ 或 $U^\dagger$，态就在下文定义的两类二维子空间之间跳换一次；处于 $\{|v_j\rangle,|\bar v_j\rangle\}$ 一侧时用 $Z_\Pi$ 型门，处于 $\{|u_j\rangle,|\bar u_j\rangle\}$ 一侧时用 $Z_{\tilde\Pi}$ 型门。信号算符（$U$ 或 $U^\dagger$）的总使用次数为 $d$，故门复杂度为 $O(d\cdot C_U)$，其中 $C_U$ 是单次实现 $U$（或 $U^\dagger$）的代价。

主定理¶

记 $A = \sum_j \sigma_j |u_j\rangle\langle v_j|$ 为 $A = \tilde\Pi U\Pi$ 的奇异值分解，并设 $\sigma_j\in(0,1)$、且该分解覆盖了全部输入与输出方向（即 $\ker A\cap\mathrm{im}\,\Pi = \{0\}$ 且 $\mathrm{im}\,\tilde\Pi = \mathrm{span}\{|u_j\rangle\}$；对块编码这相当于 $A$ 满秩，退化情形见下文注记）。对给定的 $\vec\Phi$，定义平移后的相位向量

\[\Psi_0 = \Phi_0 + \frac{\pi}{4},\qquad \Psi_k = \Phi_k + \frac{\pi}{2}\ \ (1\le k\le d-1),\qquad \Psi_d = \Phi_d + \frac{\pi}{4},\]

并令 $P(x) := \big[S(\Psi_0)\prod_{k=1}^d(W(x)S(\Psi_k))\big]_{00}$ 为它对应的 QSP 多项式。

定理（量子奇异值变换）：在上述记号下，有

\[d\ \text{奇}:\qquad \tilde\Pi\,U_{\vec\Phi}\,\Pi \;=\; (-i)^d\sum_j P(\sigma_j)\,|u_j\rangle\langle v_j|;\]

\[d\ \text{偶}:\qquad \Pi\,U_{\vec\Phi}\,\Pi \;=\; (-i)^d\sum_j P(\sigma_j)\,|v_j\rangle\langle v_j|.\]

右端的整体相位 $(-i)^d$ 与 $\sigma_j$ 无关，可以通过把 $\Phi_0$ 平移 $\pi d/4$ 消去，物理上无关紧要。特别地，当 $A$ 是 Hermitian 矩阵且 $P$ 的奇偶性与 $d$ 一致时，两种情形都给出矩阵函数

\[\big(\langle 0|^{\otimes m}\otimes I\big)\,U_{\vec\Phi}\,\big(|0\rangle^{\otimes m}\otimes I\big) = (-i)^d\,P(A)\]

（注意对块编码应代入归一化后的矩阵 $A/\alpha$，即多项式作用在 $\sigma_j/\alpha$ 上）。逆命题同样成立：任何满足 QSP 可达条件（次数 $\le d$、奇偶性与 $d$ 一致、$|P|\le 1$、$|P(\pm1)| = 1$）的多项式都能被 QSVT 实现，相位由 QSP 的相位求解算法给出后再按上式平移即可。证明见"理论推导"一节，那里我们把整个论证逐步展开。

数学框架¶

块编码回顾¶

矩阵 $A\in\mathbb C^{N\times N}$（$N = 2^n$）的 $(\alpha, m, \varepsilon)$-块编码（block encoding）是 $(m+n)$ 量子比特酉算符 $U_A$，满足

\[\left\| A - \alpha \big( \langle 0|^{\otimes m} \otimes I \big) U_A \big( |0\rangle^{\otimes m} \otimes I \big) \right\| \le \varepsilon .\]

用本教程的语言重述：取 $\Pi = \tilde\Pi = |0\rangle\langle0|^{\otimes m}\otimes I$，则 $\tilde\Pi U_A\Pi$ 近似等于 $A/\alpha$。构造方法（LCU、泡利分解、直接构造）见块编码教程。

投影反射与相位门¶

QSVT 使用两个反射型相位门 $e^{i\phi Z_\Pi}$ 与 $e^{i\phi Z_{\tilde\Pi}}$。它们交替与 $U$、$U^\dagger$ 复合，实现对奇异值的"相位处理"。在块编码情形 $\Pi = \tilde\Pi$，两种门是同一个物理操作 $e^{i\phi R_0}$（辅助寄存器上的多控相位旋转，代价 $O(m)$ 个门），区别只在于它在电路中的位置；而在一般的双投影形式中，二者作用在不同的辅助结构上。这正是 QSVT 相比 Qubitization 行走算符（只用一个反射 $R_0$ 与 $U_A$ 的乘积 $W' = U_A R_0$）更一般的地方。

奇异值变换多项式与符号函数¶

对多项式 $P$，定义 $A = \sum_j\sigma_j|u_j\rangle\langle v_j|$ 的奇异值变换（singular value transformation）

\[P^{SV}(A) := \sum_j P(\sigma_j)\,|u_j\rangle\langle v_j| .\]

当 $A$ 是 Hermitian 矩阵时，奇异值分解可以直接由特征值分解读出，此时会出现符号函数（sign function）。设 $A = \sum_j \lambda_j|E_j\rangle\langle E_j|$（$\lambda_j$ 可正可负），则

\[\sigma_j = |\lambda_j|,\qquad |u_j\rangle = |E_j\rangle,\qquad |v_j\rangle = \mathrm{sign}(\lambda_j)\,|E_j\rangle,\]

其中极分解 $A = \mathrm{sign}(A)\cdot|A|$ 的偏等距算符正是 $\mathrm{sign}(A) = \sum_j\mathrm{sign}(\lambda_j)|E_j\rangle\langle E_j|$。由此可以直接核对两类多项式的行为：

$P$ 为偶多项式时，$P(\sigma_j) = P(|\lambda_j|) = P(\lambda_j)$，故 $\sum_jP(\sigma_j)|v_j\rangle\langle v_j| = P(A)$；
$P$ 为奇多项式时，$P(\sigma_j)|u_j\rangle\langle v_j| = P(|\lambda_j|)\mathrm{sign}(\lambda_j)|E_j\rangle\langle E_j| = P(\lambda_j)|E_j\rangle\langle E_j|$，故 $P^{SV}(A) = P(A)$。

也就是说，对 Hermitian 输入，只要多项式的奇偶性与电路层数一致，QSVT 实现的就是货真价实的矩阵函数 $P(A)$；符号函数正是左、右奇异向量之间的那一步符号配平。这个观察也是矩阵求逆应用的基础：$A^{-1} = \mathrm{sign}(A)\cdot|A|^{-1}$，因此用奇多项式 $P(x)\approx 1/(\kappa x)$ 就能实现 $A^{-1}$（见"应用一"）。

算法步骤详解¶

以"用 QSVT 实现 $f(A)$"为例，完整流程如下。

第一步：多项式逼近¶

将目标函数 $f: [-1, 1] \to \mathbb{C}$（必要时先做归一化缩放使 $|f|\le 1$）用 $d$ 次多项式 $P_d$ 逼近：

\[\max_{x \in [-1, 1]} |f(x) - P_d(x)| \le \varepsilon_{\mathrm{poly}} .\]

逼近的次数学与工具见 QSP 教程"逼近精度"一节，此处摘要如下：

切比雪夫（Chebyshev）截断：对解析函数给出指数收敛，例如 $f(x) = e^{-i\tau x}$ 需要 $d = O(\tau + \log(1/\varepsilon))$；
Remez 算法：求最优一致逼近，用于压低常数因子；
带平滑过渡的构造（如误差函数核）：用于符号函数、截断求逆等有不连续性的目标，额外贡献 $\log$ 因子。

若目标不具备确定奇偶性（如 $e^{-i\tau x}$），我们把它拆成偶部与奇部（$\cos\tau x$ 与 $-i\sin\tau x$），分别用两条 QSVT 序列实现，再用一个附加辅助比特做线性组合，代价只增加常数因子。

第二步：计算相位参数¶

先用 QSP 的算法（Haah 的 $O(d^2)$ 解析算法，或 Levenberg–Marquardt 迭代）求出 QSP 相位 $\vec\Psi$，再按主定理中的公式平移为 QSVT 相位：

\[\Phi_0 = \Psi_0 - \frac{\pi}{4},\qquad \Phi_k = \Psi_k - \frac{\pi}{2}\ \ (1\le k\le d-1),\qquad \Phi_d = \Psi_d - \frac{\pi}{4},\]

最后可把 $\Phi_0$ 再平移 $\pi d/4$ 以消去整体相位 $(-i)^d$。

第三步：构造块编码¶

构造 $A$ 的块编码 $U_A$（归一化常数 $\alpha$，使 $\sigma_j/\alpha\le 1$；若某些 $\sigma_j/\alpha$ 恰好等于 $1$，把 $\alpha$ 稍微放大即可，见理论推导末尾的注记）。方法包括 LCU（对 $A = \sum_k\alpha_kU_k$）、泡利分解加 PREP/SELECT、专用电路，详见块编码教程。

第四步：执行 QSVT 电路¶

按 $d$ 的奇偶选择上文两种电路之一，调用 $U_A$（及其逆）共 $d$ 次，插入 $d+1$ 个相位门。门复杂度为 $O(d\cdot C_{U_A})$，其中 $C_{U_A}$ 为单次块编码调用的门代价。

第五步：提取结果¶

QSVT 的输出本身仍然是一个块编码：辅助寄存器投影到 $|0\rangle^{\otimes m}$ 的分量恰好是 $(-i)^dP^{SV}(A/\alpha)$。我们强调，这一步没有任何本质的概率损耗——投影恒等式是算符层面的精确陈述。当把 $P^{SV}(A)$ 作用到某个输入态 $|b\rangle$ 上时，成功幅度由 $\|P^{SV}(A)|b\rangle\|$ 决定（例如求逆问题的幅度约为 $1/\kappa$ 量级），不足时可用振幅放大以 $O(1/\text{幅度})$ 次调用补足。

具体应用¶

应用一：矩阵求逆 $A^{-1}$¶

设 $\|A\|\le\alpha$、条件数为 $\kappa = \alpha\sigma_{\min}$。由"奇异值变换多项式与符号函数"一节的分析，我们取奇多项式

\[P(x) \approx \frac{1}{\kappa x},\qquad x \in [1/\kappa, 1]\]

（先做 $1/\kappa$ 归一化以保证 $|P|\le 1$；在 $|x|<1/\kappa$ 处用符号函数型截断并做平滑过渡）。带过渡带的光滑逼近给出

\[d = O\big(\kappa\log(\kappa/\varepsilon)\big)\]

次多项式。QSVT 实现的总调用次数为 $O(\kappa\log(\kappa/\varepsilon))$ 次 $U_A$，总门数为 $O(\kappa\log(\kappa/\varepsilon)\cdot C_{U_A})$。作为对照，原始 HHL 算法对条件数的依赖是 $O(\kappa^2)$ 量级（源于相位估计与受控旋转的精度需求），QSVT 版本把 $\kappa$ 依赖从二次降到线性，这是理论上的重大改进。

应用二：哈密顿量模拟 $e^{-iHt}$¶

\[P(x) \approx e^{-i\tau x},\qquad \tau = \alpha t ,\]

这是一个整函数，由 QSP 教程"逼近精度"一节的 Bernstein 椭圆分析，切比雪夫截断需要

\[d = O\big(\alpha t + \log(1/\varepsilon)\big)\]

次；$e^{-i\tau x}$ 无确定奇偶性，按第一步末尾拆成 $\cos\tau x$（偶）与 $-i\sin\tau x$（奇）两支分别实现。总门数为 $O((\alpha t + \log(1/\varepsilon))\cdot C_{U_H})$，与 QSP、Qubitization 教程给出的结果一致；对 $L$ 项泡利分解的 $H$，$C_{U_H} = O(Ln + C_{\mathrm{PREP}})$。

应用三：振幅放大（Grover 搜索）¶

把搜索问题写成投影酉算符的语言。设 $\tilde\Pi = |w\rangle\langle w|$ 是标记态上的投影，$\Pi = |s\rangle\langle s|$ 是初始均匀叠加态上的投影，$U$ 是提供搜索动力学的酉（例如由制备与反射组合而成的算子）。关键的一阶块是

\[A = \tilde\Pi\,U\,\Pi = \langle w|U|s\rangle\;|w\rangle\langle s|,\]

它只有一个奇异值

\[\sigma_1 = \big|\langle w|U|s\rangle\big|\]

（一阶算符 $c\,|w\rangle\langle s|$ 的奇异值就是系数的模长；初始制备 $U = I$ 时 $\sigma_1 = \langle w|s\rangle = 1/\sqrt{N}$）：把 $|s\rangle$ 分量搬运到 $|w\rangle$ 的振幅正是被变换的"信号"。目标多项式取为在 $x = 1/\sqrt N$ 处接近 $1$、其余处接近 $0$ 的峰形多项式，所需次数为 $d = O(\sqrt N)$，于是 QSVT 以 $O(\sqrt N)$ 次调用复现 Grover 界。在不变平面上，信号与相位门的交替复合成熟悉的反射乘积型 Grover 迭代（每迭代一次转过 $2\arcsin(1/\sqrt N)$），与 QSP 教程例子一的振幅放大图像一致；QSVT 的版本还自动给出固定点搜索（fixed-point search）——峰形多项式不会过冲。

应用四：量子 Gibbs 态制备¶

目标是制备 $\rho_\beta = e^{-\beta H}/Z$。我们用 QSVT 实现 $e^{-\beta H/2}$ 的块编码：目标多项式为 $P(x)\approx e^{-\beta\alpha x/2}$（作用在 $x = E_j/\alpha$ 上），所需次数

\[d = O\big(\beta\alpha + \log(1/\varepsilon)\big).\]

注意配分函数 $Z = \mathrm{tr}(e^{-\beta H})$ 是全局常数，不能也不需要放进多项式里；正确流程是把 $e^{-\beta H/2}$ 的块编码作用到最大混合态或均匀叠加态的纯化上，后选择辅助寄存器即得温度 $\beta$ 的 Gibbs 态。该方法用于量子机器学习和统计物理。

理论推导¶

本节完整展开从块编码到奇异值变换的全部推导。论证分六步：先建立 $A = \tilde\Pi U\Pi$ 的奇异值分解（含符号函数），再由酉性构造"缺陷向量"，证明 $(\mathcal K_j, \mathcal K'_j)$ 二维子空间对的结构（酉分解 $U = \tilde S\Lambda S^\dagger$ 与信号矩阵 $M(\sigma)$），然后把 QSVT 电路约化为每个子空间上的 QSP 序列，导出精确的相位对应并完成定理证明。

记号与前提¶

以下设 $U$ 为酉算符，$\Pi,\tilde\Pi$ 为投影，$A = \tilde\Pi U\Pi$，其奇异值满足 $0<\sigma_j<1$，且奇异值分解覆盖全部输入输出方向（$\ker A\cap\mathrm{im}\,\Pi = \{0\}$、$\mathrm{im}\,\tilde\Pi = \mathrm{span}\{|u_j\rangle\}$；边缘与退化情形见本节末尾注记）。记 $\rho_j := \sqrt{1-\sigma_j^2}$。我们还需要一个初等事实：作为酉算符的块，$A$ 必是压缩算符，即 $\sigma_j\le 1$。证明：对 $|\varphi\rangle\in\mathrm{im}\,\Pi$，

\[\|A|\varphi\rangle\| = \|\tilde\Pi U|\varphi\rangle\| \le \|U|\varphi\rangle\| = \|\varphi\rangle\|,\]

故 $\|A\|\le 1$。

第一步：投影算符的奇异值分解（含符号函数）¶

$A$ 把 $\mathrm{im}\,\Pi$ 映到 $\mathrm{im}\,\tilde\Pi$，其奇异值分解有标准形式

\[A = \sum_j \sigma_j\,|u_j\rangle\langle v_j|,\qquad \{|v_j\rangle\}_j\subset\mathrm{im}\,\Pi\ \text{正交归一},\quad \{|u_j\rangle\}_j\subset\mathrm{im}\,\tilde\Pi\ \text{正交归一},\]

其中求和遍历所有正奇异值。构造方法与普通矩阵相同：$\{|v_j\rangle\}$ 是 $A^\dagger A$ 在 $\mathrm{im}\,\Pi$ 上的非零特征向量，$\sigma_j^2$ 为对应特征值，$|u_j\rangle := A|v_j\rangle/\sigma_j$ 自动落入 $\mathrm{im}\,\tilde\Pi$ 并构成正交组。当 $A$ 是 Hermitian 矩阵时，如"数学框架"一节所述，$|v_j\rangle = \mathrm{sign}(\lambda_j)|u_j\rangle$，符号函数恰好记录了左、右奇异向量的相对符号。

第二步：酉性强制出的缺陷向量¶

现在利用 $U$ 的酉性，把每个奇异向量"补全"成一个二维子空间。对每个 $j$，考虑 $U|v_j\rangle$ 并按 $\tilde\Pi$ 分块：

\[\big\||\bar u_j'\rangle\big\|^2 = 1 - \sigma_j^2 = \rho_j^2 .\]

于是当 $0<\sigma_j<1$ 时可以定义单位向量

\[|\bar u_j\rangle := \frac{(I-\tilde\Pi)U|v_j\rangle}{\rho_j}\;\in\ker\tilde\Pi .\]

完全对称地（把 $U$ 换成 $U^\dagger$、$\Pi$ 与 $\tilde\Pi$ 互换、$A$ 换成 $A^\dagger$），利用 $\Pi U^\dagger|u_j\rangle = A^\dagger|u_j\rangle = \sigma_j|v_j\rangle$ 定义

\[|\bar v_j\rangle := \frac{(I-\Pi)U^\dagger|u_j\rangle}{\rho_j}\;\in\ker\Pi,\]

并记

\[\mathcal K_j := \mathrm{span}\{|v_j\rangle,|\bar v_j\rangle\},\qquad \mathcal K'_j := \mathrm{span}\{|u_j\rangle,|\bar u_j\rangle\}.\]

我们需要两组正交性。第一组是平凡的：$\langle v_j|\bar v_{j'}\rangle = 0$、$\langle u_j|\bar u_{j'}\rangle = 0$（像空间与核空间正交）。第二组需要计算：对 $j\ne j'$，

\[\rho_j\rho_{j'}\,\langle\bar u_j|\bar u_{j'}\rangle = \langle v_j|U^\dagger(I-\tilde\Pi)U|v_{j'}\rangle = \langle v_j|v_{j'}\rangle - \langle v_j|U^\dagger\tilde\Pi U|v_{j'}\rangle .\]

我们计算第二项。先把 $\tilde\Pi$ 作用到本步的分解式 $U|v_{j'}\rangle = \sigma_{j'}|u_{j'}\rangle + |\bar u_{j'}'\rangle$ 上，$\ker\tilde\Pi$ 中的分量被消去，得 $\tilde\Pi U|v_{j'}\rangle = \sigma_{j'}|u_{j'}\rangle$；再用 $\bar v_{j'}$ 的定义式 $U^\dagger|u_{j'}\rangle = \sigma_{j'}|v_{j'}\rangle + \rho_{j'}|\bar v_{j'}\rangle$，得

\[U^\dagger\tilde\Pi U|v_{j'}\rangle = \sigma_{j'}^2|v_{j'}\rangle + \sigma_{j'}\rho_{j'}|\bar v_{j'}\rangle,\]

于是与 $\langle v_j|v_{j'}\rangle = \delta_{jj'}$、$\langle v_j|\bar v_{j'}\rangle = 0$ 合并，得

\[\rho_j\rho_{j'}\,\langle\bar u_j|\bar u_{j'}\rangle = \delta_{jj'} - \sigma_j^2\delta_{jj'} = \rho_j^2\,\delta_{jj'},\]

即 $\langle\bar u_j|\bar u_{j'}\rangle = \delta_{jj'}$。同理 $\langle\bar v_j|\bar v_{j'}\rangle = \delta_{jj'}$。因此 $\{|u_j\rangle,|\bar u_j\rangle\}_j$ 与 $\{|v_j\rangle,|\bar v_j\rangle\}_j$ 各自构成正交归一系。

值得强调的是，$\mathcal K_j$ 与 $\mathcal K'_j$ 一般既不相等也不正交（例如 $\langle v_j|u_{j'}\rangle$ 可以是任意数）——这不影响任何推导，因为我们只需要每个族内部的正交性，以及下述"成对映射"的结构。

第三步：二维不变子空间与信号矩阵 $M(\sigma)$¶

现在计算 $U$ 在这些子空间之间的作用。由第二步的定义直接展开：

\[U|v_j\rangle = \sigma_j|u_j\rangle + \rho_j|\bar u_j\rangle. \tag{1}\]

对 $U^\dagger|u_j\rangle$ 用对称的定义式得

\[U^\dagger|u_j\rangle = \sigma_j|v_j\rangle + \rho_j|\bar v_j\rangle, \tag{2}\]

对 (2) 两边作用 $U$ 并解出 $U|\bar v_j\rangle$：

\[U|\bar v_j\rangle = \frac{|u_j\rangle - \sigma_j U|v_j\rangle}{\rho_j} = \frac{(1-\sigma_j^2)|u_j\rangle - \sigma_j\rho_j|\bar u_j\rangle}{\rho_j} = \rho_j|u_j\rangle - \sigma_j|\bar u_j\rangle. \tag{3}\]

\[U^\dagger|\bar u_j\rangle = \frac{U^\dagger(I-\tilde\Pi)U|v_j\rangle}{\rho_j} = \frac{\big(1-\sigma_j^2\big)|v_j\rangle - \sigma_j\rho_j|\bar v_j\rangle}{\rho_j} = \rho_j|v_j\rangle - \sigma_j|\bar v_j\rangle. \tag{4}\]

把 (1)、(3)（以及 (2)、(4)）排成矩阵：在基 $(|v_j\rangle,|\bar v_j\rangle)$ 与 $(|u_j\rangle,|\bar u_j\rangle)$ 之间，$U$ 与 $U^\dagger$ 的表示矩阵都是同一个二阶矩阵

\[\begin{split}M(\sigma_j) := \begin{pmatrix} \sigma_j & \rho_j \\ \rho_j & -\sigma_j \end{pmatrix},\qquad \rho_j = \sqrt{1-\sigma_j^2}. \tag{5}\end{split}\]

直接验证 $M(\sigma_j)^2 = I$（两列正交且范数为 $1$），故 $M^{-1} = M$——这解释了为什么 $U$ 与 $U^\dagger$ 的表示矩阵相同。

此外，(1)–(4) 还表明不同指标 $j$ 之间没有串扰：例如 $\langle u_{j'}|U|v_j\rangle = \sigma_j\langle u_{j'}|u_j\rangle + \rho_j\langle u_{j'}|\bar u_j\rangle = (\sigma_j\delta + \rho_j\cdot0)$ 只在 $j' = j$ 时非零，其余三个矩阵元同理。因此

\[U\,\mathcal K_j = \mathcal K'_j,\qquad U^\dagger\,\mathcal K'_j = \mathcal K_j,\qquad U\ \text{不把}\ \mathcal K_j\ \text{映到别的}\ \mathcal K'_{j'}\ (j'\ne j).\]

酉分解（信号矩阵的集中陈述）：把 $\{|v_j\rangle,|\bar v_j\rangle\}_j$ 与 $\{|u_j\rangle,|\bar u_j\rangle\}_j$ 分别扩充成全空间的正交基，定义以它们为列的酉算符 $S$ 与 $\tilde S$，并令

\[\Lambda := \Big(\bigoplus_j M(\sigma_j)\Big)\oplus \Lambda_{\mathrm{comp}},\]

其中 $\Lambda_{\mathrm{comp}}$ 是正交补上的任意酉算符（例如 $I$），则

\[U = \tilde S\,\Lambda\,S^\dagger .\]

这就是本教程意义下的"酉分解 $U = S'\,\Sigma\,S^\dagger$"：矩阵 $A$ 的全部信息（奇异值）都集中在块对角酉算符 $\Lambda$ 的 $2\times2$ 块 $M(\sigma_j)$ 里，而 $S,\tilde S$ 只是基变换。QSVT 的电路分析因此可以逐块进行。

第四步：QSVT 序列在不变子空间上的约化¶

现在考察两种相位门在这些子空间上的行为。由 $|v_j\rangle\in\mathrm{im}\,\Pi$、$|\bar v_j\rangle\in\ker\Pi$：

\[\begin{split}e^{i\phi Z_\Pi}\Big|_{\{(|v_j\rangle,|\bar v_j\rangle)\}} = \begin{pmatrix} e^{i\phi} & 0\\ 0 & e^{-i\phi} \end{pmatrix} = S(\phi),\end{split}\]

同理 $e^{i\phi Z_{\tilde\Pi}}$ 在基 $(|u_j\rangle,|\bar u_j\rangle)$ 下也是 $S(\phi)$。于是整个 QSVT 电路的轨迹是：输入 $|v_j\rangle\in\mathcal K_j$，每作用一次信号（$U$ 或 $U^\dagger$，矩阵都是 $M(\sigma_j)$）就跳到另一个子空间，同时每个相位门在当前基下都是对角的处理器 $S(\Phi_k)$。把整条电路写在 $\mathcal K_j$ 的坐标里（以 $(|v_j\rangle,|\bar v_j\rangle)$ 为第 0、1 行），对任意的 $d$ 都得到统一的表达式

\[V_j \;=\; e^{i\Phi_0 Z}\,M(\sigma_j)\,e^{i\Phi_1 Z}\,M(\sigma_j)\;e^{i\Phi_2 Z}\,M(\sigma_j)\cdots M(\sigma_j)\,e^{i\Phi_d Z}, \tag{6}\]

其中含 $d$ 个 $M$ 与 $d+1$ 个处理器。输出的提取规则是：$d$ 偶时输出落在 $\mathcal K_j$，投影 $\Pi$ 取 $|v_j\rangle$ 分量；$d$ 奇时输出落在 $\mathcal K'_j$，投影 $\tilde\Pi$ 取 $|u_j\rangle$ 分量。两种情形取到的都是乘积 (6) 的 $(0,0)$ 元。

我们用最小例子逐步验证。(d=1，奇)：

\[\begin{split}V_j = e^{i\Phi_0 Z}M e^{i\Phi_1 Z}\ \text{作用于}\ (1,0)^{\mathsf T}:\quad e^{i\Phi_1}\ \text{（处理器）}\ \to\ e^{i\Phi_1}\begin{pmatrix}\sigma\\ \rho\end{pmatrix}\ \text{（信号）}\ \to\ \begin{pmatrix}e^{i(\Phi_0+\Phi_1)}\sigma\\ e^{i(\Phi_1-\Phi_0)}\rho\end{pmatrix}\ \text{（处理器）},\end{split}\]

$(0,0)$ 元为 $\sigma e^{i(\Phi_0+\Phi_1)}$，是一个一次奇多项式。

(d=2，偶) 按时间从右向左逐步追踪 $|v_j\rangle$ 的坐标：

处理器 $e^{i\Phi_2Z}$：得 $e^{i\Phi_2}|v\rangle$；
信号 $U$（由式 (1)）：得 $e^{i\Phi_2}(\sigma|u\rangle + \rho|\bar u\rangle)$；
处理器 $e^{i\Phi_1Z}$（在 $\mathcal K'_j$ 基下对角）：得 $e^{i\Phi_2}(e^{i\Phi_1}\sigma|u\rangle + e^{-i\Phi_1}\rho|\bar u\rangle)$；
信号 $U^\dagger$（由式 (4)）：利用 $U^\dagger|u\rangle = \sigma|v\rangle+\rho|\bar v\rangle$ 与 $U^\dagger|\bar u\rangle = \rho|v\rangle-\sigma|\bar v\rangle$，得 $$e^{i\Phi_2}\Big[\big(e^{i\Phi_1}\sigma^2 + e^{-i\Phi_1}\rho^2\big)|v\rangle + \big(e^{i\Phi_1}-e^{-i\Phi_1}\big)\sigma\rho\,|\bar v\rangle\Big];$$
处理器 $e^{i\Phi_0Z}$：给 $|v\rangle$ 分量乘 $e^{i\Phi_0}$。

输出投影 $\Pi$ 取 $|v\rangle$ 分量，得二次偶多项式

\[[V_j]_{00} = e^{i(\Phi_0+\Phi_2)}\big(e^{i\Phi_1}\sigma^2 + e^{-i\Phi_1}\rho^2\big). \tag{7}\]

第五步：与 QSP 的精确对应¶

第四步把 QSVT 化成了"信号 $M(\sigma)$ + 处理器 $e^{i\Phi Z}$"的单量子比特序列，而 QSP 教程的定理是关于"信号 $W(x)$ + 处理器 $S(\phi)$"的。二者由一个恒等式联系起来：

\[M(\sigma) = -i\,S\!\left(\tfrac{\pi}{4}\right)\,W(\sigma)\,S\!\left(\tfrac{\pi}{4}\right). \tag{8}\]

验证：$S(\pi/4) = \mathrm{diag}(e^{i\pi/4}, e^{-i\pi/4})$，逐块相乘得 $S(\pi/4)WS(\pi/4) = \begin{pmatrix} i\sigma & i\rho\\ i\rho & -i\sigma\end{pmatrix} = i\,M(\sigma)$。

把 (8) 代入 (6)，并利用相邻处理器可以合并相位（$S(a)S(b) = S(a+b)$）：

\[M\,e^{i\Phi_kZ} = -i\,S(\tfrac\pi4)\,W\,S\!\left(\Phi_k+\tfrac\pi4\right),\]

相邻两个 $M$ 之间多余的 $S(\pi/4)$ 被前一个处理器吸收，使中间相位移到 $\Phi_k+\frac\pi2$；最左端 $e^{i\Phi_0Z}$ 与 $S(\frac\pi4)$ 合并为 $S(\Phi_0+\frac\pi4)$。整理得矩阵恒等式

\[V_j = (-i)^d\;S(\Psi_0)\prod_{k=1}^{d}\Big(W(\sigma_j)\,S(\Psi_k)\Big) = (-i)^d\,U_{\mathrm{QSP}}(\vec\Psi;\sigma_j), \tag{9}\]

其中 $\Psi_0 = \Phi_0+\frac\pi4$、$\Psi_k = \Phi_k+\frac\pi2$（$1\le k\le d-1$）、$\Psi_d = \Phi_d+\frac\pi4$ 正是主定理中的相位平移。这就是"QSVT 的每个不变子空间上运行着一条 QSP 序列"的精确表述；换言之，QSVT 是 $N$ 条并行的 QSP 序列，每条对应一个奇异值。

我们再用两个低阶例子核对 (9)。$d=1$：右端 $(-i)\,[S(\Phi_0+\frac\pi4)WS(\Phi_1+\frac\pi4)]_{00} = (-i)\,\sigma\,e^{i(\Phi_0+\Phi_1+\frac\pi2)} = \sigma e^{i(\Phi_0+\Phi_1)}$，与第四步的直接计算一致。$d=2$：由 $[S(a)WS(b)WS(c)]_{00} = e^{i(a+c)}(\sigma^2e^{ib}-\rho^2e^{-ib})$（两次矩阵相乘即可验证），取 $(a,b,c) = (\Phi_0+\frac\pi4,\ \Phi_1+\frac\pi2,\ \Phi_2+\frac\pi4)$：

\[[U_{\mathrm{QSP}}]_{00} = e^{i(\Phi_0+\Phi_2+\frac\pi2)}\big(\sigma^2e^{i(\Phi_1+\frac\pi2)} - \rho^2e^{-i(\Phi_1+\frac\pi2)}\big) = -\,e^{i(\Phi_0+\Phi_2)}\big(e^{i\Phi_1}\sigma^2 + e^{-i\Phi_1}\rho^2\big),\]

乘以 $(-i)^2 = -1$ 后恰为 (7)。两种算法一致。

由 (9) 与 QSP 的矩阵形式定理（QSP 教程"引理 1"），我们还得到完整的矩阵形式：存在由 $\vec\Psi$ 决定的互补多项式 $Q$（$\deg Q\le d-1$，与 $d-1$ 同奇偶），使

\[\begin{split}V_j = (-i)^d\begin{pmatrix} P(\sigma_j) & i\rho_j\,Q(\sigma_j)\\ i\rho_j\,Q^{*}(\sigma_j) & P^{*}(\sigma_j) \end{pmatrix},\qquad |P(x)|^2 + (1-x^2)|Q(x)|^2 = 1 .\end{split}\]

特别地，泄漏出投影子空间的分量由 $i\rho_jQ(\sigma_j)$ 精确给出，且在 $\sigma_j\to1$ 时自动消失。

第六步：定理的证明¶

正命题的证明。由第三步，电路的每个因子（$U$、$U^\dagger$、两种相位门）都保持子空间族 $\{\mathcal K_j,\mathcal K'_j\}$ 不变且不产生 $j$ 之间的串扰；由第四步，$U_{\vec\Phi}$ 限制到第 $j$ 对子空间上的矩阵是 (6)，输入 $|v_j\rangle$ 对应坐标 $(1,0)^{\mathsf T}$。于是：

$d$ 奇：输出态的 $\mathcal K'_j$ 坐标是 (6) 的第一列，$\tilde\Pi$ 投影取其第 $0$ 分量 $[V_j]_{00}$，而 $\ker\tilde\Pi$ 中的 $|\bar u_j\rangle$ 分量被投影消去；
$d$ 偶：输出态的 $\mathcal K_j$ 坐标是 (6) 的第一列，$\Pi$ 投影取第 $0$ 分量。

结合 (9) 与 $[U_{\mathrm{QSP}}]_{00} = P$，即得定理的两个等式。交叉项 $\langle v_{j'}|U_{\vec\Phi}|v_j\rangle$（$j'\ne j$）由无串扰性质为零；又由定理前提，$\mathrm{im}\,\Pi$ 恰由 $\{|v_j\rangle\}$ 张成、$\mathrm{im}\,\tilde\Pi$ 恰由 $\{|u_j\rangle\}$ 张成，不存在其他输入或输出方向，故两个算符等式在全体方向上成立。

Hermitian 情形。当 $A$ Hermitian、$\Pi = \tilde\Pi$ 时，$|u_j\rangle = \mathrm{sign}(\lambda_j)|E_j\rangle$、$|v_j\rangle = |E_j\rangle$（符号可任放一侧）。代入两个等式：$d$ 奇时 $\sum_jP(\sigma_j)|u_j\rangle\langle v_j| = \sum_jP(|\lambda_j|)\mathrm{sign}(\lambda_j)|E_j\rangle\langle E_j|$，对奇多项式等于 $\sum_jP(\lambda_j)|E_j\rangle\langle E_j| = P(A)$；$d$ 偶时 $\sum_jP(\sigma_j)|v_j\rangle\langle v_j| = \sum_jP(|\lambda_j|)|E_j\rangle\langle E_j|$，对偶多项式同样等于 $P(A)$。证毕。

逆命题的证明。设 $P$ 满足 QSP 可达条件。由 QSP 表示定理（QSP 教程"定理：QSP 表示定理"），存在相位 $\vec\Psi$ 使 $[U_{\mathrm{QSP}}(\vec\Psi)]_{00} = P$。按第二步的公式把 $\vec\Psi$ 平移为 QSVT 相位 $\vec\Phi$，由已证的正命题，所得电路实现 $(-i)^dP^{SV}$，整体相位用 $\Phi_0\to\Phi_0+\frac{\pi d}4$ 消去。证毕。

注记（边缘奇异值与核方向）。上述构造在 $\sigma_j = 1$ 处退化（$\rho_j = 0$，二维子空间塌缩成一维，此时 $U|v_j\rangle = |u_j\rangle$，电路退化为纯相位累积）。由于 (9) 的两端都是 $\sigma\in[0,1]$ 上的连续矩阵值函数，且在 $(0,1)$ 内恒等，故在端点处也成立；这同时说明 $\sigma_j = 1$ 的行为与 QSP 的端点条件 $|P(\pm1)| = 1$ 相容。实践中我们还可以直接把块编码的归一化常数 $\alpha$ 取为严格大于 $\|A\|$，使所有 $\sigma_j/\alpha < 1$，彻底避开退化。至于 $\ker A$ 方向：若 $A$ 在两个投影像之间存在核方向（例如 $A$ 不满秩），上述算符恒等式应理解为先把输出投影回 $\mathrm{span}\{|u_j\rangle\}$——用无串扰性质的同样归纳可以证明，从核方向出发的轨迹始终与所有 $\mathcal K'_j$ 正交，故其贡献到 $\mathrm{span}\{|u_j\rangle\}$ 的分量为零，与 $P^{SV}$ 在核方向上取零的定义一致；而电路把核方向输入泄漏到 $\mathrm{im}\,\tilde\Pi\ominus\mathrm{span}\{|u_j\rangle\}$ 的分量不受 $P^{SV}$ 约束。这不影响应用：应用中的输入态（如 $|b\rangle$ 经阈值多项式处理后）都落在 $A$ 支集的相关方向上。

注记（可达集的放宽）。在本文的电路形式下，可实现的多项式集与 QSP 完全一致（含端点条件 $|P(\pm1)| = 1$）。Gilyén 等人（2019）与 Martyn 等人（2021）利用双投影子形式与对称相位约定进一步证明：目标多项式可以作为某个复值 QSP 多项式的实部被实现，从而可达集放宽为"次数 $\le d$、奇偶性与 $d$ 一致、$|P|\le 1$"，不再要求端点条件。矩阵求逆等不满足端点条件的目标在实践中使用这一放宽形式；其完整证明涉及相位约定之间的细致换算，超出本教程范围，我们只引用结论。

数值抽查：一个 $2\times2$ 例子¶

取 Qubitization 教程例子一中的矩阵与块编码：$A = \mathrm{diag}(0.6, 0.8)$（Hermitian，$\alpha = 1$，一个辅助比特），

\[\begin{split}U_A = \begin{pmatrix} 0.6 & 0.8 \\ 0.8 & -0.6 \end{pmatrix}\oplus\begin{pmatrix} 0.8 & 0.6 \\ 0.6 & -0.8 \end{pmatrix}\end{split}\]

对 $j=1$：$U_A|0a\rangle|0s\rangle = 0.6\,|0a0s\rangle + 0.8\,|1a0s\rangle$，故 $\bar u_1 = |1a0s\rangle$、$\rho_1 = 0.8$，$\mathcal K_1 = \mathcal K'_1 = \mathrm{span}\{|0a0s\rangle, |1a0s\rangle\}$，$U_A$ 在此基下的矩阵恰为

\[\begin{split}M(0.6) = \begin{pmatrix} 0.6 & 0.8 \\ 0.8 & -0.6 \end{pmatrix}\end{split}\]

——与公式 (5) 完全一致（$\sigma = 0.6$、$\rho = 0.8$）。$j = 2$ 同理给出 $M(0.8)$，即第二个直和块。

现在运行 $d=2$、$\vec\Phi = (0, \pi/2, 0)$ 的 QSVT 电路。由恒等式 (8) 反解，这对应 QSP 相位 $\vec\Psi = (\pi/4, \pi, \pi/4)$，其多项式为 $P(x) = e^{i(\Psi_0+\Psi_2)}(\sigma^2e^{i\Psi_1}-\rho^2e^{-i\Psi_1})$。代入 $e^{i(\Psi_0+\Psi_2)} = e^{i\pi/2} = i$ 与 $e^{i\Psi_1} = e^{-i\Psi_1} = -1$：

\[P(x) = i\,(\rho^2 - \sigma^2) = i(1-2\sigma^2) = -\,i\,T_2(\sigma),\]

即（差一个相位因子的）二阶切比雪夫多项式。直接计算 $j=1$ 块上 (6) 的 $(0,0)$ 元验证：此时 (6) 为 $M\,\mathrm{diag}(i,-i)\,M$，先算右端两个因子的乘积

\[\begin{split}\mathrm{diag}(i,-i)\,M = \begin{pmatrix}i&0\\0&-i\end{pmatrix}\begin{pmatrix}0.6&0.8\\0.8&-0.6\end{pmatrix} = \begin{pmatrix}0.6i&0.8i\\-0.8i&0.6i\end{pmatrix},\end{split}\]

再左乘 $M = \begin{pmatrix}0.6&0.8\\0.8&-0.6\end{pmatrix}$，其 $(0,0)$ 元为 $0.6\times0.6i + 0.8\times(-0.8i) = 0.36i - 0.64i = -0.28i$；而定理的预言是 $(-i)^2\,P(0.6) = -P(0.6) = iT_2(0.6) = i\times(2\times0.36-1) = -0.28i$，两者一致。这与 Qubitization 教程中行走算符幂的转移矩阵恒等式 $(\langle0|\otimes I)W'^{\,n}(|0\rangle\otimes I) = T_n(A/\lambda)$ 相呼应：切比雪夫多项式 $T_d$ 既可以由行走算符的 $d$ 次幂实现，也可以由 $d$ 层 QSVT 相位电路实现，二者是同一多项式的两条电路路径。

误差传播与调用次数的最优性¶

QSVT 的误差来源有三类，我们逐项给出机制。

\[\big\|f^{SV} - P^{SV}\big\| \le \|f - P\|_{\infty} \le \varepsilon_{\mathrm{poly}} .\]

相位数值误差。设计算出的相位满足 $|\tilde\Phi_k - \Phi_k|\le\delta$。每个处理器满足 $\big\|\frac{\partial}{\partial\phi}S(\phi)\big\| = \|iZS(\phi)\| = 1$，信号 $M(\sigma)$ 与相位无关，故乘积 (6) 的每个元素作为 $\vec\Phi$ 的函数是 Lipschitz 常数 $\le d+1$ 的映射（链式法则加三角不等式），输出偏差 $O(d\delta)$。

块编码误差。设以 $\varepsilon$-精度的块编码 $\tilde U$（即 $\|\tilde A - A\|\le\varepsilon$，$\tilde A = \tilde\Pi\tilde U\Pi$）代替 $U$ 运行同样的电路。Gilyén 等人（2019）证明输出与目标的偏差为 $O(d\varepsilon)$。证明思路：块误差相当于每个不变平面上的有效信号值偏离 $\sigma_j$ 达 $O(\varepsilon)$（Weyl 扰动定理），而电路输出 (6) 的 $(0,0)$ 元作为这些信号值的多项式函数，$d$ 步累积的灵敏度为 $O(d)$；严格证明还需处理不变子空间自身的扰动与块间的串扰，见原文。

三项合并：

\[\big\|f^{SV} - \text{QSVT 输出}\big\| = O\big(d\cdot(\varepsilon + \delta) + \varepsilon_{\mathrm{poly}}\big).\]

调用次数的下界。对 $U_A$（及其逆）的每一次查询，输出矩阵元作为 $U_A$ 各矩阵元的函数，其多项式次数至多增加 $1$（乘一个矩阵元是一次乘法）。因此实现次数为 $d$ 的多项式变换至少需要 $\Omega(d)$ 次查询——这是经典多项式方法（polynomial method）的标准论证。QSVT 的 $d$ 次调用恰好达到此下界，因此在查询复杂度意义下是最优的。

复杂度总结¶

应用	多项式次数 $d$	总门数
$A^{-1}$	$O(\kappa \log(\kappa/\varepsilon))$	$O(\kappa \log(\kappa/\varepsilon) \cdot C_{U_A})$
$e^{-iHt}$	$O(\alpha t + \log(1/\varepsilon))$	$O((\alpha t + \log(1/\varepsilon))\cdot C_{U_H})$
$\mathrm{sign}(A)$	$O(\kappa \log(1/\varepsilon))$	$O(\kappa \log(1/\varepsilon) \cdot C_{U_A})$
$e^{-\beta H/2}$（Gibbs 态）	$O(\beta\alpha + \log(1/\varepsilon))$	$O(d \cdot C_{U_H})$
Grover 搜索	$O(\sqrt{N})$	$O(\sqrt{N})$

表中 $\alpha$ 为块编码归一化常数（LCU 情形为 $\lambda = \|\vec\alpha\|_1$），$C_{U_A}$ 为单次块编码调用的门数。所有情形均达到 $\Omega(d)$ 的查询下界。

与其他框架的统一关系¶

QSVT 可以重新导出本章前面各教程中的算法作为特例：

QSP（一维信号处理）：取 $A = x$ 为 $1\times1$ 矩阵、$U$ 为单量子比特信号旋转，QSVT 逐字退化为 QSP；
Qubitization：对 LCU 块编码，行走算符 $W' = U_AR_0$ 的二维不变平面正是本文的 $(\mathcal K_j,\mathcal K'_j)$ 结构在 Hermitian 情形下的实现；行走幂给出切比雪夫多项式（见数值抽查），相位交错给出一般多项式；
HHL（矩阵求逆）：$d = O(\kappa\log(\kappa/\varepsilon))$ 的奇多项式加振幅放大；
Grover（振幅放大）：一阶块编码 $A = |w\rangle\langle s|$，$d = O(\sqrt N)$；
哈密顿量模拟：$d = O(\alpha t+\log(1/\varepsilon))$，与 Trotter 的 $O(L\lambda^2t^2/\varepsilon)$-型门数（见 Trotterization 教程）相比，对精度的依赖从 $1/\varepsilon$ 改进到 $\log(1/\varepsilon)$。

这一统一不仅在理论上有审美价值，更有实际意义：所有算法共享相同的电路结构（交替的块编码与相位旋转），区别仅在于相位参数——这意味着通用的 QSVT 编译器可以一键生成各种量子算法。

实现挑战¶

1. 块编码的构造成本¶

QSVT 假定 $U_A$ 已知，但构造 $U_A$ 本身可能代价高昂：

泡利分解的 $L$ 项哈密顿量：$C_{U_A} = O(L\cdot n + C_{\mathrm{PREP}})$；
稠密矩阵：$C_{U_A} = O(N)$ 量级的 QRAM 型访问，失去量子优势；
结构化矩阵（稀疏、低秩）：$C_{U_A} = O(\mathrm{poly}(n))$。

2. 相位参数的数值精度¶

Haah 的 $O(d^2)$ 算法对大 $d$ 可能面临数值稳定性问题。当前最佳实践：

使用高精度浮点计算；
迭代求精（先用低精度求粗解，再用牛顿法细化）；
对称化约束（$\Psi_k = \Psi_{d-k}$ 型约束）降低参数空间。

3. 近期设备的限制¶

QSVT 电路需要 $d$ 次块编码调用，对近期量子设备（NISQ）来说 $d$ 可能过大。缓解策略：

低阶 QSVT（$d = O(10)$）结合经典后处理；
变分 QSVT：用参数化电路近似 QSVT 序列；
块编码的深度优化（使用专用量子门）。

近期进展¶

年份	贡献	内容
2019	Gilyén et al.	QSVT 原始论文：统一框架与完整理论
2021	Martyn et al.	QSP 与 QSVT 的等价性（Grand Unification），相位约定的系统梳理
2022 年起	多项工作	QSVT 在量子化学、Gibbs 态制备、偏微分方程与量子机器学习中的应用

总结¶

QSVT 是量子计算理论的一座里程碑。它把看似独立的量子算法统一为"对奇异值的多项式变换"这一优雅框架：奇异值分解（Hermitian 情形下由符号函数配平左、右奇异向量）与酉性共同产生一族二维不变子空间，酉分解 $U = \tilde S\Lambda S^\dagger$ 把块编码的全部谱信息压缩进 $2\times2$ 信号矩阵 $M(\sigma)$；QSVT 电路在每个不变子空间上逐块化为一条 QSP 序列，相位对应为两端平移 $\pi/4$、中间平移 $\pi/2$。由此，QSP 的表示定理、逼近理论与最优性逐字提升为矩阵情形，实现了深度最优、误差精确可控的矩阵函数计算。理解 QSVT 是理解现代量子算法设计的钥匙。

参考文献：

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.
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.

返回目录：量子计算算法教程系列

应用	多项式次数 \(d\)	总门数
\(A^{-1}\)	\(O(\kappa \log(\kappa/\varepsilon))\)	\(O(\kappa \log(\kappa/\varepsilon) \cdot C_{U_A})\)
\(e^{-iHt}\)	\(O(\alpha t + \log(1/\varepsilon))\)	\(O((\alpha t + \log(1/\varepsilon))\cdot C_{U_H})\)
\(\mathrm{sign}(A)\)	\(O(\kappa \log(1/\varepsilon))\)	\(O(\kappa \log(1/\varepsilon) \cdot C_{U_A})\)
\(e^{-\beta H/2}\)（Gibbs 态）	\(O(\beta\alpha + \log(1/\varepsilon))\)	\(O(d \cdot C_{U_H})\)
Grover 搜索	\(O(\sqrt{N})\)	\(O(\sqrt{N})\)