# Qubitization 算法详解：量子计算的离散化基石

Qubitization（量子化）由 Guang Hao Low 与 Isaac Chuang 于 2016 年提出，是量子计算中将连续的矩阵函数计算问题转化为离散酉操作的关键技术。它是量子奇异值变换（QSVT）的物理基础，为哈密顿量模拟、量子线性代数和量子搜索提供了统一的数学结构。

## 问题背景

量子算法的核心任务之一是实现矩阵函数 $f(A)$——包括 $e^{-iAt}$（时间演化）、$A^{-1}$（线性方程组求解）、投影到特定子空间等。这些操作本质上是**连续**的，而量子门电路是**离散**的。Qubitization 的贡献在于提供了一座桥梁：将任意矩阵 $A$ 嵌入一个更大的量子行走酉算符（quantum walk operator），使得对 $A$ 的多项式变换等价于对该酉算符的特征相位施加单量子比特意义下的信号处理。

### 核心困境

给定矩阵 $A$（非酉、非方阵），如何在量子电路上执行 $f(A)$？

- 若 $A$ 是酉算符，可以直接用量子门实现；
- 若 $A$ 非酉，需要某种"酉化"——这就是 Qubitization 要做的事。

## 核心思想：量子行走与酉嵌入

### 量子行走酉算符

Qubitization 的核心构造是：给定 $n$-量子比特系统上的矩阵 $A$（满足 $\|A\| \le \alpha$），构造一个量子行走酉算符 $W$，使得 $W$ 的谱与 $A$ 的奇异值直接相关。

我们采用 LCU（线性组合酉，linear combination of unitaries）形式的块编码。设 $A = \sum_{k=0}^{L-1}\alpha_k U_k$（$U_k$ 为酉，$\alpha_k \in \mathbb{R}$；不妨设 $\alpha_k \ge 0$，因为符号可以吸收进 $U_k$），记 $\lambda = \sum_k \alpha_k \ge \|A\|$。定义

$$\text{PREP}\,|0\rangle^{\otimes m} = |\mathcal{A}\rangle = \frac{1}{\sqrt{\lambda}}\sum_{k=0}^{L-1}\sqrt{\alpha_k}\,|k\rangle,\qquad \text{SELECT} = \sum_{k=0}^{L-1}|k\rangle\langle k|\otimes U_k,$$

以及辅助寄存器上的反射算子（reflection）

$$R_0 = 2|0\rangle\langle 0|^{\otimes m} - I .$$

量子行走酉算符定义为（下面两种形式相差一个 PREP 共轭，见下文）

$$W = \text{SELECT}\cdot\big(2|\mathcal{A}\rangle\langle\mathcal{A}|\otimes I - I\big),\qquad W' = U_A\cdot R_0,$$

其中 $U_A = \text{PREP}^\dagger\cdot\text{SELECT}\cdot\text{PREP}$ 是 $A$ 的 $(\lambda, m, 0)$-块编码。两种形式的等价性验证如下：利用 $2|\mathcal{A}\rangle\langle\mathcal{A}| - I = \text{PREP}\,R_0\,\text{PREP}^\dagger$（由 $|0\rangle^{\otimes m}\xrightarrow{\text{PREP}}|\mathcal{A}\rangle$ 直接代入即得）与 $\text{PREP}^\dagger\text{PREP} = I$，我们有

$$\text{PREP}^\dagger\, W\, \text{PREP} = \text{PREP}^\dagger\text{SELECT}\text{PREP}\,R_0 = U_A R_0 = W'.$$

因此 $W$ 与 $W'$ 西相似，谱完全相同；本文在推导谱结构时使用 $W$（显式 SELECT 形式便于追踪不变子空间），在使用块编码抽象时使用 $W'$。

### 量子化定理

**定理（Qubitization，Low & Chuang）**：设 $A$ 为 Hermitian 矩阵，$A = \sum_j E_j|E_j\rangle\langle E_j|$ 为其谱分解，且 $\max_j|E_j| \le \lambda$。令 $\theta_j = \arccos(E_j/\lambda) \in [0, \pi]$，则 $W$（等价地 $W'$）保持一组二维不变子空间 $\{\mathcal{K}_j\}$ 不变，且在每个 $\mathcal{K}_j$ 上（在适当的正交基下）的作用是旋转

$$W\big|_{\mathcal{K}_j} = \begin{pmatrix} \cos\theta_j & -\sin\theta_j \\ \sin\theta_j & \cos\theta_j \end{pmatrix} = R_y(2\theta_j),\qquad R_y(2\theta) := \begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{pmatrix}.$$

