# 块编码详解：量子线性代数的基础设施

块编码（Block Encoding）是量子计算中实现矩阵操作的基础原语。它的核心思想是：将一个（可能非酉的）矩阵 $A$ 嵌入一个更大的酉算符 $U_A$ 的"子块"中，从而在量子电路上实现对 $A$ 的操作。块编码是 QSVT、Qubitization、量子线性代数等现代量子算法的基石。

## 问题背景

量子计算机只能执行酉操作（量子门），但科学计算中需要处理的矩阵往往不是酉的：它们可能不是方阵、不满足 $U^\dagger U = I$、甚至不是 Hermitian 的。如何在量子电路上"执行"一个非酉矩阵？

**朴素方案的失败**：

- 直接将 $A$ 编码为量子门：$A$ 不是酉算符，不能作为量子门；
- 先计算 $A$ 再酉化：计算 $A$ 本身就需要 $O(N^2)$ 经典资源；
- 用 QPE 提取特征值再构造：仅限可对角化且只需谱信息的场景。

**块编码方案**：构造一个更大的酉算符 $U_A$，使其"子块"恰好等于 $A$（乘以某个缩放因子）。

## 数学定义

### 块编码的定义

**定义**：矩阵 $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$$

其中：

- $\alpha > 0$ 是**归一化常数**。由三角不等式与 $\|(\langle 0|^{\otimes m} \otimes I)U_A(|0\rangle^{\otimes m} \otimes I)\| \le \|U_A\| = 1$ 可得 $\|A\| \le \alpha + \varepsilon$，因此 $\alpha$ 必须至少与 $\|A\|$ 同阶；
- $m$ 是**辅助量子比特数**；
- $\varepsilon$ 是**近似误差**；
- $\langle 0|^{\otimes m}$ 表示在辅助寄存器上投影到 $|0\rangle^{\otimes m}$。

**几何直觉**：$U_A$ 是 $(m+n)$-量子比特空间上的酉矩阵。将 Hilbert 空间按辅助寄存器是否处于 $|0\rangle^{\otimes m}$ 分块，则 $U_A$ 的分块矩阵形式为

$$U_A = \begin{pmatrix} A/\alpha + O(\varepsilon) & * \\ * & * \end{pmatrix},$$

即左上角的 $N \times N$ 块近似等于 $A/\alpha$，其余块（记作 $*$）无约束，只要求整体酉性。

### 广义块编码

对非方阵 $A \in \mathbb{C}^{M \times N}$（$M = 2^m$，$N = 2^n$，$m \ne n$），我们先将其零填充为方阵

$$\bar{A} = \begin{pmatrix} A & 0 \\ 0 & 0 \end{pmatrix} \in \mathbb{C}^{2^{\max(m,n)} \times 2^{\max(m,n)}},$$

再按方阵定义构造 $\bar A$ 的块编码，它作用在 $m_a + \max(m, n)$ 个量子比特上；在其"左上块"处取到的就是 $A/\alpha$。等价地，也可以把块编码定义为连接两个同维数 Hilbert 空间的酉算子，本文一律采用方阵零填充的写法。

## 块编码的构造方法

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

**适用场景**：$A$ 可表示为酉矩阵的线性组合 $A = \sum_{k=1}^{L} \alpha_k U_k$。

这是最通用的块编码构造方法。

**构造**：

1. **PREP 操作**：在辅助寄存器上制备振幅态
   $$\text{PREP}\,|0\rangle^{\otimes m_a} = |\mathcal{A}\rangle = \frac{1}{\sqrt{\lambda}} \sum_{k=1}^{L} \sqrt{|\alpha_k|}\, |k\rangle,$$
   其中 $\lambda := \|\vec{\alpha}\|_1 = \sum_k |\alpha_k|$，$m_a = \lceil\log_2 L\rceil$。该态是归一化的，因为平方振幅之和 $\sum_k |\alpha_k| / \lambda = 1$。

2. **SELECT 操作**：受控酉选择
   $$\text{SELECT} = \sum_{k=1}^{L} |k\rangle\langle k| \otimes \text{sgn}(\alpha_k)\, U_k,$$
   其中符号 $\mathrm{sgn}(\alpha_k) = \alpha_k/|\alpha_k|$ 已吸收进受控酉中。

3. **组合**：$U_A = \text{PREP}^\dagger \cdot \text{SELECT} \cdot \text{PREP}$。

