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

问题背景

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

核心困境

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

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

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

量子行走酉算符

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

令 $A \in \mathbb{C}^{N \times N}$（$N = 2^n$），并假设已知其块编码（Block Encoding）：

$$\langle 0|_a U_A |0\rangle_a \otimes I_s = A / \alpha$$

其中 $\alpha$ 是归一化常数，$U_A$ 是 $(m+n)$-量子比特酉算符，$a$ 是 $m$ 个辅助量子比特，$s$ 是 $n$ 个系统量子比特。

Qubitization 构造如下酉算符：

$$W(A) = \text{REF}_\Phi \cdot U_A$$

其中 $\text{REF}_\Phi = I - 2|\Phi\rangle\langle\Phi|$ 是关于态 $|\Phi\rangle = |0\rangle_a |\phi\rangle_s$ 的反射算符，$|\phi\rangle_s$ 是系统寄存器的某个参考态（通常为 $|0\rangle^{\otimes n}$）。

谱定理

定理（Low & Chuang, 2016）：设 $A = \sum_j \sigma_j |u_j\rangle\langle v_j|$ 是 $A$ 的奇异值分解，$\sigma_j \in [0, 1]$。令 $\theta_j = \arccos(\sigma_j)$，则 $W(A)$ 在 $\text{span}\{|u_j\rangle, |v_j\rangle\}$ 的每个二维子空间上，其作用等价于一个二维旋转：

$$W(A) \big|_{\text{span}\{|u_j\rangle, |v_j\rangle\}} = \begin{pmatrix} \sigma_j & -\sqrt{1-\sigma_j^2} \\ \sqrt{1-\sigma_j^2} & \sigma_j \end{pmatrix} = R_y(2\theta_j)$$

换言之，$W(A)$ 的特征值为 $e^{\pm i\theta_j}$（$\theta_j = \arccos(\sigma_j)$），奇异值被编码为特征相位。对 $W(A)$ 施加关于 $\theta_j$ 的多项式变换，等价于对 $\sigma_j$ 施加相应变换。

这一结果的深远意义在于：对任意多项式 $p$，存在量子电路实现 $\sum_j p(\sigma_j) |u_j\rangle\langle v_j|$，且电路深度为 $O(\deg(p))$。

块编码（Block Encoding）

块编码是 Qubitization 的前置技术，需先理解其原理。

定义