换言之，$W$ 的特征值为 $e^{\pm i\theta_j}$，$\cos\theta_j = E_j/\lambda$：$A$ 的谱信息被编码为行走算符的特征相位。对 $W$ 的特征相位施加多项式变换，等价于对 $E_j/\lambda$ 施加同样的多项式变换。一般（非 Hermitian）情形下，$E_j$ 换成 $A$ 的奇异值 $\sigma_j$，结论形式相同。

这一结果的深远意义在于：**对任意满足 $|p(x)|\le 1$（$x\in[-1,1]$）且具有确定奇偶性的 $d$ 次多项式 $p$，存在深度为 $O(d)$ 的量子电路实现 $p(A/\alpha)$ 的块编码**。完整证明见"理论推导"一节。

## 块编码（Block Encoding）

块编码是 Qubitization 的前置技术，这里做简要回顾，详细讨论见配套教程。

### 定义

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

$$\left\| A - \alpha \left( \langle 0|^{\otimes m} \otimes I_{2^n} \right) U_A \left( |0\rangle^{\otimes m} \otimes I_{2^n} \right) \right\| \le \varepsilon$$

即 $U_A$ 的"左上角块"（辅助寄存器投影到 $|0\rangle^{\otimes m}$ 时）近似等于 $A/\alpha$。

### 构造块编码的方法

**方法一：LCU（线性组合酉操作）**

若 $A = \sum_{k=0}^{L-1} \alpha_k U_k$（$U_k$ 为酉），则 LCU 框架天然给出块编码：PREP 制备 $|\mathcal{A}\rangle = \frac{1}{\sqrt{\lambda}} \sum_k \sqrt{|\alpha_k|} |k\rangle$（$\lambda = \|\vec{\alpha}\|_1$），SELECT 实现 $\sum_k |k\rangle\langle k| \otimes \text{sgn}(\alpha_k) U_k$，则

$$U_A = \text{PREP}^\dagger \cdot \text{SELECT} \cdot \text{PREP}$$

的左上角块恰好是 $A/\lambda$。验证只需展开 $\langle\mathcal{A}|\text{SELECT}|\mathcal{A}\rangle = \frac{1}{\lambda}\sum_k\alpha_kU_k$（逐项代入 $\langle\mathcal A|k\rangle = \sqrt{|\alpha_k|/\lambda}$）。

**方法二：Pauli 分解**

对泡利分解 $A = \sum_P \alpha_P P$，SELECT 实现为 $\sum_P |P\rangle\langle P| \otimes P$，每个泡利字符串 $P$ 可由 $O(n)$ 个门实现。

**方法三：直接构造**

若 $A$ 本身已接近酉或具有特殊结构（如对角），可直接写出更浅的块编码电路，见块编码教程的方法三。

## 量子行走酉算符的构造

### 反射算子的实现

行走算符 $W = \text{SELECT}\cdot(2|\mathcal{A}\rangle\langle\mathcal{A}|\otimes I - I)$ 中的反射 $2|\mathcal{A}\rangle\langle\mathcal{A}| - I$ 按定义展开为三个因子的乘积：

$$2|\mathcal{A}\rangle\langle\mathcal{A}| \otimes I - I = \text{PREP}\cdot R_0 \cdot \text{PREP}^\dagger,\qquad R_0 = 2|0\rangle\langle0|^{\otimes m} - I,$$

其中 $R_0$ 是辅助寄存器上的多控相位翻转：把 $m$ 个辅助比特全部为 $|0\rangle$ 的分支保持不变、其余分支加相位 $-1$。它可以用标准的多元受控门分解实现，代价 $O(m)$ 个基本门（配合 $O(m)$ 比特的干净辅助）。

### 完整构造

$$W = \text{SELECT}\cdot\big(2|\mathcal{A}\rangle\langle\mathcal{A}|\otimes I - I\big),\qquad\text{或等价地}\qquad W' = U_A\cdot R_0 .$$

**门复杂度**：$W$ 需要 1 次 SELECT、2 次 PREP 与 1 次 $R_0$，即 $O(C_{\text{SELECT}} + 2C_{\text{PREP}} + m)$；$W'$ 需要 1 次 $U_A$ 与 1 次 $R_0$。对泡利分解的 $L$ 项哈密顿量，$C_{\text{SELECT}} = O(L\cdot n)$，故单次行走调用为 $O(L\cdot n + C_{\text{PREP}})$。

### 二维不变子空间

