作者: Kamil Khadiev, Aliya Khadieva, Vadim Sagitov, Kamil Khasanov, Mansur Ziatdinov

1. 核心物理图象

这篇文章的核心物理图象是为量子计算机上的量子哈希（指纹）算法，设计一条高效运行的物理“路线图”。由于真实的量子芯片（如超导量子计算机）上的量子比特并不能任意两两相连，只能操作物理上相邻的量子比特，因此，一个量子算法在理论上可以运行，但在物理芯片上实现时却需要大量的额外操作（CNOT门）。文章的贡献在于提出了一种通用算法，通过在图论中寻找一条“1-覆盖路径”（一种访问所有量子比特或它们邻居的路线），将这个抽象的量子算法映射到任意具体物理芯片的拓扑结构上，从而最小化实现算法的物理开销（即CNOT门数量）。这就像导航软件为你在道路网络中规划一条最短的行驶路线，以最优地访问所有目的地。

2. 关键术语解释

• 量子哈希（指纹）算法（Quantum Hashing / Fingerprinting）：这是一种量子算法技术，能够用一个极短的量子态“指纹”来高度概率地识别一份长数据串。它类似于经典哈希，但利用了量子叠加态的特性，在量子自动机、通信协议和机器学习等领域有广泛应用。本篇论文旨在优化此算法在真实硬件上的实现。
• 量子比特连接图（Qubit Connectivity Graph）：这是对量子芯片硬件结构的一种抽象。图中的每个顶点代表一个物理量子比特，每条边代表两个量子比特之间能够直接执行双量子比特门（如CNOT门）的物理连接。不同芯片（如IBMQ、Rigetti）有不同的连接图。算法的通用性体现在它能适应任意的连接图。
• CNOT门成本（CNOT Cost）：这是衡量量子电路复杂度的一个关键指标。CNOT门是双量子比特门中最基础也最常用的操作之一。由于它们比单量子比特门更容易出错且耗时更长，因此减少电路中的CNOT门数量是优化量子电路的首要目标。本文的核心优化目标就是最小化这个“成本”。
• 1-覆盖路径（1-Covering Path）：这是来自图论的一个概念，指一条路径，它访问的顶点集合加上这些顶点的所有邻居，能够覆盖图中的全部顶点。本算法通过寻找最短的“1-覆盖路径”来规划量子比特操作的顺序，从而实现最少化CNOT门数量。

3. 主要贡献

1. 提出了一种针对任意量子比特连接图的通用电路生成算法：该算法能为量子哈希算法生成一个“浅层”（Shallow）电路，该电路能适配任意架构的量子芯片，而非局限于特定的线性或星型连接。
2. 引入了“1-覆盖路径”问题的精确和近似求解算法：这是该研究的数学基础和关键理论工具。精确算法（基于动态规划）虽时间复杂度高，但能保证最优解；近似算法则针对大规模图提供了几乎线性时间的高效方案。
3. 显著降低了CNOT门成本：与已有的通用方法相比，该算法在理论上将CNOT成本的上限从 (6n\ell - 4\ell + 2) 降低到 (6n\ell - 7\ell + 2)（其中 (n) 是量子比特数，(\ell) 是算法应用次数）。在一个具体的网格图例中，它实现了**16%-17%**的CNOT成本降低。
4. 展示了算法的普适性和兼容性：该通用算法在特定的硬件架构（如线性最近邻LNN，IBMQ的16/27量子比特架构）上生成的电路，与之前专门为这些架构手工优化出的最佳电路成本相同，证明了其“一石多鸟”的强大效力。

4. 研究方法

论文采用了“从算法到图论，再到硬件映射”的系统性研究方法：

• 算法层面：目标是将量子哈希算法的核心操作——(UCR)门（均匀受控旋转门）——进行分解和简化。他们采用了一种“浅层电路”近似，用一系列更简单的(CR_y)（受控(R_y)旋转）和(SWAP)（交换）门来替代，而这些门都可以进一步分解为基本的CNOT门。
• 图论层面：如何用最少的CNOT门串联这些操作？作者的巧思是将量子比特的物理运动（通过(SWAP)门）抽象为图论中的路径问题。他们定义了“最短非简单1-覆盖路径”问题，并给出了两种解法：
  • 精确算法：通过动态规划和广度优先搜索（BFS）在所有可能的顶点子集和路径中寻找最短长度，时间复杂度为 (O((m+n)2^n))，属于指数级但保证最优。
  • 近似算法：将问题分解为“连通支配集”问题和“最短遍历路径”问题，分别用已知的近似算法（如( ( \ln \Delta + 3) )-近似算法 和 Christofides–Serdyukov算法）快速求解，总时间复杂度仅为 (O((n + m) \log n))，非常适合当前物理硬件规模。
• 硬件映射：算法的核心输出是一条“1-覆盖路径”。这个路径直接对应了电路设计中靶量子比特（(q_0)）的移动轨迹。通过沿此路径移动靶比特，并对路径上及路径“覆盖”到的邻居量子比特施加(CR_y)门，即可构造出完整的电路。

5. 实验结果与结论

论文的核心结论是通过图论优化，可以显著提升量子哈希算法在受限硬件上的实现效率。这种提升不仅体现在理论上，而且在具体的网格图示例中得到了验证（CNOT成本从123降至101，降幅约18%）。更重要的是，该算法具有很强的普适性：它不仅能处理任意连接图，而且对已知的特定架构（如LNN）也能生成与专门优化方案相同的最优电路，表明这是一个统一的、可扩展的解决方案。

作者在最后也提出了几个开放性问题，为后续研究指明了方向：

• 对于特定类型的图（例如IBMQ或Rigetti的真实连接图），是否能在多项式时间内找到精确的最优解？
• 是否有更高效的贪心算法可以用于求解1-SNSCP问题？

6. 论文标签

量子算法, 编译与优化, 量子信息, 模拟, 量子复杂性

📄 点击此处展开/折叠原文 PDF

原文链接： Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering Path