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

问题背景

量子计算机只能执行酉操作（量子门），但科学计算中需要处理的矩阵往往是非酉的（非方阵、含奇异值、非 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$ 是归一化常数（$\|A\| \le \alpha + \varepsilon$） - $m$ 是辅助量子比特数 - $\varepsilon$ 是近似误差 - $\langle 0|^{\otimes m}$ 表示在辅助寄存器上投影到 $|0\rangle^{\otimes m}$

几何直觉：$U_A$ 是 $(m+n)$-量子比特空间的酉矩阵。将其按辅助寄存器分块：

$$U_A = \begin{pmatrix} A/\alpha & * \\ * & * \end{pmatrix}$$

左上角的 $N \times N$ 块恰好是 $A/\alpha$。

广义块编码

对非方阵 $A \in \mathbb{C}^{M \times N}$（$M = 2^m$, $N = 2^n$）：

$$U_A = \begin{pmatrix} A/\alpha & * \\ * & * \end{pmatrix}: \mathbb{C}^{2^{m_a} \cdot M} \to \mathbb{C}^{2^{m_a} \cdot N}$$

需要 $m_a$ 个辅助量子比特，$U_A$ 作用在 $m_a + \max(m, n)$ 个量子比特上。

块编码的构造方法

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

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

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

构造：

1. PREP 操作：制备辅助态 $$\text{PREP}|0\rangle^{\otimes m_a} = \frac{1}{\sqrt{A}} \sum_{k=1}^{L} \sqrt{|\alpha_k|} |k\rangle$$ 其中 $A = \|\vec{\alpha}\|_1 = \sum_k |\alpha_k|$，$m_a = \lceil\log_2 L\rceil$。

2. SELECT 操作：受控酉选择 $$\text{SELECT} = \sum_{k=1}^{L} |k\rangle\langle k| \otimes \text{sgn}(\alpha_k) U_k$$

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

验证：

$$\langle 0|^{\otimes m_a} U_A |0\rangle^{\otimes m_a} = \frac{1}{A} \sum_{k=1}^{L} \alpha_k U_k = \frac{A}{A} = \frac{A}{\|\vec{\alpha}\|_1}$$

因此 $\alpha = \|\vec{\alpha}\|_1$，$m = m_a = \lceil\log_2 L\rceil$。

门复杂度：

方法二：Pauli 分解

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

泡利字符串是自然的酉算符，LCU 的特例。

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{A}} \sum_P \sqrt{|\alpha_P|} |P\rangle$。

复杂度：

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

方法三：直接酉线性组合

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

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

块编码：用 $m_a = 1$ 辅助比特，$U_A$ 为受控旋转：

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

门数 $O(N)$，但 $N = 2^n$ 指数增长——仅在小系统实用。

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

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

块编码的基本性质

性质一：缩放

若 $U_A$ 是 $A$ 的 $(\alpha, m, \varepsilon)$-块编码，则 $\beta U_A$ 是 $\beta A$ 的 $(\beta\alpha, m, \beta\varepsilon)$-块编码（$\beta > 0$）。

性质二：乘积

若 $U_A$ 是 $A$ 的 $(\alpha_A, m, \varepsilon_A)$-块编码，$U_B$ 是 $B$ 的 $(\alpha_B, m, \varepsilon_B)$-块编码（共用辅助寄存器），则：

$$U_B \cdot U_A$$

是 $BA$ 的 $(\alpha_A \alpha_B, m, \alpha_A \varepsilon_B + \alpha_B \varepsilon_A)$-块编码。

性质三：线性组合

若 $U_A$、$U_B$ 分别是 $A$、$B$ 的块编码，$c, d \in \mathbb{R}$：

$$cU_A + dU_B$$

一般不是酉算符，因此不是块编码。需要 LCU 技术重新构造。

性质四：伴随

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

块编码与量子线性代数

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

矩阵函数：QSVT

给定 $A$ 的块编码 $U_A$，QSVT 可以实现 $f(A)$ 的块编码，深度 $O(\text{deg}(f_{\text{approx}}))$。

常用矩阵函数：

量子行走：Qubitization

$U_A$ 直接用于构造量子行走酉算符 $W(A) = \text{REF}_\Phi \cdot U_A$，其特征相位编码了 $A$ 的奇异值。

量子相位估计（QPE）

对 $U_A$ 执行 QPE，读出 $A$ 的奇异值/特征值。

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

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

给定 $Ax = b$，$A$ 的块编码 $U_A$。

步骤：

1. 用 QSVT 构造 $A^{-1}$ 的块编码（深度 $d = O(\kappa \log(\kappa/\varepsilon))$）
2. 应用到 $|b\rangle$ 的量子态编码
3. 测量提取 $\langle x|M|x\rangle$ 等汇总信息

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

应用二：哈密顿量模拟

$H = \sum_k \alpha_k H_k$ 的块编码由 LCU 给出，$\alpha = \|\vec{\alpha}\|_1$。

$e^{-iHt}$ 的 QSVT 实现深度 $O(\|H\|t + \log(1/\varepsilon))$，每次 $U_H$ 代价 $O(L \cdot n)$。

应用三：量子 Gibbs 态制备

目标：制备 $\rho_\beta = e^{-\beta H}/Z$。

1. 构造 $H$ 的块编码 $U_H$
2. 用 QSVT 实现 $e^{-\beta H/2}$ 的块编码（深度 $O(\beta)$）
3. 应用到均匀叠加态，后选择

应用四：奇异值阈值

给定 $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)$（阈值函数的多项式逼近），深度 $O(\kappa \log(1/\varepsilon))$。

块编码的资源估计

量子比特开销

门开销

对泡利分解的 $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。

当前进展与挑战

理论进展

实现挑战

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.