对每个本征态 $|E_j\rangle$，关键的两条轨道是（详细推导见"理论推导"）：

$$|x_j\rangle := |\mathcal{A}\rangle|E_j\rangle,\qquad |p_j\rangle := \text{SELECT}\,|x_j\rangle,$$

且 $\mathcal{K}_j = \mathrm{span}\{|x_j\rangle, |p_j\rangle\}$ 在 $W$ 下不变（在 SELECT 为对合、即 SELECT$^2 = I$ 时成立——泡利字符串 LCU 自动满足，见理论推导末尾的一般性注记）。把 $|p_j\rangle$ 中沿 $|x_j\rangle$ 的分量剥离后，$W$ 在正交归一基下的矩阵恰为上述旋转 $R_y(2\theta_j)$。

## Qubitization 的应用

### 应用一：哈密顿量模拟

对 $H = \sum_k \alpha_k H_k$（$H_k$ 为泡利字符串），构造 $H$ 的 LCU 块编码（归一化常数 $\lambda = \|\vec\alpha\|_1$）后，行走算符 $W' = U_H R_0$ 在不变平面上的参数满足 $\cos\theta_j = E_j/\lambda$，其中 $E_j$ 为 $H$ 的本征值。

时间演化 $e^{-iHt}$ 的目标于是化为：对每个 $j$ 实现 $e^{-iE_jt} = e^{-i(\lambda t)\,(E_j/\lambda)}$，即以 $\tau = \lambda t$ 逼近整函数 $x \mapsto e^{-i\tau x}$。把量子信号处理（QSP）的相位旋转交替插入 $W'$ 之间，得到

$$(\langle 0|^{\otimes m}\otimes I)\,\widetilde{U}_{\vec\Phi}\,(|0\rangle^{\otimes m}\otimes I) \;=\; P(H/\lambda)\;\approx\; e^{-iHt},$$

其中 $P$ 是次数 $d = O(\lambda t + \log(1/\varepsilon))$ 的 QSP 多项式（逼近阶数的完整推导见 QSP 教程"逼近精度"一节）。

### 应用二：量子线性代数

HHL 算法（见配套教程）的现代版本以 Qubitization + QSP 为核心：

1. 构造 $A$ 的块编码 $U_A$（归一化常数 $\alpha$，条件数 $\kappa$）；
2. 构造行走算符 $W'(A) = U_A R_0$，取 $d = O(\kappa\log(\kappa/\varepsilon))$ 次多项式 $P$，使 $|P(x)|\le 1$ 且 $P(x)\approx 1/(\kappa x)$（$x\in[1/\kappa,1]$），将 QSP 相位插入 $W'(A)$，即得 $P(A/\alpha)$ 的块编码，也就是缩放后 $A^{-1}$ 的块编码；
3. 作用于 $|b\rangle$ 得到近似 $|x\rangle \propto A^{-1}|b\rangle$ 的态（成功幅度可用振幅放大提升）。

总调用次数为 $O(\kappa\log(\kappa/\varepsilon))$ 次 $U_A$，优于原始 HHL 的 $O(\kappa^2)$。

### 应用三：量子搜索

Grover 搜索可以重新表述为 Qubitization 的特例。令 $A = |w\rangle\langle w|$（标记态的投影，$\alpha = 1$），此时行走算符退化为两个反射的乘积

$$W = (I - 2|w\rangle\langle w|)(I - 2|s\rangle\langle s|),$$

其中 $|s\rangle$ 为均匀叠加态。它是张成于 $\{|w\rangle, |w^\perp\rangle\}$（$|w^\perp\rangle\propto |s\rangle - \langle w|s\rangle|w\rangle$）平面上的旋转，每作用一次转过角度 $2\arcsin(1/\sqrt N)$，特征值为 $e^{\pm i\theta}$ 且 $\cos\theta = 1 - 2/N$（与 $\theta = 2\arccos\sqrt{1/N}$ 给出同一对特征值，因为两者相差 $\pi$ 的补角变换）。对 $W$ 施加 QSP 多项式即可实现振幅放大，得到 $O(\sqrt N)$ 的搜索复杂度。

## 理论推导

本节给出量子化定理与核心恒等式的完整证明。为明确起见，我们对 Hermitian 的 $A$ 与泡利字符串型 LCU（此时 SELECT 为对合：SELECT$^2 = I$，因为每个泡利字符串平方为 $I$）给出完整论证；对一般酉 LCU 的推广见本节末尾的注记。以下均设系数 $\alpha_k \ge 0$、$\lambda = \sum_k\alpha_k$、$\tilde E_j := E_j/\lambda \in [-1, 1]$（$|E_j| \le \|A\| \le \lambda$）。

