⚛️ quantum physics

Reducing C-NOT Counts for State Preparation and Block Encoding via Diagonal Matrix Migration

该论文提出了一种基于对角矩阵迁移技术的算法，通过利用对角矩阵与绕 z 轴均匀控制旋转的交换性，显著降低了量子态制备和块编码中的 C-NOT 门数量，使其在通用态、单辅助比特块编码及低秩矩阵场景下均优于现有最优界限。

原作者： Zexian Li, Guofeng Zhang, Xiao-Ming Zhang

发布于 2026-03-18

📖 1 分钟阅读🧠 深度阅读

原作者： Zexian Li, Guofeng Zhang, Xiao-Ming Zhang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文主要讲的是如何让量子计算机“干活”时更省力、更省钱。

为了让你轻松理解，我们可以把量子计算机想象成一个超级复杂的乐高积木工厂，而这篇论文的作者（李泽贤、张国庆、张小鸣）就是两位天才的“积木搭建大师”。

1. 背景：为什么要优化？

在量子计算的世界里，要解决科学问题（比如模拟新药分子、优化物流路线），我们需要先给计算机“输入”数据。

状态准备（State Preparation）：就像是把一堆散乱的乐高积木，按照特定的形状拼成一个初始的“模型”。
块编码（Block Encoding）：就像是把一张复杂的“图纸”（矩阵）塞进一个更大的“盒子”（量子电路）里，让机器能读懂并处理它。

问题在于：以前的搭建方法太笨重了。每多拼一块积木，就需要很多“连接件”（C-NOT 门，这是量子电路里最贵、最容易出错的零件）。如果连接件太多，整个模型还没拼好，积木就散架了（因为现在的量子计算机很容易出错）。

2. 核心魔法：对角矩阵“大迁徙” (Diagonal Matrix Migration)

作者提出了一种叫**“对角矩阵迁徙”**的新技巧。这听起来很学术，但我们可以用一个生动的比喻：

想象你在整理一个巨大的衣柜（量子电路）。

旧方法：你每挂一件衣服（执行一个操作），都要把衣柜里的隔板（对角矩阵）挪来挪去，每挪一次都要消耗很多力气（C-NOT 门）。
新方法（迁徙）：作者发现，有些隔板（对角矩阵）其实是可以**“滑过去”**的！因为它们和某些操作（比如绕 Z 轴旋转）互不干扰。
- 这就好比你发现，把隔板从左边移到右边，衣服不会掉下来，反而能把原本需要分两步做的动作合并成一步。
- 通过这种“滑移”和“合并”，他们成功省下了大量的连接件。

3. 他们做到了什么？（三大成就）

成就一：拼模型更省料了（状态准备优化）

以前：拼一个 $n$ 个量子比特的模型，大概需要 $23/24 \times 2^n$ 个连接件。
现在：利用“迁徙”技巧，只需要 $11/12 \times 2^n$ 个连接件。
比喻：以前拼一个 10 层的乐高城堡需要 1000 块连接件，现在只需要 900 块。虽然看起来只少了 10%，但在量子世界里，这相当于少用了近一半的昂贵零件，让模型更稳定。

成就二：塞图纸更聪明了（块编码优化）

以前：要把一张复杂的图纸塞进盒子里，需要很多连接件，而且有时候塞进去的图纸会被“放大”变形（归一化因子不够好）。
现在：他们设计了一个**“单助手”协议**（Single Ancilla），只用一个额外的“助手”量子比特，就能把图纸塞进去，而且变形最小（使用了最佳的光谱范数）。
惊人之处：他们的连接件数量甚至比理论上“拼一个完美立方体”（幺正合成）的最低要求还要少！这就像是你用拼普通积木的力气，拼出了一个完美的球体，打破了之前的认知。

成就三：专治“简单”图纸（低秩矩阵优化）