**验证**：我们需要计算 $(\langle 0|^{\otimes m_a} \otimes I)\, U_A\, (|0\rangle^{\otimes m_a} \otimes I)$。由于 $\mathrm{PREP}|0\rangle^{\otimes m_a} = |\mathcal A\rangle$ 且 $\langle 0|^{\otimes m_a}\mathrm{PREP}^\dagger = \langle\mathcal A|$，插入 $\mathrm{PREP}\mathrm{PREP}^\dagger = I$ 得

$$(\langle 0|^{\otimes m_a} \otimes I)\, U_A\, (|0\rangle^{\otimes m_a} \otimes I) = (\langle\mathcal A| \otimes I)\, \text{SELECT}\, (|\mathcal A\rangle \otimes I).$$

再利用 $\langle\mathcal A|k\rangle = \sqrt{|\alpha_k|/\lambda}$，把 SELECT 的谱分解逐项代入：

$$(\langle\mathcal A| \otimes I)\, \text{SELECT}\, (|\mathcal A\rangle \otimes I) = \sum_{k=1}^{L} \sqrt{\frac{|\alpha_k|}{\lambda}}\cdot\text{sgn}(\alpha_k)\cdot\sqrt{\frac{|\alpha_k|}{\lambda}}\; U_k = \frac{1}{\lambda}\sum_{k=1}^{L} \alpha_k U_k = \frac{A}{\lambda}.$$

因此 $U_A$ 是 $A$ 的 $(\lambda, m_a, 0)$-块编码，即 $\alpha = \lambda = \|\vec{\alpha}\|_1$，$m = \lceil\log_2 L\rceil$。

**门复杂度**：

| 操作 | 门数 |
|------|------|
| PREP | $O(\text{poly}(m_a))$（取决于 $\vec{\alpha}$ 的结构） |
| SELECT | $O(L \cdot C_U)$（$C_U$ 为单个 $U_k$ 的门数） |
| $U_A$ 总计 | $O(L \cdot C_U + \text{poly}(m_a))$ |

### 方法二：Pauli 分解

**适用场景**：$A = \sum_{P \in \mathcal{P}} \alpha_P P$（泡利字符串线性组合）。

泡利字符串是幺模酉算符，因此这是 LCU 的特例：$\lambda = \sum_P |\alpha_P|$。

**SELECT 的实现**：

$$\text{SELECT} = \sum_{P} |P\rangle\langle P| \otimes P$$

每个泡利字符串 $P = \sigma_1 \otimes \sigma_2 \otimes \cdots \otimes \sigma_n$ 可由 $O(n)$ 个单比特门与 CNOT 实现（受控版本只需常数因子额外开销）。

**PREP 的实现**：制备 $|\mathcal{A}\rangle = \frac{1}{\sqrt{\lambda}} \sum_P \sqrt{|\alpha_P|} |P\rangle$，通常用均匀叠加态加受控相位旋转实现。

**复杂度**：

$$C_{U_A} = O(L \cdot n + \text{poly}(m_a))$$

其中 $L$ 为非零泡利字符串项数，$m_a = \lceil \log_2 L\rceil$。

### 方法三：直接构造（对角矩阵）

对某些结构化矩阵，可以找到更高效的块编码。

**例子**：$A = D$（对角矩阵），$D = \text{diag}(d_1, \ldots, d_N)$，且 $|d_j| \le \alpha$。

用 $m_a = 1$ 个辅助比特，取

$$U_A = \sum_j |j\rangle\langle j| \otimes R_y(2\arccos(d_j/\alpha)),$$

其中 $R_y(2\theta) = \begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{pmatrix}$。验证左上块：由于 $\langle 0|R_y(2\theta)|0\rangle = \cos\theta$，代入 $\theta = \arccos(d_j/\alpha)$ 得

$$(\langle 0| \otimes I)\, U_A\, (|0\rangle \otimes I) = \sum_j |j\rangle\langle j| \cdot \frac{d_j}{\alpha} = \frac{D}{\alpha}.$$

门数为 $O(N)$，但 $N = 2^n$ 随 $n$ 指数增长，因此该方法仅对小系统或具有结构（如稀疏、平滑）的对角矩阵实用。

### 方法四：量子随机存取存储器（QRAM）

对任意 $A$，若有 QRAM 可以高效访问矩阵元素，则可构造 $O(\text{poly}(n))$ 复杂度的块编码。但 QRAM 本身的物理实现是重大技术挑战（详见 QRAM 教程）。

## 块编码的基本性质

### 性质一：缩放

若 $U_A$ 是 $A$ 的 $(\alpha, m, \varepsilon)$-块编码，则同一个酉算符 $U_A$ 可以视为 $\beta A$ 的 $(\beta\alpha, m, \beta\varepsilon)$-块编码（$\beta > 0$）。

