6、近期量子计算中的多编程机制解析

近期量子计算中的多编程机制解析

1. 量子电路分区算法

在量子计算中，量子电路分区是一个关键环节。这里介绍两种重要的分区算法：GSP 算法和 QHSP 算法。

1.1 GSP 算法复杂度

设硬件量子比特（物理量子比特）数量为 (n)，需要分配分区的电路量子比特（逻辑量子比特）数量为 (k)。GSP 算法从 (n) 个量子比特硬件中选择 (k) 个子图的所有组合，其时间复杂度为 (O(C(n, k)))，也就是 (O(n \choose k))。对于每个子图，它计算其保真度得分，包括计算最长最短路径，这部分的复杂度为 (O(k^3))。最终，其复杂度等同于 (O(k^3 \min(n^k, n^{n - k})))。在大多数情况下，电路量子比特数量小于硬件量子比特数量，所以时间复杂度变为 (O(k^3 n^k))，并且随着电路量子比特数量的增加呈指数增长。

1.2 QHSP 算法

QHSP 算法用于量子电路分区，它考虑耦合图、校准数据、串扰特性和已使用的量子比特，从起始点生成分区，优化量子比特放置并最小化串扰。
-起始点收集：QHSP 算法首先收集 (m) 个起始点，其中 (m \leq n)。为了得到起始点，需要对 (n) 个物理量子比特按其物理节点度进行排序，这需要 (O(n \log(n))) 的时间。然后，遍历电路的所有门（例如电路有 (g) 个门），并根据逻辑节点度对 (k) 个逻辑量子比特进行排序，这需要 (O(g + k \log(k))) 的时间。
-合并过程：对于每个起始点，算法迭代地合并最佳邻居量子比特，直到每个