块编码（Block Encoding）

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

问题背景

量子计算机只能执行酉操作（量子门），但科学计算中需要处理的矩阵往往不是酉的：它们可能不是方阵、不满足 $U^{†}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,\epsilon )$-块编码是 $(m+n)$-量子比特酉算符 $U_A$，满足：

$\Vert A-\alpha \left(⟨0{|}^{\otimes m}\otimes I_{2^n}\right)U_A\left(|0{⟩}^{\otimes m}\otimes I_{2^n}\right)\Vert \le \epsilon$

其中：

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

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

$U_A=\left(\begin{array}{cc}A/\alpha +O(\epsilon )& \ast \\ \ast & \ast \end{array}\right),$

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

广义块编码

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

$\bar{A}=\left(\begin{array}{cc}A& 0\\ 0& 0\end{array}\right)\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{⟩}^{\otimes m_a}=|\mathcal{A}⟩=\frac{1}{\sqrt{\lambda }}{\sum }_{k=1}^L\sqrt{|{\alpha }_k|}|k⟩,$ 其中 $\lambda :=\Vert \vec{\alpha }{\Vert }_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⟩⟨k|\otimes \text{sgn}({\alpha }_k)U_k,$ 其中符号 $\mathrm{sgn}({\alpha }_k)={\alpha }_k/|{\alpha }_k|$ 已吸收进受控酉中。

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

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

$(⟨0{|}^{\otimes m_a}\otimes I)U_A(|0{⟩}^{\otimes m_a}\otimes I)=(⟨\mathcal{A}|\otimes I)\text{SELECT}(|\mathcal{A}⟩\otimes I).$

再利用 $⟨\mathcal{A}|k⟩=\sqrt{|{\alpha }_k|/\lambda }$，把 SELECT 的谱分解逐项代入：

$(⟨\mathcal{A}|\otimes I)\text{SELECT}(|\mathcal{A}⟩\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 =\Vert \vec{\alpha }{\Vert }_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⟩⟨P|\otimes P$

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

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

复杂度：

$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,\dots ,d_N)$，且 $|d_j|\le \alpha$。

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

$U_A={\sum }_j|j⟩⟨j|\otimes R_y(2\arccos (d_j/\alpha )),$

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

$(⟨0|\otimes I)U_A(|0⟩\otimes I)={\sum }_j|j⟩⟨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,\epsilon )$-块编码，则同一个酉算符 $U_A$ 可以视为 $\beta A$ 的 $(\beta \alpha ,m,\beta \epsilon )$-块编码（$\beta >0$）。

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

性质二：乘积

若 $U_A$ 是 $A$ 的 $({\alpha }_A,m_A,{\epsilon }_A)$-块编码，$U_B$ 是 $B$ 的 $({\alpha }_B,m_B,{\epsilon }_B)$-块编码，且两者使用互不重叠的辅助寄存器，则 $U_B\cdot U_A$ 是 $BA$ 的 $({\alpha }_A{\alpha }_B,m_A+m_B,{\alpha }_B{\epsilon }_A+{\alpha }_A{\epsilon }_B+{\epsilon }_A{\epsilon }_B)$-块编码。

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

$(⟨0_B{0}_A|\otimes I)U_B{U}_A(|0_B{0}_A⟩\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$ 与非投影部分正交。接着估计误差：由 $\Vert \tilde{B}\Vert \le 1$、$\Vert A\Vert \le {\alpha }_A+{\epsilon }_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,$

取范数得 $\Vert {\alpha }_A{\alpha }_B\tilde{B}\tilde{A}-BA\Vert \le {\alpha }_B{\epsilon }_A+{\epsilon }_B({\alpha }_A+{\epsilon }_A)$。$■$

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

性质三：线性组合

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

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

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

$a_0=\frac{c{\alpha }_A}{|c|{\alpha }_A+|d|{\alpha }_B},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⟩⟨0|\otimes U_A+|1⟩⟨1|\otimes U_B$。把辅助投影 $⟨0|\otimes ⟨0_{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{cO({\epsilon }_A)+dO({\epsilon }_B)}{|c|{\alpha }_A+|d|{\alpha }_B},$

误差项按三角不等式不超过 $(|c|{\epsilon }_A+|d|{\epsilon }_B)/(|c|{\alpha }_A+|d|{\alpha }_B)$，换算回矩阵范数即得所证。$■$

性质四：伴随

$U_A^{†}$ 是 $A^{†}$ 的 $(\alpha ,m,\epsilon )$-块编码。

验证：对块编码不等式取伴随，注意 $(⟨0|\otimes I)U_A^{†}(|0⟩\otimes I)=[(⟨0|\otimes I)U_A(|0⟩\otimes I){]}^{†}$，范数在取伴随下不变。

块编码与量子线性代数

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

矩阵函数：QSVT

给定 $A$ 的块编码 $U_A$，QSVT 可以实现 $f(A)$ 的块编码，深度 $O(\mathrm{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 /\epsilon ))$	线性方程组
$e^{-iAt}$	$O(t+\log (1/\epsilon ))$	时间演化
$\text{sign}(A)$	$O(\kappa \log (1/\epsilon ))$	奇异值变换
${\Pi }_{\le 0}(A)$	$O(\kappa \log (1/\epsilon ))$	投影
$e^{-\beta A}$	$O(\beta +\log (1/\epsilon ))$	Gibbs 态

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

量子行走：Qubitization

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

$W=\text{SELECT}\cdot (2|\mathcal{A}⟩⟨\mathcal{A}|\otimes I-I),$

其特征相位编码了 $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 /\epsilon ))$），将 QSP 相位插入量子行走，得到 $P(A/\alpha )$ 的块编码，也就是缩放后 $A^{-1}$ 的块编码；
2. 作用到 $|b⟩$ 上，得到近似 $\propto A^{-1}|b⟩=|x⟩$ 的态（成功幅度由归一化因子决定，可用振幅放大补足）；
3. 测量提取 $⟨x|M|x⟩$ 等汇总信息。

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

应用二：哈密顿量模拟

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

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

应用三：量子 Gibbs 态制备

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

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

应用四：奇异值阈值

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

$A_{\tau }={\sum }_{{\sigma }_j\ge \tau }{\sigma }_j|u_j⟩⟨v_j|$

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

块编码的资源估计

量子比特开销

矩阵结构	$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}⟩$ 需要 $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.

---

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch05-hamiltonian-qsp/block-encoding-tutorial
• 内容遵循 CC BY-NC-SA 4.0 许可协议