线路编译理论(Transpilation Theory)

量子线路编译(Transpilation)是将抽象的、与硬件无关的量子程序转换为可以在特定量子设备上忠实执行的形式的过程。这涉及四个深度关联的问题：优化线路以减少门数量和深度、将逻辑量子比特映射到满足连接性约束的物理量子比特上、从有限的本机门集(Native Gate Set)中合成任意酉操作、以及在连接性需求不被满足时通过插入SWAP门来路由量子比特。

pyqpanda3通过Transpiler类、用于门合成的decompose函数以及用于构建芯片耦合图的generate_topology提供了完整的编译流水线。本指南解释了每个阶段背后的理论基础。

编译流水线(Transpilation Pipeline)

在深入各个主题之前，了解编译各阶段之间的关系是很有帮助的。pyqpanda3按顺序应用一系列遍(Pass)，每个遍负责转换的一个方面。

每个遍对线路的有向无环图(DAG, Directed Acyclic Graph)表示进行读写。DAG捕获了门之间的依赖关系：一个门只有在其同一量子比特线路上所有前驱门完成后才能执行。默认的遍顺序定义在DefaultTranspilationPasses中，依次为：初始化(Init)、布局(Layout)、路由(Routing)、翻译(Translation)、优化(Optimization，包括前优化和后优化)和调度(Scheduling)。optimization_level参数控制优化和路由遍的激进程度。

---

线路优化(Circuit Optimization)

为什么优化很重要

量子门是不完美的。每施加一个门都会引入误差，而CNOT或CZ等双比特门的噪声通常比单比特门高一到两个数量级。线路深度同样至关重要，因为量子比特会随时间发生退相干。减少门数量和线路深度可以直接提高计算结果的保真度(Fidelity)。

线路优化的目标是产生一个功能等效的线路，使其更短、更浅，并使用更少的昂贵门，同时保持原始线路所实现的酉变换不变。

pyqpanda3中的优化级别

Transpiler接受一个optimization_level参数来控制优化的激进程度：

级别	行为
0	无优化。线路仅被翻译和路由，不进行优化。
1	基本优化。应用门合并和简单消除。
2	激进优化。包括交换性感知优化(Commutativity-Aware Optimization)、窥孔分析(Peephole Analysis)和基于衰减的SABRE路由启发式算法。

在级别2中，编译器还在路由过程中使用基于衰减的代价函数（参见Sabre算法部分），并在翻译阶段应用更彻底的门合并。

门消除(Gate Cancellation)

最简单的优化是门消除：当两个相邻的门互为逆操作时，两者都可以被移除。例如，施加一个$H$门后紧接着再施加一个$H$门，结果为单位操作：

$$H\cdot H=I$$

类似地，$X\cdot X=I$、$CNOT\cdot CNOT=I$（在同一对比特上）以及$R_z(\theta )\cdot R_z(-\theta )=I$。

pyqpanda3通过OptimizationPass的remove_h和remove_cx方法实现此优化，这些方法扫描DAG以寻找可消除的门对。消除过程是迭代进行的，因为移除一对门可能会暴露出新的可消除门对。

门合并(Gate Merging)

在同一量子比特上绕同一轴的连续旋转门可以合并为一个旋转。例如：

$$R_x(\alpha )\cdot R_x(\beta )=R_x(\alpha +\beta )$$

这适用于任何旋转轴。pyqpanda3通过merge_rx、merge_ry、merge_rz和通用的merge_q1_gate方法实现此优化。合并过程：

1. 依次扫描DAG中的每条量子比特线路。
2. 当两个连续的单比特门作用于同一轴时，合并它们的参数。
3. 如果合并后的角度为零（或低于数值容差），则完全移除该门。

合并在路由之后特别有效，因为SWAP分解会引入CNOT门序列，这些门可能级联产生相邻线路上的冗余单比特操作。

交换性感知优化(Commutativity-Aware Optimization)

并非线路中所有看起来相邻的门对实际上都需要相邻。两个门$G_1$和$G_2$可交换，如果$G_1\cdot G_2=G_2\cdot G_1$。当门可以交换时，优化器可以重新排列它们以创造新的消除或合并机会。

pyqpanda3通过OptimizationPass中的commutation_cancel和check_commutation方法实现交换性分析。该分析基于DAG表示进行：

1. 对于共享同一量子比特线路的每对门，检查它们是否可交换。
2. 如果可以交换，允许重构DAG使得可消除或可合并的门变为相邻。
3. 在重构后的DAG上应用消除和合并。

这对于混合单比特门和双比特门的线路特别有效，因为许多单比特旋转与CNOT门的控制端是可交换的。例如，控制量子比特上的$R_z$与CNOT可交换：

$$R_z(\theta )\otimes I\cdot \text{CNOT}=\text{CNOT}\cdot R_z(\theta )\otimes I$$

窥孔优化(Peephole Optimization)