矩阵 $A \in \mathbb{C}^{N \times 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$ 时）近似等于 $A/\alpha$。

构造块编码的方法

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

若 $A = \sum_{k=1}^{L} \alpha_k U_k$（$U_k$ 为酉），则 LCU 框架天然给出块编码：

1. PREP：制备 $|\mathcal{A}\rangle = \frac{1}{\sqrt{\|\vec{\alpha}\|_1}} \sum_k \sqrt{|\alpha_k|} |k\rangle$
2. 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 / \|\vec{\alpha}\|_1$。

方法二：Pauli 分解

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

方法三：酉线性组合

若 $A$ 本身已是酉矩阵的线性组合，块编码的代价主要在 PREP 电路。

量子行走酉算符的构造

REF 操作的实现

反射算符 $\text{REF}_\Phi = I - 2|\Phi\rangle\langle\Phi|$ 的实现：

$$\text{REF}_\Phi = (I_a \otimes \text{REF}_0^s) \cdot (Z_0^a \otimes I_s)$$

其中： - $Z_0^a = I - 2|0\rangle\langle 0|$ 是辅助寄存器上的相位翻转 - $\text{REF}_0^s = I - 2|0\rangle\langle 0|$ 是系统寄存器上的相位翻转

两个反射的实现各需 $O(n)$ 个 CNOT 门（多控 $Z$ 门分解）。

完整构造

$$W(A) = \text{REF}_\Phi \cdot U_A$$

门复杂度：$\text{REF}_\Phi$ 需 $O(n)$ 门，$U_A$ 取决于块编码的构造方式。对泡利分解的 $L$ 项哈密顿量，$U_A$ 需 $O(L \cdot n)$ 门。

二维子空间的作用

对每个奇异值 $\sigma_j$，$W(A)$ 限制在 $\text{span}\{|u_j\rangle, |v_j\rangle\}$ 上的矩阵表示（在合适的正交基下）：

$$W(A) \to \begin{pmatrix} \sigma_j & -\sqrt{1-\sigma_j^2} \\ \sqrt{1-\sigma_j^2} & \sigma_j \end{pmatrix} = \exp\left(-i\theta_j \sigma_y\right), \quad \theta_j = \arccos(\sigma_j)$$

证明概要：

1. 对 $|v_j\rangle$（$A$ 的右奇异向量）： $$\text{REF}_\Phi \cdot U_A |0\rangle |v_j\rangle = \text{REF}_\Phi \left(\sigma_j |0\rangle |u_j\rangle + \sqrt{1-\sigma_j^2} |\Phi^\perp\rangle\right)$$ $$= \sigma_j |0\rangle |u_j\rangle - \sqrt{1-\sigma_j^2} |\Phi^\perp\rangle$$

2. 其中 $|\Phi^\perp\rangle$ 是与 $|\Phi\rangle$ 正交的分量。

3. 类似地计算 $W(A)$ 对 $|0\rangle|u_j\rangle$ 的作用，得到上述二维旋转矩阵。

Qubitization 的应用

应用一：哈密顿量模拟

对 $H = \sum_k \alpha_k H_k$（$H_k$ 为酉），构造 $H$ 的块编码后，$W(H/\|H\|)$ 的特征相位为 $\theta_j = \arccos(E_j/\|H\|)$，其中 $E_j$ 为 $H$ 的本征值。

时间演化 $e^{-iHt}$ 可以通过量子信号处理（QSP）施加关于 $\cos\theta_j$ 的切比雪夫多项式来近似：

$$e^{-iHt} \approx \sum_j T_d(E_j/\|H\|) |u_j\rangle\langle u_j|$$

其中 $T_d$ 是 $d$ 次切比雪夫多项式。QSP 的详细内容见配套教程。

应用二：量子线性代数

HHL 算法（见配套教程）的现代版本使用 Qubitization + QPE：

1. 构造 $A^{-1}$ 的块编码（通过 $A$ 的块编码 + QPE 后选择）
2. 对 $W(A)$ 执行 QPE 读出特征值
3. 用受控旋转实现 $1/\sigma_j$

总复杂度为 $O(\kappa \cdot \log(1/\varepsilon))$ 个 $U_A$ 调用，优于原始 HHL 的 $O(\kappa^2)$。

应用三：量子搜索

Grover 搜索可以重新表述为 Qubitization 的特例。令 $A = |w\rangle\langle w|$（标记态的投影），$W(A)$ 的特征相位为 $0$（在 $|w\rangle$ 方向）或 $\pi/2$（在正交方向），对 $W(A)$ 施加 QSP 即可实现 Grover 的 $O(\sqrt{N})$ 搜索。

理论推导

奇异值到特征相位的映射

定理：设 $A = \sum_j \sigma_j |u_j\rangle\langle v_j|$（$\sigma_j \ge 0$），$W(A) = \text{REF}_\Phi \cdot U_A$。则 $W(A)$ 的特征分解为：

$$W(A) = \sum_{j} \left( e^{i\theta_j} |\psi_j^+\rangle\langle\psi_j^+| + e^{-i\theta_j} |\psi_j^-\rangle\langle\psi_j^-| \right) + \Pi_\perp$$

其中： - $\theta_j = \arccos(\sigma_j) \in [0, \pi/2]$ - $|\psi_j^\pm\rangle = \frac{1}{\sqrt{2}} \left(|v_j\rangle \pm i |u_j\rangle\right)$（在合适的相位约定下） - $\Pi_\perp$ 是 $A$ 的核空间（$\sigma_j = 0$ 的子空间）上的投影

证明：

在二维子空间 $\{|v_j\rangle, |u_j\rangle\}$ 上，令 $|v_j\rangle \perp |0\rangle|\phi\rangle$（$|v_j\rangle$ 的辅助寄存器部分不一定与 $|0\rangle$ 平行，这里用理想情况说明）。

$$U_A |0\rangle|v_j\rangle = \sigma_j |0\rangle|u_j\rangle + \sqrt{1-\sigma_j^2} |v_j^\perp\rangle$$

$$\text{REF}_\Phi U_A |0\rangle|v_j\rangle = \sigma_j |0\rangle|u_j\rangle - \sqrt{1-\sigma_j^2} |v_j^\perp\rangle$$

定义 $|\tilde{v}_j\rangle = \sqrt{1-\sigma_j^2}^{-1} |v_j^\perp\rangle$，在 $\{|v_j\rangle, |\tilde{v}_j\rangle\}$（或适当对称化的基）中，$W(A)$ 是 $2 \times 2$ 旋转矩阵 $R_y(2\theta_j)$。

$R_y(2\theta_j)$ 的特征值为 $e^{\pm i\theta_j}$，对应特征向量为：

$$|\psi_j^\pm\rangle = \frac{1}{\sqrt{2}} (|v_j\rangle \mp i|\tilde{v}_j\rangle) \qquad \blacksquare$$

多项式变换的实现

推论：对任意 $d$ 次实多项式 $p(x)$ 满足 $|p(x)| \le 1$（$x \in [-1, 1]$），存在深度为 $O(d)$ 的量子电路 $V$，使得：

$$V \cdot |\Phi\rangle = \sum_j p(\sigma_j) |u_j\rangle\langle v_j| \cdot |\Phi\rangle + \text{误差}$$

证明思路：由谱定理，$W(A)^k$ 在每个二维子空间上为 $R_y(2k\theta_j)$。利用切比雪夫多项式 $T_k(\cos\theta) = \cos(k\theta)$，有：

$$\sum_{k=0}^{d} c_k T_k(\sigma_j) = \sum_{k=0}^{d} c_k \cos(k\theta_j) = \sum_{k=0}^{d} c_k \cdot \text{Re}\left[e^{ik\theta_j}\right]$$

因此 $\sum_k c_k T_k(\sigma_j)$ 可通过 $W(A)$ 的幂次的线性组合实现，深度 $O(d)$（每次 $W(A)$ 为常数深度）。多项式系数 $c_k$ 由切比雪夫展开确定。

具体例子

例子一：2×2 矩阵的 Qubitization

令 $A = \begin{pmatrix} 0.6 & 0 \\ 0 & 0.8 \end{pmatrix}$，奇异值为 $\sigma_0 = 0.6$，$\sigma_1 = 0.8$。

奇异向量为 $|u_0\rangle = |v_0\rangle = |0\rangle$，$|u_1\rangle = |v_1\rangle = |1\rangle$。

$\theta_0 = \arccos(0.6) \approx 0.927$，$\theta_1 = \arccos(0.8) \approx 0.644$。

构造块编码：$A$ 已是对角矩阵，$U_A = \text{diag}(0.6, 0.8, \cdot, \cdot) \oplus \text{适当补全}$。$U_A$ 需要一个辅助量子比特，块编码 $\langle 0|_a U_A |0\rangle_a = A$。

REF 操作：$\text{REF}_\Phi = (I \otimes Z) \cdot (Z \otimes I)$（两个单量子比特反射）。

$W(A)$ 的特征值：$e^{\pm i \cdot 0.927}$ 和 $e^{\pm i \cdot 0.644}$。

例子二：横场 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$ 项，$\|H\|_1 = 3 + 2 = 5$。

1. 块编码：$U_H = \text{PREP}^\dagger \cdot \text{SELECT} \cdot \text{PREP}$，辅助寄存器 $m = \lceil\log_2 7\rceil = 3$ 量子比特。PREP 制备 $|\mathcal{A}\rangle = \frac{1}{\sqrt{5}}(\sqrt{1}|Z_1Z_2\rangle + \sqrt{1}|Z_2Z_3\rangle + \sqrt{1}|Z_3Z_4\rangle + \sqrt{0.5}|X_1\rangle + \cdots)$。

2. $W(H/5)$ 的特征相位：$\theta_j = \arccos(E_j/5)$，其中 $E_j$ 为 $H$ 的本征值。

3. 对 $W(H/5)$ 施加 QSP，可实现 $e^{-iHt}$ 或 $H$ 的其他函数。

复杂度总结

对比：

Qubitization + QSP 无需后选择（对单次迭代），误差界严格可控，是目前已知的渐近最优哈密顿量模拟方法之一。

与 QSVT 的关系

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

• Qubitization 将 $A$ 的奇异值映射为量子行走酉算符的特征相位
• QSVT 对这些特征相位施加任意多项式变换（通过交替的 $W(A)$ 幂次和相位旋转）
• 两者结合实现了对 $A$ 的任意奇偶多项式变换，深度 $O(\deg(p))$

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

总结

Qubitization 是量子计算中的核心基础设施。它通过将矩阵的奇异值编码为量子行走酉算符的特征相位，将”矩阵函数计算”转化为”多项式逼近 + 量子门操作”的离散问题。这一技术不仅统一了哈密顿量模拟、量子线性代数和量子搜索的算法设计，也是理解 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.