### 第一步：块编码在 $|0\rangle|E_j\rangle$ 上的作用

由 $U_A = \text{PREP}^\dagger\text{SELECT}\text{PREP}$ 与 $\text{PREP}|0\rangle^{\otimes m} = |\mathcal{A}\rangle$，我们有

$$U_A|0\rangle|E_j\rangle = \text{PREP}^\dagger\,\text{SELECT}\,|\mathcal{A}\rangle|E_j\rangle = \text{PREP}^\dagger|p_j\rangle,$$

其中 $|p_j\rangle := \text{SELECT}(|\mathcal{A}\rangle|E_j\rangle) = \frac{1}{\sqrt{\lambda}}\sum_k\sqrt{\alpha_k}|k\rangle\,U_k|E_j\rangle$。

**计算 $|p_j\rangle$ 沿 $|\mathcal{A}\rangle$ 方向的分量**：利用 $\langle\mathcal{A}|k\rangle = \sqrt{\alpha_k/\lambda}$，

$$(\langle\mathcal{A}|\otimes I)\,|p_j\rangle = \frac{1}{\lambda}\sum_k \alpha_k\, U_k|E_j\rangle = \frac{A|E_j\rangle}{\lambda} = \tilde E_j\,|E_j\rangle,$$

因此 $|p_j\rangle$ 与 $|x_j\rangle = |\mathcal{A}\rangle|E_j\rangle$ 的内积为 $\langle x_j|p_j\rangle = \tilde E_j$。又 $\text{SELECT}$ 是酉算符，$\|p_j\| = 1$，于是勾股定理给出剩余分量的范数：

$$\big\|\,|p_j\rangle - \tilde E_j|x_j\rangle\,\big\|^2 = 1 - \tilde E_j^2 .$$

据此定义单位向量 $|q_j\rangle := \dfrac{|p_j\rangle - \tilde E_j|x_j\rangle}{\sqrt{1-\tilde E_j^2}}$（当 $\tilde E_j = \pm 1$ 时 $\mathcal{K}_j$ 退化为一维，$W|x_j\rangle = \pm|x_j\rangle$，结论平凡成立），它满足 $(\langle\mathcal{A}|\otimes I)|q_j\rangle = 0$，即辅助寄存器部分与 $|\mathcal{A}\rangle$ 正交。

对 $\text{PREP}^\dagger|p_j\rangle$ 用同样的分解：$\text{PREP}^\dagger$ 把 $|\mathcal{A}\rangle$ 映回 $|0\rangle$、保持与 $|\mathcal{A}\rangle$ 正交的分量正交，故

$$U_A|0\rangle|E_j\rangle = \tilde E_j\,|0\rangle|E_j\rangle + \sqrt{1-\tilde E_j^2}\;|\bar q_j\rangle,\qquad |\bar q_j\rangle := \text{PREP}^\dagger|q_j\rangle,$$

且 $(\langle 0|^{\otimes m}\otimes I)|\bar q_j\rangle = (\langle\mathcal{A}|\otimes I)|q_j\rangle = 0$。

### 第二步：二维不变子空间与旋转矩阵

考虑 $W = \text{SELECT}\cdot(2|\mathcal{A}\rangle\langle\mathcal{A}|\otimes I - I)$ 在 $\mathcal{K}_j = \mathrm{span}\{|x_j\rangle, |p_j\rangle\}$ 上的作用。

**作用在 $|x_j\rangle$ 上**：$|x_j\rangle$ 的辅助寄存器恰为 $|\mathcal{A}\rangle$，被反射固定：$(2|\mathcal{A}\rangle\langle\mathcal{A}|\otimes I)|x_j\rangle = |x_j\rangle$，故

$$W|x_j\rangle = \text{SELECT}|x_j\rangle = |p_j\rangle = \tilde E_j|x_j\rangle + \sqrt{1-\tilde E_j^2}\,|q_j\rangle.$$

**作用在 $|p_j\rangle$ 上**：先把 $|p_j\rangle$ 按反射分解：由 $(\langle\mathcal{A}|\otimes I)|p_j\rangle = \tilde E_j|E_j\rangle$ 知 $(2|\mathcal{A}\rangle\langle\mathcal{A}|\otimes I)|p_j\rangle = 2\tilde E_j|x_j\rangle - |p_j\rangle$，于是