现实中的很多数据（比如推荐系统、大语言模型）其实有很多部分是重复的（低秩）。
作者发现，对于这种“简单”的图纸，不需要用全副武装的方法。他们专门设计了一套**“精简版”流程**，连接件数量随着数据的“简单程度”线性减少。
比喻：如果图纸上全是空白，你就不需要把整个衣柜都拆了重装，只需要把空白部分盖住就行，省料效果极佳。

4. 总结与意义

这篇论文的核心思想就是：不要死板地按部就班，要学会利用数学规律（交换律）来“偷工减料”。

对科学界的影响：这意味着未来的量子算法可以运行在更小的、更容易制造的量子芯片上，因为对“连接件”的需求降低了。
通俗结论：作者发明了一种**“更聪明的拼法”**，让量子计算机在处理数据输入时，更省钱（C-NOT 更少）、更稳定（出错更少）、更灵活。

这就好比在交通拥堵的城市里，别人还在按红绿灯一个个走，而作者发现了一条可以穿行的地下通道，让大家能更快、更省力地到达目的地。

这篇论文提出了一种名为对角矩阵迁移（Diagonal Matrix Migration, DMM）的新颖技术，旨在优化量子计算中量子态制备（State Preparation）和块编码（Block Encoding）的电路复杂度，特别是显著降低了C-NOT 门的数量。C-NOT 门是目前量子硬件中最昂贵且易出错的双量子比特门，因此减少其数量对于提升量子算法的实用性和可扩展性至关重要。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

核心挑战：在科学计算的量子算法中，量子态制备和块编码是关键的输入模型。然而，这些操作的电路复杂度（特别是 C-NOT 门数量）往往主导了整个算法的端到端门复杂度。
现有局限：
- 态制备：现有的主流算法（如 Plesch-Brukner, 2011）虽然接近理论下界，但其 C-NOT 门数量的主导项系数为 $23/24 \approx 0.958$ ，尚未达到理论极限 $1/2 = 0.5$ 。
- 块编码：现有的块编码协议（如 FABLE, BITBLE）通常使用非最优的缩放因子（scaling factor），或者虽然使用谱范数（spectral norm）作为缩放因子，但其 C-NOT 门数量依然较高。
- 理论差距：对于 $n$ 量子比特的幺正合成（Unitary Synthesis），理论下界约为 $1/4 \cdot 4^n$ ，而通用块编码的下界更低（ $1/8 \cdot 4^n$ ），但现有算法未能充分利用这一差距。

2. 方法论 (Methodology)

论文的核心创新在于引入了对角矩阵迁移（Diagonal Matrix Migration）技术，并结合了递归块-ZXZ 分解（Recursive Block-ZXZ Decomposition）。

基本思想：
- 利用对角矩阵与绕 Z 轴的均匀受控旋转（Uniformly Controlled Rotation, UCRZ）以及 C-NOT 门之间的对易性（Commutativity）。
- 在合成幺正矩阵（Unitary）或等距矩阵（Isometry）时，通常会产生一些对角矩阵因子。传统方法会单独实现这些对角矩阵，而新方法将这些对角矩阵“迁移”（commute）通过前面的 C-NOT 门或 UCRZ 层，并将其合并到后续的递归步骤或矩阵乘法中。
- 通过这种方式，原本需要单独实现的 C-NOT 门被消除或合并，从而减少了总门数。
具体流程：
1. 态制备 (SPDMM)：
  - 将 $n$ 量子比特态向量重塑为矩阵并进行奇异值分解（SVD）。
  - 递归地合成左右奇异向量矩阵（ $U$ 和 $V^\dagger$ ），但在合成过程中允许保留一个对角矩阵因子（即合成 $U \cdot \Delta$ 而非 $U$ ）。
  - 利用对角矩阵迁移技术，将递归步骤中产生的对角矩阵合并到下一层递归的输入向量中，从而减少每一层的 C-NOT 消耗。
2. 块编码 (SIABLE)：
  - 针对满秩矩阵，利用单辅助比特（Single Ancilla）架构。
  - 将矩阵分解为两个幺正矩阵和一个对角矩阵（或均匀受控旋转）的组合。
  - 同样应用对角矩阵迁移，将 $V^\dagger$ 合成中的对角矩阵迁移并合并到 $W_A$ 的合成中，优化整体电路结构。