验证：$(\beta A)/(\beta\alpha) = A/\alpha$，左上块不变；误差按范数放大 $\beta$ 倍，即 $\|\beta A - \beta\alpha\,(\langle0|\otimes I)U_A(|0\rangle\otimes I)\| = \beta\,\|A - \alpha(\langle0|\otimes I)U_A(|0\rangle\otimes I)\| \le \beta\varepsilon$。注意我们不能把块编码乘以 $\beta$，因为 $\beta U_A$（$\beta \ne 1$）不是酉算符；改变的是"归一化常数"这一标注方式，而非电路本身。

### 性质二：乘积

若 $U_A$ 是 $A$ 的 $(\alpha_A, m_A, \varepsilon_A)$-块编码，$U_B$ 是 $B$ 的 $(\alpha_B, m_B, \varepsilon_B)$-块编码，且两者使用**互不重叠**的辅助寄存器，则 $U_B \cdot U_A$ 是 $BA$ 的 $(\alpha_A \alpha_B,\ m_A + m_B,\ \alpha_B \varepsilon_A + \alpha_A \varepsilon_B + \varepsilon_A \varepsilon_B)$-块编码。

**证明**：记 $\Pi_A = |0\rangle\langle0|^{\otimes m_A}$、$\Pi_B = |0\rangle\langle0|^{\otimes m_B}$（分别作用于两个辅助寄存器），$\Pi = \Pi_B\Pi_A$，并记 $\tilde A = (\langle0|^{\otimes m_A}\otimes I)U_A(|0\rangle^{\otimes m_A}\otimes I)$，$\tilde B$ 同理。由于 $U_A$ 不触碰 B-辅助寄存器，$\Pi_B$ 与 $U_A$ 对易，且 $\Pi_B |0\rangle^{\otimes m_B} = |0\rangle^{\otimes m_B}$、$\langle0|^{\otimes m_B}\Pi_B = \langle0|^{\otimes m_B}$。于是辅助投影可以"穿过"互不触碰的酉算符逐层剥离：

$$(\langle 0_B 0_A| \otimes I)\, U_B U_A\, (|0_B 0_A\rangle \otimes I) = \tilde B \cdot \tilde A,$$

其中交叉项（例如 $\Pi_0^B U_B (I - \Pi_0^B)$ 与 $(I-\Pi_0^B)U_A\Pi_0^B$ 型乘积）恒为零，因为右端因子中 $\Pi_B$ 与非投影部分正交。接着估计误差：由 $\|\tilde B\| \le 1$、$\|A\| \le \alpha_A + \varepsilon_A$ 与分解

$$\alpha_B\tilde B \cdot \alpha_A\tilde A - BA = \alpha_B\tilde B\,(\alpha_A \tilde A - A) + (\alpha_B\tilde B - B)\,A,$$

取范数得 $\|\alpha_A\alpha_B\, \tilde B\tilde A - BA\| \le \alpha_B\varepsilon_A + \varepsilon_B(\alpha_A + \varepsilon_A)$。$\blacksquare$

注意：若 $U_A, U_B$ **共用**同一个辅助寄存器，则上述交叉项一般不为零，$U_BU_A$ 的左上块是 $\tilde B\tilde A$ 加上一个无法控制的 $*$-块乘积，结论不成立。这正是需要独立辅助寄存器的原因。

### 性质三：线性组合

若 $U_A$、$U_B$ 分别是 $A$、$B$ 的块编码，则 $cU_A + dU_B$（$c,d\in\mathbb C$）一般不是酉算符，因此**不能**直接作为块编码。正确的做法是再引入一个辅助比特做受控选择：

**引理（线性组合）**：在性质二的记号下，对任意 $c, d \in \mathbb{C}$，存在 $cA + dB$ 的 $\big(|c|\alpha_A + |d|\alpha_B,\ 1 + m_A + m_B,\ |c|\varepsilon_A + |d|\varepsilon_B\big)$-块编码。

**验证**：新增一个辅助比特并制备叠加态 $a_0|0\rangle + a_1|1\rangle$，其中取

$$a_0 = \frac{c\,\alpha_A}{|c|\alpha_A + |d|\alpha_B},\qquad a_1 = \frac{d\,\alpha_B}{|c|\alpha_A + |d|\alpha_B}$$