窥孔优化检查小的窗口（通常为2-3个门的子线路），并用等效但更短的序列替换它们。这类似于经典编译器中使用的窥孔优化技术。

在pyqpanda3中，窥孔优化集成在BasicTranslationPass中。在merage_and_translation步骤中，小子线路与已知等价库（EquivalenceLibrary）进行匹配。当找到匹配时，子线路被替换为更高效的等效形式。

例如，序列$H\cdot R_z(\theta )\cdot H$可以替换为$R_x(\theta )$：

$$H\cdot R_z(\theta )\cdot H=R_x(\theta )$$

模板匹配(Template Matching)

模板匹配通过维护线路恒等式库（模板）来推广窥孔优化。每个模板是一对等效线路：一个用于搜索的模式和一个用于替换的模式。模板库包括如下恒等式：

• 门分解模板：$S=R_z(\pi /2)$、$T=R_z(\pi /4)$
• 门等价模板：$\text{CNOT}=(I\otimes H)\cdot \text{CZ}\cdot (I\otimes H)$
• 旋转简化模板：$R_z({\theta }_1)\cdot R_z({\theta }_2)=R_z({\theta }_1+{\theta }_2)$

BasicTranslationPass使用的EquivalenceLibrary存储这些模板，并在翻译阶段执行高效匹配。

酉合成优化(Unitary Synthesis Optimization)

OptimizationPass中的unitary_synthesis方法采用了不同的方法：它提取小子线路（通常1-2个量子比特），计算它们的组合酉矩阵，然后使用最少数量的本机门重新合成该酉操作。这比窥孔优化更强大，因为它不局限于已知模板；它可以为任意子线路找到最优分解。

该过程：

1. 在DAG中识别1或2个量子比特上的子线路。
2. 计算组合酉矩阵$U=G_n\cdots G_2\cdot G_1$。
3. 使用KAK或Euler分解酉矩阵$U$（参见门合成）。
4. 用优化后的分解替换原始子线路。

这种方法可以将多门子线路简化为仅几个本机门，即使没有明显的个别消除或合并。

优化遍流程

在pyqpanda3中，优化在编译流水线的多个阶段被应用。DefaultTranspilationPasses类定义了遍顺序，包括前优化遍和后优化遍：

1. 前优化(Pre-optimization)（OptimizationPass的"pre"模式）：在路由之前应用，简化线路并减少路由算法需要处理的门数量。这包括门消除、合并以及通过decompose_oracle进行的预言机分解。

2. 后优化(Post-optimization)：在路由和翻译之后应用，清理SWAP分解引入的冗余门。这是交换性感知优化最有效的阶段，因为SWAP插入经常创建如下模式：

$$\text{CNOT}(q_a,q_b)\cdot R_z(\theta )(q_b)\cdot \text{CNOT}(q_a,q_b)$$

如果$R_z$可以穿过CNOT交换，则该模式可以被简化。

3. 翻译阶段优化：BasicTranslationPass在将线路门翻译为本机门时应用门合并。merage_and_translation方法合并连续的单比特门，并为每个双比特门选择最高效的分解。

这些优化阶段之间的交互产生了复合效应：前优化减小线路规模，从而加速路由；路由在更小的线路上产生更少的SWAP；后优化清理任何剩余的冗余。

优化决策的代价模型(Cost Model)

优化决策由一个权重不同门类型的代价模型指导。在实际硬件上，双比特门比单比特门昂贵得多：

$$\text{cost}(\text{CNOT})\approx 10\times \text{cost}(R_z)$$$$\text{cost}(\text{CZ})\approx 10\times \text{cost}(R_z)$$

这种代价不对称性驱使优化器优先选择减少双比特门数量的变换，即使以增加单比特门为代价。例如，优化器可能用两个单比特门替换一个CNOT，如果整体线路变得更加可靠。

当向编译器提供ChipBackend时，代价模型可以纳入设备特定的校准数据。ChipBackend中的compensate_angle_map存储双比特门的逐边角度校正，compensate_pulse标志在翻译阶段启用脉冲级补偿。

---

拓扑映射(Topology Mapping)

量子比特映射问题

真实的量子处理器并不具有全连接(All-to-All Connectivity)。超导量子芯片通常将量子比特排列在二维网格或类似拓扑中，每个量子比特仅与少数邻居直接相连。双比特门只能施加在连接图中物理相邻的一对量子比特上。

量子比特映射问题(Qubit Mapping Problem)是将线路中的逻辑（虚拟）量子比特分配到芯片上的物理量子比特的任务，使得线路中的每个双比特门都可以在物理相邻的量子比特上执行。当当前分配无法满足这一要求时，必须插入SWAP门将量子比特状态移动到相邻位置。

耦合图(Coupling Maps)

耦合图(Coupling Map)（或拓扑图(Topology Graph)）描述了量子芯片的物理连接性。它表示为图$G=(V,E)$，其中$V$是物理量子比特集合，$E$是边集合，每条边表示可以在相连的量子比特之间直接施加双比特门。

