IEEE Transactions on Quantum Engineering (Jan 2023)
Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits
Abstract
It is important for the design of a distributed quantum circuit (DQC) to minimize the communication cost in k-way balanced partitioning. In this article, given an original quantum circuit (QC), a partitioning number k, the maximum capacity δ inside each partition, and the maximum size tolerance γ between two partitions, a new k-way (δ, γ)-balanced partitioning problem can be formulated as a k-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 k-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 initial k-way partitioning result in the connection graph, the fuzzy memberships on k clusters can be generated in fuzzy k-means graph clustering. Finally, based on the fuzzy memberships on k 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 k partitions to minimize the communication cost in k-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.
Keywords
