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

块编码（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$ 的分块矩阵形式为

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

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

广义块编码¶

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

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

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

块编码的构造方法¶

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

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

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

构造：

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$。
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|$ 已吸收进受控酉中。
组合：$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$）。

性质二：乘积¶

若 $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$）。

步骤：

用 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}$ 的块编码；
作用到 $|b\rangle$ 上，得到近似 $\propto A^{-1}|b\rangle = |x\rangle$ 的态（成功幅度由归一化因子决定，可用振幅放大补足）；
测量提取 $\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})$。

构造 $H$ 的块编码 $U_H$（归一化 $\alpha \ge \|H\|$）；
用 QSVT 实现 $e^{-\beta H/2}$ 的块编码，所需次数为 $O(\beta\alpha + \log(1/\varepsilon))$；
作用到最大混合态或均匀叠加态上并做后选择，得到温度 $\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	多项工作：高效块编码的构造优化

实现挑战¶

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

总结¶

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

参考文献：

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

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

函数	多项式次数 \(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 态

矩阵结构	\(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)\)

操作	门数
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))\)