pyqpanda3将耦合图表示为边的列表，每条边是一个对[u, v]：

# A linear topology for 4 qubits: 0 -- 1 -- 2 -- 3
topology = [[0, 1], [1, 2], [2, 3]]

generate_topology函数创建常见的拓扑模式：

拓扑类型	描述	示例（4个量子比特）
"linear"	最近邻链	[[0,1], [1,2], [2,3]]
"circular"	环形（添加回绕边）	[[0,1], [1,2], [2,3], [3,0]]
"square"	二维网格	网格连接

为什么拓扑很重要

考虑一个在线性拓扑0 -- 1 -- 2 -- 3上对量子比特0和3施加CNOT的简单线路。量子比特0和3不直接相连，因此CNOT无法按原样执行。编译器必须插入SWAP门将逻辑状态移动到相邻的物理量子比特上。

一个SWAP门本身分解为三个CNOT门：

$$\text{SWAP}(q_i,q_j)=\text{CNOT}(q_i,q_j)\cdot \text{CNOT}(q_j,q_i)\cdot \text{CNOT}(q_i,q_j)$$

每个插入的SWAP向线路添加三个CNOT门，增加了深度和错误率。因此，找到良好的初始映射并最小化SWAP插入数量对于产生高效的硬件兼容线路至关重要。

距离矩阵(Distance Matrix)

给定耦合图$G$，编译器计算一个距离矩阵$D$，其中$D[i][j]$是物理量子比特$i$和$j$在拓扑图中的最短路径距离。该矩阵在构建TranspilationParameter时使用Dijkstra算法计算：

$$D[i][j]=\underset{\text{paths}}{min}|p(i\to j)|$$

距离矩阵被路由算法广泛使用，用于评估当前量子比特映射距离满足每个门的连接性要求有多远。作用于逻辑量子比特$q_a$和$q_b$的门$g$可执行，当且仅当$D[\pi (q_a)][\pi (q_b)]=1$，其中$\pi$是从逻辑量子比特到物理量子比特的当前映射。

距离矩阵还在初始布局中发挥作用。编译器使用DAG::get_largest_path()找到拓扑图中最长的最短路径。然后沿着该路径映射线路量子比特，以最大化在任何SWAP插入之前可用的直接相邻对比特数量。

邻接性和连接性属性

耦合图有几个影响编译的重要属性：

连通性(Connectedness)：拓扑图必须是连通的。如果图有不连通的分量，编译器通过largest_connected_component()检测到这一点，如果线路需要跨越分量的量子比特交互，则抛出错误。

最长路径(Largest path)：线路中的量子比特数量不能超过拓扑图中最长最短路径的长度。pyqpanda3验证此约束：

$$|Q_{\text{circuit}}|\le |p_{\text{longest}}(G)|$$

如果违反此约束，编译器将抛出错误，因为没有任何映射能在不超过可用物理量子比特的情况下满足所有连接性要求。

边的方向(Edge direction)：耦合图被视为无向图。边[u, v]表示可以以任一方向（控制或目标）在量子比特$u$和$v$之间施加双比特门。

初始映射策略(Initial Mapping Strategies)

初始映射的质量对路由期间需要的SWAP门数量有很大影响。pyqpanda3支持多种策略：

1. 平凡映射(Trivial mapping)：逻辑量子比特$i$映射到物理量子比特$i$。简单但通常不是最优的。

2. 最长路径映射(Largest-path mapping)：线路量子比特映射到拓扑图中的最长路径。这最大化了可用的直接相连量子比特对数量。

3. SabrePreLayout：一种预布局优化，使用图匹配找到最小化所需额外边数量的初始映射。它的工作方式：

   • 提取线路的交互图（哪些量子比特对共享双比特门）。
   • 在线路的交互图和拓扑图之间寻找子图同构。
   • 使用minimize_extra_edges方法优化映射。

4. 用户指定映射(User-specified mapping)：调用者可以通过transpile()方法的init_mapping参数提供{virtual_qubit: physical_qubit}形式的字典。

当未提供初始映射时，pyqpanda3运行SABRE的前向-后向-前向遍历（见下文）来自动发现良好的映射。

路由算法概述

路由是插入SWAP门以满足连接性约束的过程。存在多种方法：

算法	策略	复杂度	质量
基本SWAP	贪心：逐个插入SWAP以满足每个门	$O(|G{|}^2)$	低
随机SWAP	随机SWAP插入配合模拟退火	$O(|G{|}^2\cdot k)$	中
SABRE	启发式双向搜索配合前瞻	$O(|G{|}^2)$	高

pyqpanda3使用SABRE算法作为其默认路由方法。SABRE在下面Sabre算法部分中详细描述。

---

门合成(Gate Synthesis)

本机门集问题(The Native Gate Set Problem)

