| Summary: | It is important for the design of a distributed quantum circuit (DQC) to minimize the communication cost in <italic>k</italic>-way balanced partitioning. In this article, given an original quantum circuit (QC), a partitioning number <italic>k</italic>, the maximum capacity δ inside each partition, and the maximum size tolerance γ between two partitions, a new <italic>k</italic>-way (δ, γ)-balanced partitioning problem can be formulated as a <italic>k</italic>-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 in <italic>k</italic>-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 the <italic>initial k-way</italic> partitioning result in the connection graph, the fuzzy memberships on <italic>k</italic> clusters can be generated in fuzzy <italic>k</italic>-means graph clustering. Finally, based on the fuzzy memberships on <italic>k</italic> clusters 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 onto <italic>k</italic> partitions to minimize the communication cost in <italic>k</italic>-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.
|
|---|