Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits
Jin-Tai Yan · IEEE Transactions on Quantum Engineering · 2023
It is important for the design of a distributed quantum circuit (DQC) to minimize the communication cost ink-way balanced partitioning. In this article, given an original quantum circuit (QC), a partitioning numberk, the maximum capacity δ inside each partition, and the maximum size tolerance γ between two partitions, a newk-way (δ, γ)-balanced partitioning problem can be formulated as ak-way partitioning problem under the capacity constraint δ and the size-tolerance constraint γ, and a fuzzy-based partitioning algorithm can be proposed to minimize the communication cost ink-way (δ, γ)-balanced partitioning for a DQC design. First, an edge-weighted connection graph can be constructed from the gates in a given QC. Furthermore, based on the estimation of the probabilistic connection strength between two vertices in the connection graph and theinitial k-waypartitioning result in the connection graph, the fuzzy memberships onkclusters can be generated in fuzzyk-means graph clustering. Finally, based on the fuzzy memberships onkclusters in the connection graph, the maximum capacity inside each partition, and the maximum size tolerance between two partitions, all the vertices in the connection graph can be assigned ontokpartitions to minimize the communication cost ink-way (δ, γ)-balanced partitioning. Compared with Daei's recursive Kernighan–Lin-based algorithm in four-way balanced partitioning, the experimental results show that the proposed fuzzy-based partitioning algorithm with three size-tolerance constraints γ = 1, γ = 2, and γ = 3 can use 58.3%, 61.3%, and 64.5% of CPU time to reduce 16.1%, 21.2%, and 24.6% of the communication cost for the eight tested circuits on the average, respectively. Compared with the modified partitioning algorithm from Dadkhah's partitioning algorithm in three-way, four-way, or five-way balanced partitioning, the experimental results show that the proposed fuzzy-based partitioning algorithm with the size-tolerance constraint γ = 3 can use 35.0% of CPU time to reduce 11.1% of the communication cost for the eight tested circuits on the average, respectively.