每个量子处理器支持有限的本机门集(Native Gate Set)。对于超导量子比特，通常是类似$\{R_z,X_{\pi /2},\text{CZ}\}$或$\{U_3,\text{CNOT}\}$的集合。然而，量子算法使用更丰富的门集设计，可能包括任意旋转、受控操作和多量子比特酉操作。

门合成(Gate Synthesis)是将任意酉操作分解为目标本机门集中门序列的过程。pyqpanda3中的decompose函数执行此分解。

单比特门的Euler分解(Euler Decomposition)

任何单比特酉操作$U\in SU(2)$都可以分解为三个旋转。最常见的分解是：

ZYZ分解

$$U=e^{i\gamma }{R}_z(\varphi )\cdot R_y(\theta )\cdot R_z(\lambda )$$

其中$\gamma$是全局相位，$\theta$、$\varphi$、$\lambda$是由矩阵元素确定的旋转角度：

$$\theta =2\arctan \left(\frac{|U_{10}|}{|U_{00}|}\right)$$$$\varphi =\arg (U_{11})+\arg (U_{10})-\arg (detU)$$$$\lambda =\arg (U_{11})-\arg (U_{10})$$$$\gamma =\frac{1}{2}\arg (detU)$$

pyqpanda3在KAK合成模块的params_zyz_inner中实现了此分解。

ZXZ分解

类似地，任何单比特酉操作可以写成：

$$U=e^{i\gamma }{R}_z(\alpha )\cdot R_x(\beta )\cdot R_z(\gamma )$$

ZXZ分解在目标门集偏好$R_x$旋转而非$R_y$旋转时很有用。

分解的选择影响所需的本机门数量。对于门集$\{R_z,X_{\pi /2}\}$，其中$R_x(\theta )=R_z(-\pi /2)\cdot R_y(\theta )\cdot R_z(\pi /2)$，ZYZ分解更高效，因为它直接使用$R_y$旋转，可以以最小的开销转换为$R_z$和$X_{\pi /2}$序列。

双比特门的KAK分解

任何双比特酉操作$U\in SU(4)$都可以使用KAK分解（也称为Cartan分解或Weyl分解）进行分解：

$$U=(K_1^L\otimes K_1^R)\cdot U_d(a,b,c)\cdot (K_2^L\otimes K_2^R)$$

其中：

• $K_1^L,K_1^R,K_2^L,K_2^R\in SU(2)$是单比特酉操作。
• $U_d(a,b,c)$是由三个实数$a\ge b\ge |c|\ge 0$参数化的非局域部分。

非局域交互矩阵为：

$$U_d(a,b,c)=\exp [i(c\cdot I\otimes Z+b\cdot Z\otimes I+a\cdot Z\otimes Z)]$$

更明确地：

$$U_d(a,b,c)=\left(\begin{array}{cccc}{e}^{ic}\cos (a-b)& 0& 0& i{e}^{ic}\sin (a-b)\\ 0& e^{-ic}\cos (a+b)& i{e}^{-ic}\sin (a+b)& 0\\ 0& i{e}^{-ic}\sin (a+b)& e^{-ic}\cos (a+b)& 0\\ i{e}^{ic}\sin (a-b)& 0& 0& e^{ic}\cos (a-b)\end{array}\right)$$

三元组$(a,b,c)$位于Weyl腔(Weyl Chamber)中，这是一个四面体区域，对所有双比特纠缠操作的等价类进行分类。

Weyl腔分类(Weyl Chamber Classification)

$(a,b,c)$的值决定了操作的纠缠能力：

区域	$(a,b,c)$	门类型
类恒等	$(0,0,0)$	可分离操作（无纠缠）
类CNOT	$(\pi /4,0,0)$	局部等价于CNOT
类SWAP	$(\pi /2,0,0)$	局部等价于SWAP
双CNOT	$(\pi /4,\pi /4,0)$	局部等价于两个CNOT
一般情况	$(a,b,c)$	最多需要3个CNOT + CZ门

pyqpanda3实现了TwoQubitWeylDecomposition类和TwoQubitBasisDecomposer单例。分解器使用Weyl分解来确定所需的最少基础门数量：

• 0个基础门：目标是可分离操作（无纠缠）。
• 1个基础门：目标局部等价于基础门。
• 2个基础门：对于超受控基础门（如CNOT或CZ），目标可以通过两次施加基础门达到。
• 3个基础门：最一般的情况，需要三次施加。

特化(Specialization)

pyqpanda3通过针对特定门类型的特化分解进一步优化。TwoQubitWeylDecomposition类包含专门的特化方法：

• IdEquivSpecialize：用于近似恒等操作（0个基础门）。
• SWAPEquivSpecialize：用于近似SWAP的操作。
• ControlledEquivSpecialize：用于近似受控门的操作。
• fSimaabEquivSpecialize、fSimabbEquivSpecialize、fSimabmbEquivSpecialize：用于fSim类型操作。
• GeneralSpecialize：用于一般情况。

量子Shannon分解(Quantum Shannon Decomposition, QSD)

