Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits
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 &a...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10113735/ |
| _version_ | 1797322551890804736 |
|---|---|
| author | Jin-Tai Yan |
| author_facet | Jin-Tai Yan |
| author_sort | Jin-Tai Yan |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T05:15:57Z |
| format | Article |
| id | doaj.art-46525ae462824585bbfc8e5245ff9cc5 |
| institution | Directory Open Access Journal |
| issn | 2689-1808 |
| language | English |
| last_indexed | 2024-03-08T05:15:57Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj.art-46525ae462824585bbfc8e5245ff9cc52024-02-07T00:01:52ZengIEEEIEEE Transactions on Quantum Engineering2689-18082023-01-01411510.1109/TQE.2023.327202310113735Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum CircuitsJin-Tai Yan0https://orcid.org/0000-0002-7614-2545Graduate Institute of Sound Technology, Tainan National University of the Arts, Tainan, TaiwanIt 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.https://ieeexplore.ieee.org/document/10113735/Balanced partitioningcommunication costdistributed quantum circuit (DQC)fuzzy <named-content xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" content-type="math" xlink:type="simple"> <inline-formula> <tex-math notation="LaTeX">$k$</tex-math> </inline-formula> </named-content>-means graph clustering (FKGC) |
| spellingShingle | Jin-Tai Yan Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits IEEE Transactions on Quantum Engineering Balanced partitioning communication cost distributed quantum circuit (DQC) fuzzy <named-content xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" content-type="math" xlink:type="simple"> <inline-formula> <tex-math notation="LaTeX">$k$</tex-math> </inline-formula> </named-content>-means graph clustering (FKGC) |
| title | Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits |
| title_full | Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits |
| title_fullStr | Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits |
| title_full_unstemmed | Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits |
| title_short | Fuzzy-Based Balanced Partitioning Under Capacity and Size-Tolerance Constraints in Distributed Quantum Circuits |
| title_sort | fuzzy based balanced partitioning under capacity and size tolerance constraints in distributed quantum circuits |
| topic | Balanced partitioning communication cost distributed quantum circuit (DQC) fuzzy <named-content xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" content-type="math" xlink:type="simple"> <inline-formula> <tex-math notation="LaTeX">$k$</tex-math> </inline-formula> </named-content>-means graph clustering (FKGC) |
| url | https://ieeexplore.ieee.org/document/10113735/ |
| work_keys_str_mv | AT jintaiyan fuzzybasedbalancedpartitioningundercapacityandsizetoleranceconstraintsindistributedquantumcircuits |