$$W|p_j\rangle = \text{SELECT}\big(2\tilde E_j|x_j\rangle - |p_j\rangle\big) = 2\tilde E_j|p_j\rangle - \text{SELECT}|p_j\rangle = 2\tilde E_j|p_j\rangle - \text{SELECT}^2|x_j\rangle.$$

这里我们使用了 $|p_j\rangle = \text{SELECT}|x_j\rangle$。**关键一步**：对泡利字符串 LCU 有 $\text{SELECT}^2 = \sum_k|k\rangle\langle k|\otimes U_k^2 = I$，因此 $\text{SELECT}^2|x_j\rangle = |x_j\rangle$，代入得

$$W|p_j\rangle = 2\tilde E_j|p_j\rangle - |x_j\rangle.$$

**换到正交归一基**：由 $|p_j\rangle = \tilde E_j|x_j\rangle + \sqrt{1-\tilde E_j^2}|q_j\rangle$ 反解 $|q_j\rangle = \big(|p_j\rangle - \tilde E_j|x_j\rangle\big)/\sqrt{1-\tilde E_j^2}$，代入上式：

$$W|q_j\rangle = \frac{W|p_j\rangle - \tilde E_j\,W|x_j\rangle}{\sqrt{1-\tilde E_j^2}} = \frac{\big(2\tilde E_j|p_j\rangle - |x_j\rangle\big) - \tilde E_j|p_j\rangle}{\sqrt{1-\tilde E_j^2}} = \frac{\tilde E_j|p_j\rangle - |x_j\rangle}{\sqrt{1-\tilde E_j^2}}.$$

再把分子中的 $|p_j\rangle = \tilde E_j|x_j\rangle + \sqrt{1-\tilde E_j^2}|q_j\rangle$ 展开：

$$W|q_j\rangle = \frac{\tilde E_j^2|x_j\rangle + \tilde E_j\sqrt{1-\tilde E_j^2}|q_j\rangle - |x_j\rangle}{\sqrt{1-\tilde E_j^2}} = -\sqrt{1-\tilde E_j^2}\,|x_j\rangle + \tilde E_j\,|q_j\rangle.$$

于是在正交归一基 $\{|x_j\rangle, |q_j\rangle\}$ 下，

$$W\big|_{\mathcal{K}_j} = \begin{pmatrix} \tilde E_j & -\sqrt{1-\tilde E_j^2} \\ \sqrt{1-\tilde E_j^2} & \tilde E_j \end{pmatrix} = \begin{pmatrix} \cos\theta_j & -\sin\theta_j \\ \sin\theta_j & \cos\theta_j \end{pmatrix} = R_y(2\theta_j),$$

其中 $\theta_j = \arccos(\tilde E_j) = \arccos(E_j/\lambda)$。这就证明了量子化定理：$W$ 的特征值为 $e^{\pm i\theta_j}$。矩阵 $R_y(2\theta_j)$ 的特征值满足 $\det(R_y - \mu I) = \mu^2 - 2\tilde E_j\mu + 1 = 0$，判别式 $4(\tilde E_j^2 - 1) \le 0$，故 $\mu = \tilde E_j \pm i\sqrt{1-\tilde E_j^2} = e^{\pm i\theta_j}$，对应的特征向量为

$$|\psi_j^{\pm}\rangle = \frac{1}{\sqrt{2}}\Big(|x_j\rangle \mp i\,|q_j\rangle\Big)$$

（直接验证 $R_y(2\theta_j)(1, \mp i)^{\mathsf T} = e^{\pm i\theta_j}(1, \mp i)^{\mathsf T}$：两行分别给出 $\cos\theta \pm i\sin\theta$ 与 $\sin\theta \mp i\cos\theta = \mp i(\cos\theta \pm i\sin\theta)$）。在 $W' = U_AR_0$ 的表象下，同样的结论在基 $\{|0\rangle|E_j\rangle, |\bar q_j\rangle\}$ 下成立，因为 $W' = \text{PREP}^\dagger W\,\text{PREP}$ 且 $\text{PREP}^\dagger|x_j\rangle = |0\rangle|E_j\rangle$。

### 第三步：核心恒等式（切比雪夫多项式）

**定理（转移矩阵恒等式）**：对一切 $n \ge 0$，

$$\big(\langle 0|^{\otimes m}\otimes I\big)\; W'^{\,n}\; \big(|0\rangle^{\otimes m}\otimes I\big) \;=\; T_n\!\left(\frac{A}{\lambda}\right) = \sum_j \cos(n\theta_j)\,|E_j\rangle\langle E_j|,$$