对于多于两个量子比特的酉操作，pyqpanda3使用量子Shannon分解(QSD)。QSD递归地将$n$量子比特酉操作分解为更小的酉操作、受控门和多路旋转。

QSD背后的关键恒等式是余弦-正弦分解(CSD, Cosine-Sine Decomposition)。给定一个$2^n\times 2^n$的酉操作$U$，它可以被分块为：

$$U=\left(\begin{array}{cc}{U}_1& 0\\ 0& U_2\end{array}\right)\left(\begin{array}{cc}\cos \mathrm{\Theta }& -\sin \mathrm{\Theta }\\ \sin \mathrm{\Theta }& \cos \mathrm{\Theta }\end{array}\right)\left(\begin{array}{cc}{V}_1& 0\\ 0& V_2\end{array}\right)$$

其中$U_1,U_2,V_1,V_2$是$2^{n-1}\times 2^{n-1}$的酉操作，$\mathrm{\Theta }$是对角角度矩阵。CSD在_cosine_sine_decomposition中实现。

QSD的递归结构：

1. 应用CSD将$n$量子比特酉操作分解为两个$(n-1)$量子比特酉操作、一个多路旋转和另外两个$(n-1)$量子比特酉操作。
2. 递归分解每个$(n-1)$量子比特酉操作。
3. 使用_demultiplex（或_qs_demultiplex / _cs_demultiplex）分解多路旋转。
4. 基础情况是2量子比特酉操作，由KAK分解处理。

pyqpanda3通过DecompositionMode枚举支持多种分解模式：

模式	描述
QSD	量子Shannon分解（默认，最通用）
CSD	余弦-正弦分解
QR	基于QR的分解
HOUSEHOLDER_QR	基于Householder QR的分解

矩阵的decompose函数内部使用QSD：

from pyqpanda3.transpilation import decompose
import numpy as np

# Decompose a 2-qubit unitary into native gates
U = np.array([[1, 0, 0, 0],
              [0, 1, 0, 0],
              [0, 0, 0, 1],
              [0, 0, 1, 0]], dtype=complex)

circuit = decompose(U, qubits=[0, 1], basic_gates=["rx", "ry", "rz", "cx"])

等距分解(Isometry Decomposition)

当输入不是方阵酉操作而是等距映射（具有正交列的矩阵）时，pyqpanda3提供了IsometryDecomposition类。这对于态制备(State Preparation)很有用，其中目标是从$|0{⟩}^{\otimes n}$制备特定的量子态。

支持两种方案：

• CCD（逐列分解，Column-by-Column Decomposition）：使用多控门逐列分解等距映射。
• Knill：使用Knill定理将等距映射扩展为完整的酉操作，然后应用QSD。

Solovay-Kitaev近似(Solovay-Kitaev Approximation)

对于在精确意义上不是通用的门集（例如Clifford+T集合），Solovay-Kitaev定理保证任何单比特酉操作可以使用$O({\log }^c(1/ϵ))$个集合中的门来近似到精度$ϵ$，其中$c\approx 3.97$。虽然pyqpanda3专注于连续门集（如$\{R_z,R_x,\text{CZ}\}$）的精确合成，但在面向离散门集时，Solovay-Kitaev方法变得相关。

basic_gates参数

Transpiler和decompose函数都接受一个basic_gates参数来指定目标门集。例如：

# Decompose into the RX, RY, RZ, CX gate set
result = decompose(prog, basic_gates=["rx", "ry", "rz", "cx"])

# Transpile targeting CZ, X1, RZ (typical superconducting gate set)
result = transpiler.transpile(prog, chip_topology_edges=topo,
                              basic_gates=["cz", "x1", "rz"])

当basic_gates为空时，pyqpanda3使用默认门集$\{\text{CZ},X_{\pi /2},R_z\}$，对应于典型超导量子处理器的本机门集。

门数量和线路深度

门合成的质量直接影响最终的线路度量指标。QCircuit的decompose函数在翻译之前应用优化遍（OptimizationPass的"pre"模式）以最小化输出门数量。线路的合成流水线遵循以下步骤：

1. 将线路转换为DAG表示。
2. 应用InitPass规范化线路结构。
3. 应用OptimizationPass消除和合并门。
4. 提取门列表并收集门类型统计。
5. 应用BasicTranslationPass，使用等价库将每个门翻译为目标门集，并合并连续的单比特门。

生成线路的门数量取决于输入酉操作和目标门集。某些门集比其他门集允许更高效的表示。例如，门集$\{U_3,\text{CX}\}$可以用单个$U_3$门表示任何单比特操作，而$\{R_z,R_x,\text{CX}\}$可能需要最多三个旋转门来表示一个单比特操作。

矩阵分解验证

矩阵的decompose函数在合成之前执行多项验证检查：