（注意 $|a_0| + |a_1| = 1$，故该两分量叠加态可以用一个单比特旋转制备）。以该比特为控制执行"控 0 施加 $U_A$、控 1 施加 $U_B$"的受控酉 $\mathcal U = |0\rangle\langle0|\otimes U_A + |1\rangle\langle1|\otimes U_B$。把辅助投影 $\langle 0|\otimes\langle0_{m_A}0_{m_B}|$ 作用到 $\mathcal U$ 上，受控结构使两个分支分别贡献 $a_0\tilde A$ 与 $a_1\tilde B$，于是左上块为

$$a_0\tilde A + a_1\tilde B = \frac{cA + dB}{|c|\alpha_A + |d|\alpha_B} + \frac{c\,O(\varepsilon_A) + d\,O(\varepsilon_B)}{|c|\alpha_A + |d|\alpha_B},$$

误差项按三角不等式不超过 $(|c|\varepsilon_A + |d|\varepsilon_B)/(|c|\alpha_A + |d|\alpha_B)$，换算回矩阵范数即得所证。$\blacksquare$

### 性质四：伴随

$U_A^\dagger$ 是 $A^\dagger$ 的 $(\alpha, m, \varepsilon)$-块编码。

验证：对块编码不等式取伴随，注意 $(\langle0|\otimes I)U_A^\dagger(|0\rangle\otimes I) = \big[(\langle0|\otimes I)U_A(|0\rangle\otimes I)\big]^\dagger$，范数在取伴随下不变。

## 块编码与量子线性代数

块编码的真正威力在于它为**量子线性代数**提供了统一接口。

### 矩阵函数：QSVT

给定 $A$ 的块编码 $U_A$，QSVT 可以实现 $f(A)$ 的块编码，深度 $O(\deg(f_{\text{approx}}))$，其中 $f_{\text{approx}}$ 是 $f$ 的多项式逼近。可实现的 $f_{\text{approx}}$ 需满足幅值约束 $|f_{\text{approx}}(x)| \le 1$（$x \in [-1,1]$，必要时先做归一化缩放）并具有确定的奇偶性；一般函数可拆为奇部与偶部分别实现后再线性组合。

**常用矩阵函数**（设已归一化到 $[-1,1]$ 上）：

| 函数 | 多项式次数 $d$ | 应用 |
|------|-------------|------|
| $A^{-1}$ | $O(\kappa \log(\kappa/\varepsilon))$ | 线性方程组 |
| $e^{-iAt}$ | $O(t + \log(1/\varepsilon))$ | 时间演化 |
| $\text{sign}(A)$ | $O(\kappa \log(1/\varepsilon))$ | 奇异值变换 |
| $\Pi_{\le 0}(A)$ | $O(\kappa \log(1/\varepsilon))$ | 投影 |
| $e^{-\beta A}$ | $O(\beta + \log(1/\varepsilon))$ | Gibbs 态 |

其中 $\kappa$ 为条件数。各次数的来源见 QSP 教程的"逼近精度"一节。

### 量子行走：Qubitization

由 LCU 块编码可以构造量子行走酉算符

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

其特征相位编码了 $A$ 的奇异值信息，详见 Qubitization 教程。

### 量子相位估计（QPE）

对块编码或行走算符执行 QPE，可以读出 $A$ 的奇异值或特征值（精度 $\delta$ 需要 $O(1/\delta)$ 次调用）。

## 块编码在具体算法中的应用

### 应用一：HHL 线性方程组求解

给定方程 $Ax = b$ 与 $A$ 的块编码 $U_A$（归一化常数 $\alpha$、条件数 $\kappa$）。

**步骤**：

1. 用 QSVT 构造多项式 $P$（$|P(x)| \le 1$，$P(x) \approx 1/(\kappa x)$，$x \in [1/\kappa, 1]$，次数 $d = O(\kappa \log(\kappa/\varepsilon))$），将 QSP 相位插入量子行走，得到 $P(A/\alpha)$ 的块编码，也就是缩放后 $A^{-1}$ 的块编码；
2. 作用到 $|b\rangle$ 上，得到近似 $\propto A^{-1}|b\rangle = |x\rangle$ 的态（成功幅度由归一化因子决定，可用振幅放大补足）；
3. 测量提取 $\langle x|M|x\rangle$ 等汇总信息。

**门数**：$O(\kappa \log(\kappa/\varepsilon) \cdot C_{U_A})$——对 $\kappa$ 线性依赖，优于原始 HHL 的 $O(\kappa^2)$。

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

$H = \sum_k \alpha_k H_k$ 的 LCU 块编码归一化常数为 $\lambda = \|\vec{\alpha}\|_1$，单次调用代价 $O(L \cdot n + C_{\text{PREP}})$。

