有向无环图#
本教程将探讨如何使用 rustworkx 来处理有向无环图（也称为 DAGs）。
有向图#
作为入门，让我们首先回顾有向图（不含无环限制）的更广泛概念。
有向图由一组通过有向边（通常称为弧）连接的节点组成。有向边只能沿一个方向遍历， 这与无向图中的边不同，后者可以沿任一方向遍历。 例如：
import rustworkx as rx
from rustworkx.visualization import mpl_draw
path_graph = rx.generators.directed_path_graph(5)
mpl_draw(path_graph)
在此示例中，我们创建了一个包含5个节点的有向路径图。每条边的方向性由箭头表示，箭头指向目标节点。边的另一端节点称为源节点。
有向无环图#
有向无环图是一种同时不包含任何环的有向图。环是一种非空的轨迹[1]，其中轨迹的首尾节点相同。例如：
cycle_graph = rx.generators.directed_cycle_graph(5)
mpl_draw(cycle_graph)
是非无环的。而先前的路径图是无环的。
在rustworkx中，你可以创建一个新的PyDiGraph对象，通过使用check_cycle构造函数属性来强制禁止添加任何循环
dag = rx.PyDiGraph(check_cycle=True)
或在创建带有check_cycle属性的PyDiGraph对象之后：
dag.check_cycle = True
您也可以通过检查check_cycle属性来确认循环检查状态：
print(dag.check_cycle)
True
当把 check_cycle 设置为 True 时，向图中添加边的方法（例如 PyDiGraph.add_edge()）会在引入循环时报错。这种检查会带来显著（且可能很大）的运行时间开销，因此最好仅在绝对必要时使用。你还可以通过使用 PyDiGraph.add_parent() 和 PyDiGraph.add_child() 来避免这种开销，因为这两个方法同时添加新节点和边，且都不会引入循环。
有向无环图的应用#
任务调度#
有向无环图（定义为 \(G = (V,E)\)）的拓扑排序是指所有节点的线性排序，使得如果 \(G\) 包含边 \((u, v)\)，则 \(u\) 出现在 v 之前。这仅适用于 DAG（有向无环图），因为图中的环会让找到这样的线性排序变得不可能。
有向无环图（DAGs）的一个常见应用是利用拓扑排序来基于依赖关系调度一系列工作或任务。工作由节点表示，从节点 \(u\) 到节点 \(v\) 的边意味着工作 \(u\) 必须在工作 \(v\) 之前完成。有向无环图的拓扑排序将给出执行这些工作的顺序。例如：
from rustworkx.visualization import graphviz_draw
# Create a job dag
dependency_dag = rx.PyDiGraph(check_cycle=True)
job_a = dependency_dag.add_node("Job A")
job_b = dependency_dag.add_child(job_a, "Job B", None)
job_c = dependency_dag.add_child(job_b, "Job C", None)
job_d = dependency_dag.add_child(job_a, "Job D", None)
job_e = dependency_dag.add_parent(job_d, "Job E", None)
job_f = dependency_dag.add_child(job_e, "Job F", None)
dependency_dag.add_edge(job_a, job_f, None)
dependency_dag.add_edge(job_c, job_d, None)
graphviz_draw(dependency_dag, node_attr_fn=lambda node: {"label": str(node)})
上方我们定义了一个包含6个任务及任务间依赖关系的有向无环图。如果现在对图执行topological_sort()函数，该函数将返回一个遵循依赖关系的线性任务执行顺序。
topo_sorted = rx.topological_sort(dependency_dag)
# Print job labels
print([dependency_dag[job_index] for job_index in topo_sorted])
['Job E', 'Job A', 'Job F', 'Job B', 'Job C', 'Job D']
Qiskit编译器#
另一个使用有向无环图的应用是Qiskit中的编译器。Qiskit是一个用于处理量子计算的SDK。Qiskit的编译器内部将量子电路表示为有向无环图。Rustworkx最初是为了加速Qiskit编译器对有向无环图的使用而启动的。
为了探究Qiskit如何使用有向无环图(DAG)，我们首先需要了解量子电路。量子电路是由对量子数据进行相干量子操作组成的计算例程。它是由量子门、测量和重置等量子操作构成的有序序列，这些操作可以基于实时经典计算进行条件控制。量子电路的图形化表示如下：
┌───┐ ░ ┌─┐
q_0: ┤ H ├──■───░─┤M├───
└───┘┌─┴─┐ ░ └╥┘┌─┐
q_1: ─────┤ X ├─░──╫─┤M├
└───┘ ░ ║ └╥┘
meas: 2/══════════════╩══╩═
0 1
除了我们有2个量子比特q_0和q_1，2个经典比特c_0和c_1，以及对这些量子比特的一系列具有依赖关系的操作之外，这个电路的具体细节在此并不重要。每个量子比特上的最后操作是在q_0上的测量，结果存储在c_0中，以及在q_1上的测量，结果存储在c_1中。
我们可以将此量子电路表示为有向无环图，就像 Qiskit 内部那样：
dag = rx.PyDiGraph()
# Input nodes:
in_nodes = dag.add_nodes_from(["q_0", "q_1", "c_0", "c_1"])
# Output nodes
out_nodes = dag.add_nodes_from(["q_0", "q_1", "c_0", "c_1"])
# Add H gate
h_gate = dag.add_child(in_nodes[0], "h", "q_0")
# Add CX Gate
cx_gate = dag.add_child(h_gate, "cx", "q_0")
dag.add_edge(in_nodes[1], cx_gate, "q_1")
# Add measure Gates
meas_q0 = dag.add_child(cx_gate, "measure", "q_0")
meas_q1 = dag.add_child(cx_gate, "measure", "q_1")
# Measure q0 instruction edges
dag.add_edge(meas_q0, out_nodes[0], "q_0")
dag.add_edge(in_nodes[2], meas_q0, "c_0")
dag.add_edge(meas_q0, out_nodes[2], "c_0")
# Measure q1 instruction edges
dag.add_edge(meas_q1, out_nodes[1], "q_1")
dag.add_edge(in_nodes[3], meas_q1, "c_1")
dag.add_edge(meas_q1, out_nodes[3], "c_1")
graphviz_draw(
dag,
node_attr_fn=lambda node: {"label": str(node)},
edge_attr_fn=lambda edge: {"label": str(edge)}
)
在这种电路的表示形式中，数据通过比特的流动由边来建模。第一组节点是输入节点，最后一组是输出节点，分别代表每个比特（经典和量子）的初始状态和最终状态。编译器随后对量子电路的有向无环图（DAG）表示形式运行分析和转换，以优化量子电路，使其能够在实际硬件上执行。例如，一个简单的转换过程是将电路中的量子门转换为设备允许的门集合。如果我们尝试在原生不支持H量子门的量子处理器（QPU）上运行上述电路，首先必须将其转换为硬件实际支持的等效指令序列。执行此过程的简化视图如下：
# Equivalency matrix
translation_matrix = {"h": ["rz(pi/2)", "sx", "rz(pi/2)"]}
# Instructions natively supported on target QPU
hardware_instructions = {"measure", "cx", "sx", "rz", "x"}
# Iterate over instructions in order and replace gates outside of native
# instruction set with a subcircuit from the translation matrix
for gate_index in rx.topological_sort(dag):
if gate_index not in in_nodes and gate_index not in out_nodes:
if dag[gate_index] not in hardware_instructions:
edge_val = dag.out_edges(gate_index)[0][2]
equivalent_subcircuit = rx.PyDiGraph()
count = 0
for node in translation_matrix[dag[gate_index]]:
if count == 0:
equivalent_subcircuit.add_node(node)
else:
equivalent_subcircuit.add_child(count - 1, node, edge_val)
count += 1
def map_fn(source, target, weight):
if source == gate_index:
return len(equivalent_subcircuit) - 1
else:
return 0
dag.substitute_node_with_subgraph(
gate_index,
equivalent_subcircuit,
map_fn
)
graphviz_draw(
dag,
node_attr_fn=lambda node: {"label": str(node)},
edge_attr_fn=lambda edge: {"label": str(edge)}
)
Qiskit编译器在DAG上运行的另一个示例是执行分析，以查找所有串行执行的单量子比特门实例。这一系列量子门可以被分析并经常简化为更短的门序列。该分析的简化示例如下：
bit_nodes = {"q_0", "q_1", "c_0", "c_1"}
def filter_fn(node):
# Don't collect input or output nodes
if node in bit_nodes:
return False
# Don't include 2 qubit gates
if node == "cx":
return False
# Ignore non-unitary operations
if node == "measure":
return False
return True
runs = rx.collect_runs(dag, filter_fn)
print(runs)
[['rz(pi/2)', 'sx', 'rz(pi/2)']]
通过这个，我们拥有了构成一系列单量子比特门的 DAG 节点，我们可以对其进行分析并尝试简化。
执行简化操作时，我们将使用contract_nodes()来将一系列节点（在我们的案例中即量子门）替换为单个等效节点（门）。例如，如果由collect_runs()返回的3节点序列['rz(pi/2)', 'sx', 'rz(pi/2)']需要简化为单个门"U"，可以按如下方式实现：
# replace the newest 3 nods (which are the set returned by collect_runs())
dag.contract_nodes(range(len(dag) - 2, len(dag) + 1), "U")
graphviz_draw(
dag,
node_attr_fn=lambda node: {"label": str(node)},
edge_attr_fn=lambda edge: {"label": str(edge)}
)
在Qiskit中，节点的索引存储在节点的数据有效负载中，因此
上面的代码示例实际上写为类似
dag.contract_nodes([x._node_id for x in runs[0]], "U")。但这对
此处的简化示例不适用。