1. 方阵：输入必须是方阵（$m=n$）。
2. 2的幂：维度必须是2的正整数次幂，即$n=2^k$，其中$k\ge 1$为整数。
3. 量子比特数量：如果提供了qubits，其长度必须与$k={\log }_2(n)$匹配。如果未提供，量子比特自动分配为$[0,1,\dots ,k-1]$。
4. 门名称有效性：basic_gates中的每个名称必须对应一个受支持的门类型。未知的门名称会引发运行时错误。

---

Sabre算法(Sabre Algorithm)

概述

SABRE（基于SWAP的双向启发式搜索，SWAP-based BidiREctional heuristic search）算法由Li等人于2019年提出，是pyqpanda3中使用的主要路由算法。它是一种可扩展的启发式方法，用于解决量子比特路由问题，结合了前向-后向线路遍历和前瞻代价函数来寻找良好的SWAP插入模式。

SABRE是默认的路由方法，因为它以多项式时间复杂度产生高质量结果，并能很好地扩展到具有数百个量子比特和数千个门的线路。

问题形式化

给定：

• 量子线路$C=\{g_1,g_2,\dots ,g_N\}$，其中每个门$g_i$作用于量子比特集合$Q$中的量子比特。
• 耦合图$G=(V,E)$，其中$|V|\ge |Q|$。
• 从逻辑量子比特到物理量子比特的映射$\pi :Q\to V$。

找到一个SWAP操作序列，使得对于作用于量子比特$q_a,q_b$的每个双比特门$g_i$：

$$(\pi (q_a),\pi (q_b))\in E$$

在$g_i$执行时成立，同时最小化插入的SWAP门总数。

前沿层(The Front Layer)

SABRE基于前沿层(Front Layer)$F$的概念运作，$F$是可以立即执行的门集合（它们在DAG中的所有前驱已执行）。算法迭代：

1. 从$F$中移除所有量子比特对在耦合图中相邻的门（它们现在可以执行）。
2. 将在移除的门之后变为可执行的新门添加到$F$。
3. 如果$F$非空，选择并施加一个使启发式代价函数最小化的SWAP门。
4. 重复直到$F$为空。

启发式代价函数(Heuristic Cost Function)

SABRE的核心是用于评估候选SWAP门的启发式代价函数。pyqpanda3实现了三种变体：

基本代价函数

基本代价衡量前沿层门量子比特之间总距离的变化：

$$H_{\text{basic}}(\text{SWAP}(q_1,q_2))=\delta \cdot \sum _{g\in F}[D({\pi }^{\prime }(f(g)),{\pi }^{\prime }(w(g)))-D(\pi (f(g)),\pi (w(g)))]$$

其中${\pi }^{\prime }$是施加SWAP后的映射，$f(g)$和$w(g)$是门$g$的第一个和第二个量子比特，$D$是距离矩阵。系数$\delta$是两个SWAP量子比特的最大衰减因子：

$$\delta =max(\text{decay}[q_1],\text{decay}[q_2])$$

前瞻代价函数

前瞻代价通过扩展集(Extended Set)$E$中的信息增强基本代价，$E$包含尚未在前沿层但即将到达的门：

$$H(\text{SWAP})=\frac{1}{|F|}\sum _{g\in F}D({\pi }^{\prime }(f(g)),{\pi }^{\prime }(w(g)))+W\cdot \frac{1}{|E|}\sum _{g\in E}D({\pi }^{\prime }(f(g)),{\pi }^{\prime }(w(g)))$$

其中$W$是扩展集权重（pyqpanda3中为0.1）。这种前瞻机制防止算法做出导致糟糕全局结果的局部贪心选择。

衰减代价函数

衰减代价函数（在optimization_level >= 2时使用）添加衰减机制以防止相同的量子比特被重复交换：

$$H_{\text{decay}}(\text{SWAP})=max(\text{decay}[q_1],\text{decay}[q_2])\cdot H_{\text{lookahead}}(\text{SWAP})$$

每次SWAP涉及量子比特$q_i$时，其衰减因子乘以$\text{decay\_rate}$：

$$\text{decay}[q_i]\leftarrow \text{decay}[q_i]+\text{decay\_rate}$$

衰减值会周期性重置（pyqpanda3中每5次SWAP迭代，由DECAY_RESET_INTERVAL控制）以防止永久惩罚。

扩展集(The Extended Set)

扩展集是一个有界的前瞻窗口，包含即将到来的双比特门。pyqpanda3使用get_extended_set方法构建它，该方法：

1. 检查每条量子比特线路的依赖层。
2. 收集即将到来的双比特门伙伴，最多EXTEND_SET_SIZE（pyqpanda3中为20）个条目。
3. 计算当前映射下扩展集中量子比特对之间的总距离$E_{\text{sum}}$。

扩展集使路由算法能够"向前看"，避免那些帮助当前前沿层但给后续门带来问题的SWAP选择。

双向遍历(Bidirectional Traversal)

SABRE的一个关键创新是双向（前向-后向-前向）遍历：