$e^{-iHt}$ 的 QSVT 实现需要逼近整函数 $x \mapsto e^{-i(\lambda t)x}$，次数 $d = O(\lambda t + \log(1/\varepsilon))$；当存在归一化常数更紧的块编码（$\alpha$ 接近 $\|H\|$）时，相应地有 $d = O(\alpha t + \log(1/\varepsilon))$。

### 应用三：量子 Gibbs 态制备

目标：制备 $\rho_\beta = e^{-\beta H}/Z$，$Z = \mathrm{tr}(e^{-\beta H})$。

1. 构造 $H$ 的块编码 $U_H$（归一化 $\alpha \ge \|H\|$）；
2. 用 QSVT 实现 $e^{-\beta H/2}$ 的块编码，所需次数为 $O(\beta\alpha + \log(1/\varepsilon))$；
3. 作用到最大混合态或均匀叠加态上并做后选择，得到温度 $\beta$ 的 Gibbs 态。

### 应用四：奇异值阈值

给定 $A$，保留奇异值大于阈值 $\tau$ 的分量，将其余置零：

$$A_\tau = \sum_{\sigma_j \ge \tau} \sigma_j |u_j\rangle\langle v_j|$$

QSVT 实现阈值函数 $f(x) = x \cdot \mathbb{1}(x \ge \tau)$ 的多项式逼近（在 $x = \tau$ 附近做 $O(\tau)$ 宽度的平滑过渡），所需次数 $d = O\big(\tfrac{1}{\tau}\log(\tfrac{1}{\varepsilon})\big)$；若记 $\kappa = 1/\tau$，即 $d = O(\kappa\log(1/\varepsilon))$。

## 块编码的资源估计

### 量子比特开销

| 矩阵结构 | $L$（项数） | 辅助比特 $m_a$ | 总量子比特 |
|----------|-----------|--------------|-----------|
| 稀疏矩阵（$s$-稀疏） | $O(ns)$ | $O(n + \log s)$ | $O(n + \log s)$ |
| 泡利分解（$L$ 项） | $L$ | $O(\log L)$ | $n + O(\log L)$ |
| 稠密矩阵 | $O(N)$ | $O(n)$ | $O(2n)$ |
| 局部哈密顿量 | $O(\text{poly}(n))$ | $O(\text{poly}\log n)$ | $O(n + \text{poly}\log n)$ |

### 门开销

对泡利分解的 $L$ 项哈密顿量：

$$C_{U_A} = O(L \cdot n + \text{poly}(\log L))$$

$O(L \cdot n)$ 来自 SELECT（$L$ 个泡利字符串，每个 $O(n)$ 门），$\text{poly}(\log L)$ 来自 PREP。

## 当前进展与挑战

### 理论进展

| 年份 | 贡献 |
|------|------|
| 2016 | Low & Chuang：块编码 + Qubitization |
| 2019 | Gilyén et al.：QSVT 统一块编码上的多项式变换 |
| 2022 | Camps & Van Beeumen：FABLE，稠密矩阵的快速近似块编码 |
| 2023 | 多项工作：高效块编码的构造优化 |

### 实现挑战

1. **PREP 电路深度**：对一般系数 $\vec{\alpha}$，制备 $|\mathcal{A}\rangle$ 需要 $O(L)$ 门——可能成为瓶颈；
2. **SELECT 的串行性**：$L$ 个受控酉操作串行执行，总深度 $O(L)$；
3. **辅助比特数**：$m_a = O(\log L)$ 对大 $L$ 可能较高；
4. **数值精度**：PREP 中的旋转角度需高精度，门错误会累积。

## 总结

块编码是量子线性代数的基石原语。它将"在量子电路上执行非酉矩阵"这一困难问题，归约为"构造更大的酉操作"的可模块化问题：LCU 给出最通用的构造，乘积与线性组合性质保证块编码在代数运算下封闭，QSVT 与 Qubitization 则在块编码之上实现任意多项式的矩阵函数。块编码由此为矩阵求逆、哈密顿量模拟、Gibbs 态制备等核心量子算法提供了统一的接口。

---

**参考文献：**

1. Low, G. H., & Chuang, I. L. (2016). *Hamiltonian simulation by qubitization.* arXiv:1610.06546.
2. Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019). *Quantum singular value transformation and beyond.* STOC 2019.
3. Camps, D., & Van Beeumen, R. (2022). *FABLE: Fast Approximate BLock Encodings.* arXiv:2205.00099.
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/)