其中 $T_n$ 为第一类切比雪夫多项式。

**证明**：$W'|_{\mathcal{K}'_j} = R_y(2\theta_j)$（$W'$ 的不变平面 $\mathcal{K}'_j = \mathrm{span}\{|0\rangle|E_j\rangle, |\bar q_j\rangle\}$）。旋转矩阵的幂仍为旋转：$R_y(2\theta)^n = R_y(2n\theta)$（可用上面的特征分解验证：特征向量不变、特征值变为 $e^{\pm in\theta}$；或对 $n$ 归纳，用加法公式 $\cos((n{+}1)\theta) = \cos\theta\cos n\theta - \sin\theta\sin n\theta$）。因此

$$W'^{\,n}|0\rangle|E_j\rangle = \cos(n\theta_j)\,|0\rangle|E_j\rangle + \sin(n\theta_j)\,|\bar q_j\rangle.$$

现在把算符恒等式在谱分解基上展开。对任意系统态 $|\varphi\rangle = \sum_j c_j|E_j\rangle$，利用 $|\bar q_j\rangle$ 与"辅助寄存器处于 $|0\rangle^{\otimes m}$"的子空间正交（第一步已证 $(\langle 0|\otimes I)|\bar q_j\rangle = 0$），投影 $\langle0|^{\otimes m}\otimes I$ 只保留每条轨道的第一个分量：

$$\big(\langle 0|\otimes I\big)\,W'^{\,n}\,\big(|0\rangle\otimes|\varphi\rangle\big) = \sum_j c_j\cos(n\theta_j)\,|E_j\rangle.$$

再用切比雪夫多项式的定义 $T_n(\cos\theta) = \cos(n\theta)$ 与 $\cos\theta_j = E_j/\lambda$，上式即 $T_n(A/\lambda)|\varphi\rangle$。$\blacksquare$

这个恒等式就是"走转移矩阵"观点的精确表述：虽然 $W'^n$ 本身把态泄漏到庞大的联合空间中，但**从 $|0\rangle^{\otimes m}\otimes$ 出发、再投影回 $|0\rangle^{\otimes m}\otimes$ 的转移振幅**，在每个本征分支上就是 $\cos(n\theta_j)$，恰好按切比雪夫多项式依赖谱。

### 第四步：从幂到一般多项式（与 QSP 衔接）

仅有 $W'^n$ 的幂还不够——量子电路不能"免费"做幂的线性组合。正确的机制是把相位旋转直接交错插入。定义辅助寄存器上的算符

$$\widetilde{Z} := R_0 = 2|0\rangle\langle0|^{\otimes m}\otimes I - I .$$

在不变平面 $\mathcal{K}'_j = \mathrm{span}\{|0\rangle|E_j\rangle, |\bar q_j\rangle\}$ 上，$\widetilde Z$ 恰好表现为单量子比特的 $Z$：$\widetilde Z|0\rangle|E_j\rangle = +|0\rangle|E_j\rangle$（辅助比特为 $|0\rangle^{\otimes m}$，被固定）而 $\widetilde Z|\bar q_j\rangle = -|\bar q_j\rangle$（辅助部分与 $|0\rangle^{\otimes m}$ 正交，被翻转），即