1. 前向遍：从头到尾路由线路。这产生映射${\pi }_{\text{fwd}}$。
2. 后向遍：使用${\pi }_{\text{fwd}}$作为初始映射，从尾到头路由反转的线路。这产生${\pi }_{\text{bwd}}$。
3. 最终前向遍：使用${\pi }_{\text{bwd}}$作为初始映射，再次从头到尾路由线路。

其思想是前向遍产生一个粗略的映射，后向遍通过从反方向考虑线路来改进它，最终前向遍使用改进后的映射生成路由后的线路。这种三遍方法通常比单遍方法找到显著更好的映射。

为什么双向遍历有效

考虑一个线路，其中最后一个门需要量子比特0和3相邻，但初始映射将它们放得很远。单次前向遍会逐步移动量子比特到合适位置，但早期的门会"浪费"不影响后续门的SWAP。通过首先反向遍历，算法了解到量子比特0和3在末尾应该相邻，最终前向遍可以在线路早期规划SWAP以满足早期和后期的需求。

在pyqpanda3中，这种双向遍历在RoutingPass::operate中实现。当未提供初始映射时，算法：

1. 将线路量子比特分配到拓扑图的最长路径。
2. 运行SABRE先前进后后退以学习良好的初始映射。
3. 最后一次运行SABRE前进以生成路由后的线路。

计算示例

考虑在4量子比特线性拓扑0 -- 1 -- 2 -- 3上路由一个简单线路：

Circuit: CX(0,2) --> CX(1,3) --> CX(0,3)

初始映射：$\pi =\{0\to 0,1\to 1,2\to 2,3\to 3\}$

步骤1：前沿层$F=\{\text{CX}(0,2)\}$。

• 距离$D[0][2]=2>1$，因此此门不可执行。
• SWAP候选：$(0,1)$和$(1,2)$（与量子比特0和2相邻的边）。
• 评估SWAP$(0,1)$：新距离$D[1][2]=1$。分数下降。
• 评估SWAP$(1,2)$：新距离$D[0][1]=1$。分数也下降。
• 选择最佳SWAP。结果：施加SWAP$(0,1)$。映射变为$\pi =\{0\to 1,1\to 0,2\to 2,3\to 3\}$。

步骤2：前沿层$F=\{\text{CX}(0,2)\}$。

• 距离$D[\pi (0)][\pi (2)]=D[1][2]=1$。门可执行。
• 执行$\text{CX}(0,2)$。将$\text{CX}(1,3)$添加到$F$。

步骤3：前沿层$F=\{\text{CX}(1,3)\}$。

• 距离$D[\pi (1)][\pi (3)]=D[0][3]=3>1$。不可执行。
• SWAP候选包括$(0,1),(2,3)$（与量子比特$\pi (1)=0$和$\pi (3)=3$相邻的边）。
• 算法选择使量子比特0和3更靠近的SWAP。

此过程持续直到所有门被执行。插入的SWAP总数取决于使用的代价函数和初始映射的质量。

并行执行

pyqpanda3通过同时运行具有不同初始映射的多个SABRE实例来并行化路由搜索。默认使用2个并行工作线程（PARALLEL_SLOVER_CORE = 2）：

• 工作线程0从线路量子比特按正序映射到最长路径开始。
• 工作线程1从线路量子比特按逆序映射到最长路径开始。

每个工作线程独立运行前向-后向-前向遍历。第一个完成的工作线程提供结果，其他工作线程通过原子标志提前停止。

SABRE详细伪代码

以下伪代码描述了pyqpanda3中SABRE路由算法的实现：

Algorithm: SABRE Routing
Input:  Circuit gates G, coupling graph topology T,
        initial mapping pi, routing method m
Output: Routed circuit C'

1.  Compute distance matrix D from T using Dijkstra
2.  F <-- front layer of G (gates with no predecessors)
3.  decay[i] <-- 1 for all physical qubits i
4.  C' <-- empty circuit

5.  while F is not empty:
6.      executable <-- {g in F : D[pi(q_a)][pi(q_b)] == 1}
7.      for each g in executable:
8.          Append g to C'
9.          Remove g from F
10.         Add successors of g to F (if all predecessors done)

11.     if F is not empty:
12.         // Compute extended set E for lookahead
13.         (E, E_sum) <-- get_extended_set(F, pi, D)
14.
15.         // Generate SWAP candidates
16.         candidates <-- all SWAPs on edges adjacent to
17.                        qubits in F
18.
19.         // Evaluate each candidate
20.         best_swap <-- null
21.         best_score <-- +infinity
22.         for each (q1, q2) in candidates:
23.             pi' <-- pi with q1 and q2 swapped
24.             if method == "basic":
25.                 score <-- basic_cost(q1, q2, D, F)
26.             else if method == "lookahead":
27.                 score <-- lookahead_cost(q1, q2, D, F, E)
28.             else if method == "decay":
29.                 score <-- decay_cost(q1, q2, D, F, E, decay)
30.             if score < best_score:
31.                 best_score <-- score
32.                 best_swap <-- (q1, q2)
33.
34.         // Apply the best SWAP
35.         Append SWAP(best_swap) to C'
36.         Update pi by swapping q1 and q2
37.         Update decay for q1 and q2
38.         Reset decay every DECAY_RESET_INTERVAL iterations