3. 低秩矩阵优化：
  - 针对实际应用中常见的低秩矩阵，利用其自由度较少的特点，仅合成等距矩阵的前 $K$ 列/行，进一步降低复杂度。

3. 主要贡献与理论结果 (Key Contributions & Results)

A. 量子态制备优化 (State Preparation)

定理 1：对于任意 $n$ 量子比特态，提出的SPDMM算法所需的 C-NOT 门数量上限为：
$N_{state}(n) \le \frac{11}{12} 2^n$
对比：将主导项系数从 Plesch-Brukner 算法的 $23/24$ 降低到了 $11/12$ （约 0.917）。
理论下界：证明了态制备的理论下界为 $\lceil \frac{1}{2} 2^n - \dots \rceil$ ，即系数为 $1/2$ 。虽然 $11/12$ 仍未达到 $1/2$ ，但这是目前已知最好的上界。

B. 单辅助比特块编码协议 (Single Ancilla Block Encoding)

定理 2：对于 $2^{n-1} \times 2^{n-1}$ 的满秩矩阵，提出的SIABLE协议使用谱范数 $\|A\|_2$ 作为最优缩放因子，其 C-NOT 门数量上限为：
$N_{mat}(n-1) \le \frac{11}{48} \times 4^n - 2^n + \frac{7}{3}$
突破性结果：该结果的主导项系数为 $11/48$ （约 0.229）。
- 值得注意的是，这个数值甚至低于 $n$ 量子比特幺正合成（Unitary Synthesis）的理论下界（ $1/4 \cdot 4^n = 0.25 \cdot 4^n$ ）。这是因为块编码的约束比幺正合成更弱，允许更高效的实现。
- 同时，该协议也推导出了块编码的理论下界为 $1/8 \cdot 4^n$ 。

C. 低秩矩阵优化

定理 5：对于秩为 $K$ 的矩阵，C-NOT 门的主导项为：
$(K + \frac{11}{12}) 2^n$
这比全秩矩阵的 $O(2^n)$ 或 $O(4^n)$ 复杂度在 $K$ 较小时有显著优势。

4. 实验验证 (Experimental Results)

论文通过 MATLAB 库 QCLAB 进行了数值实验。
态制备：在 $n=2$ 到 $n=15$ 的范围内，SPDMM 的 C-NOT 数量均优于 Plesch-Brukner (PB)、Isometry Synthesis 和 LRSP 等现有方法。例如，当 $n=15$ 时，SPDMM 需要 29,627 个 C-NOT，而 PB 需要 38,813 个。
块编码：SIABLE 协议在 $n=3$ 到 $n=7$ 的范围内，C-NOT 数量显著低于 FABLE、BITBLE 和 Block-ZXZ 等方法，并且首次在实际算法中实现了低于幺正合成下界的门数量。

5. 意义与影响 (Significance)

降低硬件门槛：C-NOT 门是量子硬件的主要瓶颈。减少其数量直接意味着更深的电路容错能力要求和更短的退相干时间窗口，使得在当前的含噪声中等规模量子（NISQ）设备或早期容错量子计算机上运行复杂算法成为可能。
理论突破：首次提出了在块编码中 C-NOT 门数量低于幺正合成理论下界的算法，揭示了块编码作为一种输入模型在资源消耗上的巨大潜力。
通用性：提出的“对角矩阵迁移”技术是一种通用的优化策略，不仅适用于态制备和块编码，未来可能应用于其他量子电路合成任务中，通过利用对角矩阵的对易性来压缩电路。
实际应用：针对低秩矩阵的优化特别适用于机器学习（如推荐系统、大语言模型）和科学计算中的常见场景，具有极高的实用价值。

总结：该论文通过巧妙的数学变换（对角矩阵迁移）和递归分解策略，在量子态制备和块编码领域取得了目前为止最优的 C-NOT 门复杂度上界，为未来高效量子算法的实现奠定了重要的电路基础。