$$\widetilde Z\Big|_{\mathcal{K}'_j} = \begin{pmatrix}1 & 0\\ 0 & -1\end{pmatrix} = Z .$$

因此交错序列

$$\widetilde{U}_{\vec\Phi} = e^{i\Phi_0\widetilde Z}\; W'\; e^{i\Phi_1\widetilde Z}\; W'\;\cdots\; W'\; e^{i\Phi_d\widetilde Z}$$

限制到每个 $\mathcal{K}'_j$ 上，就是以 $R_y(2\theta_j)$ 为信号、以 $e^{i\Phi_kZ}$ 为处理器的**单量子比特 QSP 序列**（信号矩阵 $R_y(2\theta)$ 与 QSP 教程中的 $W(x) = \begin{pmatrix}x & i\sqrt{1-x^2}\\ i\sqrt{1-x^2} & x\end{pmatrix}$ 相差一个固定的基变换 $\mathrm{diag}(1,-i)$ 共轭，对应 $\theta\mapsto-\theta$ 的相位约定，可吸收进相位参数）。于是 QSP 教程的表示定理逐字适用于每个平面：对任何可行的 QSP 多项式 $P$（次数 $d$、奇偶性与 $d$ 一致、$|P|\le 1$），存在 $\vec\Phi$ 使

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

且深度为 $O(d)$ 次 $W'$ 调用。这就把"多项式变换实现"从恒等式（幂）提升到了完整的一般形式。

### 一般 LCU 的注记

上述证明用到 $\text{SELECT}^2 = I$，这在 $U_k$ 为泡利字符串（或任何对合酉）时自动成立。对一般的酉线性组合 $A = \sum_k\alpha_kU_k$，标准做法是把每个 $U_k$ 嵌入对合（involution）$\widehat{U}_k = \begin{pmatrix} 0 & U_k \\ U_k^\dagger & 0\end{pmatrix}$（补一个辅助比特即可，$\widehat U_k^2 = I$ 直接由分块乘法验证），对 $\sum_k\alpha_k\widehat U_k$ 重复上述论证，再限制回原系统的块上，即得同样的谱结论。这一处理属于 Gilyén–Su–Low–Wiebe（2019）的标准框架，本文不再展开。

## 具体例子

### 例子一：2×2 矩阵的 Qubitization

令 $A = \begin{pmatrix} 0.6 & 0 \\ 0 & 0.8 \end{pmatrix}$。$A$ 是 Hermitian 的，本征值即 $E_0 = 0.6$、$E_1 = 0.8$（也正是它的奇异值），本征向量为 $|E_0\rangle = |0\rangle$、$|E_1\rangle = |1\rangle$。

**构造块编码**（$\alpha = 1$，一个辅助比特）：取

$$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},$$

即 $\langle0|_aU_A|0\rangle_a = \mathrm{diag}(0.6, 0.8) = A$。两个直和块都是形如 $\begin{pmatrix}d & \sqrt{1-d^2}\\ \sqrt{1-d^2} & -d\end{pmatrix}$ 的反射（平方为 $I$），故 $U_A$ 是酉的——这正是块编码教程方法三中 $R_y$ 型构造的实数化版本。

**构造行走算符**：$W' = U_A\cdot R_0$，其中 $R_0 = 2|0\rangle\langle0|_a - I = \mathrm{diag}(1,-1)$（作用在辅助比特上）。把联合空间按系统基分成两个二维块，分别在基 $(|0\rangle_a|0\rangle_s, |1\rangle_a|0\rangle_s)$ 与 $(|0\rangle_a|1\rangle_s, |1\rangle_a|1\rangle_s)$ 下计算：

$$W'\Big|_{\mathrm{span}\{|00\rangle,|10\rangle\}} = \begin{pmatrix} 0.6 & -0.8 \\ 0.8 & 0.6 \end{pmatrix},\qquad W'\Big|_{\mathrm{span}\{|01\rangle,|11\rangle\}} = \begin{pmatrix} 0.8 & -0.6 \\ 0.6 & 0.8 \end{pmatrix},$$

即旋转角 $\theta_0 = \arccos(0.6) \approx 0.927$、$\theta_1 = \arccos(0.8) \approx 0.644$，与量子化定理的预言 $\theta_j = \arccos(E_j/\alpha)$ 一致。$W'$ 的特征值为 $e^{\pm i\cdot0.927}$ 与 $e^{\pm i\cdot0.644}$。

**核心恒等式的数值抽查**（$j = 0$）：$T_2(0.6) = 2(0.6)^2 - 1 = -0.28$。直接计算 $W'^2$ 在第一块上的 $(0,0)$ 元：