39. return C'

与其他路由算法的比较

特性	SABRE	随机SWAP	基本贪心
确定性	启发式（给定相同初始映射时确定性）	随机化	确定性
前瞻	有（扩展集）	无	无
双向	有（前向-后向-前向）	无	无
衰减机制	有（防止循环）	无	无
并行性	有（多种初始映射）	有（多次试验）	无
SWAP数量	低	中	高
运行时间	$O(|G{|}^2\cdot |V|)$	$O(|G{|}^2\cdot |V|\cdot k)$	$O(|G{|}^2\cdot |V|)$
可扩展性	良好，可达100+量子比特	中等	良好

SABRE的优势来自其以下组合：

1. 通过扩展集的前瞻，防止短视的SWAP选择。
2. 双向遍历，寻找更好的初始映射。
3. 衰减机制，防止重复的SWAP模式。
4. 并行执行，探索多种初始映射候选。

pyqpanda3中的路由

当使用非空的chip_topology_edges参数调用Transpiler.transpile()时，路由会自动执行。当拓扑为空时，路由完全跳过：

from pyqpanda3.transpilation import Transpiler, generate_topology

topo = generate_topology(5, "linear")
transpiler = Transpiler()

# Routing is applied because topology is non-empty
result = transpiler.transpile(prog, chip_topology_edges=topo,
                              optimization_level=2,
                              basic_gates=["RX", "RY", "RZ", "CNOT"])

# Routing is skipped because no topology is specified
result = transpiler.transpile(prog, optimization_level=1)

optimization_level参数影响路由：

• 在级别0或1，使用默认的SABRE路由方法。
• 在级别2，使用"decay"路由方法，添加衰减代价函数以防止次优SWAP模式。

处理动态线路

pyqpanda3的编译器支持包含经典控制流（if-else分支、while循环）的动态线路(Dynamic Circuits)。当遇到条件分支时，编译器：

1. 处理分支之前的主门序列。
2. 独立地递归编译条件分支的每个分支，在各分支之间保持当前的量子比特映射。
3. 继续处理分支之后的剩余门。

这确保了在动态线路的所有执行路径上保持量子比特映射的一致性。

---

综合应用(Putting It All Together)

下图展示了编译理论的四个组成部分如何在pyqpanda3中协同工作：

实际示例

使用pyqpanda3的完整编译工作流：

import numpy as np
from pyqpanda3.core import QProg, H, CNOT, RX
from pyqpanda3.transpilation import Transpiler, generate_topology, decompose

# Build a quantum program
prog = QProg()
prog << H(0) << CNOT(0, 1) << RX(1, np.pi/4) << CNOT(1, 2) << H(2)

# Inspect the original circuit
print("Original depth:", prog.depth())
print("Original gate counts:", prog.count_ops())

# Generate a chip topology
topology = generate_topology(5, "linear")

# Transpile with optimization level 2 and target gate set
transpiler = Transpiler()
result = transpiler.transpile(
    prog,
    chip_topology_edges=topology,
    optimization_level=2,
    basic_gates=["RX", "RY", "RZ", "CNOT"]
)

# Inspect the transpiled circuit
print("Transpiled depth:", result.depth())
print("Transpiled gate counts:", result.count_ops())
circ = result.to_circuit()
print("Two-qubit gates:", circ.num_2q_gate())

检查中间结果

pyqpanda3提供了多种方法来分析编译前后的线路：

方法	适用对象	描述
depth(include_barrier)	QProg, QCircuit	线路深度（DAG中的最长路径）
count_ops()	QProg, QCircuit	门类型计数字典
gate_operations()	QProg	所有门操作列表
num_2q_gate()	QCircuit	双比特门数量
flatten()	QProg	展平嵌套线路结构

这些方法可用于比较原始线路和编译后的线路，验证编译减少了门数量和深度同时保持了正确性。

---

参考文献(References)

1. Li, G., Ding, Y., & Xie, Y. (2019). Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. ASPLOS 2019. (SABRE算法)
2. Shende, T. S., Bullock, S. S., & Markov, I. L. (2006). Synthesis of Quantum Logic Circuits. IEEE Transactions on CAD. (量子Shannon分解)
3. Khaneja, N., & Glaser, S. J. (2001). Cartan Decomposition of SU(2^n) and Control of Spin Systems. Chemical Physics. (KAK分解)
4. Dawson, C. M., & Nielsen, M. A. (2006). The Solovay-Kitaev Algorithm. Quantum Information and Computation.
5. Iten, R., et al. (2016). Quantum Circuits for Isometries. Physical Review A. (等距分解)

另见(See Also)

• Transpiler API
• decompose API
• generate_topology API
• transpilation模块概述