$$\begin{pmatrix} 0.6 & -0.8 \\ 0.8 & 0.6 \end{pmatrix}^2 = \begin{pmatrix} 0.36-0.64 & -0.96 \\ 0.96 & 0.64-0.36 \end{pmatrix},\qquad (W'^2)_{00} = -0.28 = T_2(0.6)\;\checkmark$$

### 例子二：横场 Ising 的量子行走

一维横场 Ising 模型，$n = 4$ 量子比特：

$$H = -Z_1 Z_2 - Z_2 Z_3 - Z_3 Z_4 - 0.5(X_1 + X_2 + X_3 + X_4)$$

泡利分解：$L = 7$ 项，归一化常数 $\lambda = 3\times1 + 4\times0.5 = 5$（注意 $\lambda = \|\vec\alpha\|_1 \ge \|H\|$，这里 $\lambda$ 是 1-范数而非算符范数）。

1. **块编码**：$U_H = \text{PREP}^\dagger \cdot \text{SELECT} \cdot \text{PREP}$，辅助寄存器 $m = \lceil\log_2 7\rceil = 3$ 量子比特。PREP 制备

   $$|\mathcal{A}\rangle = \tfrac{1}{\sqrt{5}}\big(\,|{-}Z_1Z_2\rangle + |{-}Z_2Z_3\rangle + |{-}Z_3Z_4\rangle + \sqrt{0.5}\,\big(|{-}X_1\rangle + |{-}X_2\rangle + |{-}X_3\rangle + |{-}X_4\rangle\big)\,\big),$$

   其中 $|{-}P\rangle$ 标记受控算符为 $-P$ 的分支（负号吸收进 SELECT）。振幅平方和 $= (3\times1 + 4\times0.5)/5 = 1$，确为归一化态。SELECT 为 7 个受控泡利字符串的求和，且 SELECT$^2 = I$（每个 $\pm P$ 平方为 $I$），满足理论推导的前提。

2. **$W'$ 的特征相位**：$\theta_j = \arccos(E_j/5)$，其中 $E_j\in[-\|H\|,\|H\|]$ 为 $H$ 的本征值（$H$ 的谱对称于 $0$，故相位成对出现 $\pm\theta_j$）。

3. **施加 QSP**：把相位旋转 $e^{i\Phi_kR_0}$ 与 $W'$ 交错，即可实现 $P(H/5)$；例如取 $P(x)\approx e^{-i(5t)x}$ 得到 $e^{-iHt}$，所需次数 $d = O(5t + \log(1/\varepsilon))$。

## 复杂度总结

| 操作 | 门数 |
|------|------|
| 块编码 $U_A$（泡利分解，$L$ 项） | $O(L \cdot n + C_{\text{PREP}})$ |
| 反射 $R_0$ | $O(m)$ |
| 单次 $W'$ 调用 | $O(L \cdot n + C_{\text{PREP}})$ |
| $d$ 次 $W'$ 的多项式变换 | $O(d \cdot (L\cdot n + C_{\text{PREP}}))$ |

对比（模拟 $e^{-iHt}$，$\lambda = \|\vec\alpha\|_1$）：

| 方法 | 门数 |
|------|----------------------|
| Trotter（$r$ 步） | $O(r \cdot L \cdot n)$ |
| LCHS | $O(L \cdot d \cdot e^{\|\alpha\|_1 t})$（含后选择） |
| **Qubitization + QSP** | $O\big((\lambda t + \log(1/\varepsilon))\cdot(L\cdot n + C_{\text{PREP}})\big)$ |

正文的推导给出了表中第三行：$d = O(\lambda t+\log(1/\varepsilon))$ 次行走调用，每次 $O(Ln + C_{\text{PREP}})$ 门。Qubitization + QSP 无需后选择，误差界严格可控，是目前已知的渐近最优哈密顿量模拟方法之一。

## 与 QSVT 的关系

量子奇异值变换（QSVT）是 Qubitization 的自然推广：

- Qubitization 将 $A$ 的奇异值（Hermitian 情形下为本征值）映射为量子行走酉算符的特征相位；
- QSP 对每个二维不变平面施加任意满足幅值与奇偶性约束的多项式变换（通过交替的 $W'$ 调用与反射相位旋转 $e^{i\Phi\widetilde Z}$，注意信号始终是单次 $W'$，而非其幂次）；
- 两者结合实现了对 $A$ 的任意多项式的块编码，深度 $O(\deg p)$。

QSVT 的详细内容见配套教程。

## 总结

Qubitization 是量子计算中的核心基础设施。它通过将矩阵的谱信息编码为量子行走酉算符的特征相位，把"矩阵函数计算"转化为"多项式逼近 + 量子门操作"的离散问题：二维不变子空间给出精确的旋转结构（$R_y(2\theta_j)$），转移矩阵恒等式给出切比雪夫多项式的精确实现，相位交错则把它推广为完整的 QSP 多项式。这一技术不仅统一了哈密顿量模拟、量子线性代数和量子搜索的算法设计，也是理解 QSVT 等现代量子算法框架的必要基础。

---

**参考文献：**

1. Low, G. H., & Chuang, I. L. (2016). *Hamiltonian simulation by qubitization.* arXiv:1610.06546.
2. Low, G. H., & Chuang, I. L. (2017). *Optimal Hamiltonian simulation by quantum signal processing.* Physical Review Letters, 118(1), 010501.
3. Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019). *Quantum singular value transformation and beyond.* STOC 2019.
4. Childs, A. M., Kothari, R., & Somma, R. D. (2017). *Quantum algorithm for systems of linear equations with exponentially improved dependence on precision.* SIAM Journal on Computing, 46(6), 1920-1950.
---

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