Qubit Mapping: The Adaptive Divide-and-Conquer Approach
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917770821632000 |
|---|---|
| author | Huang, Yunqi Zhou, Xiangzhen Meng, Fanxu Li, Sanjiang |
| author_facet | Huang, Yunqi Zhou, Xiangzhen Meng, Fanxu Li, Sanjiang |
| contents | The qubit mapping problem (QMP) focuses on the mapping and routing of qubits in quantum circuits so that the strict connectivity constraints imposed by near-term quantum hardware are satisfied. QMP is a pivotal task for quantum circuit compilation and its decision version is NP-complete. In this study, we present an effective approach called Adaptive Divided-And-Conqure (ADAC) to solve QMP. Our ADAC algorithm adaptively partitions circuits by leveraging subgraph isomorphism and ensuring coherence among subcircuits. Additionally, we employ a heuristic approach to optimise the routing algorithm during circuit partitioning. Through extensive experiments across various NISQ devices and circuit benchmarks, we demonstrate that the proposed ADAC algorithm outperforms the state-of-the-art method. Specifically, ADAC shows an improvement of nearly 50\% on the IBM Tokyo architecture. Furthermore, ADAC exhibits an improvement of around 18\% on pseudo-realistic circuits implemented on grid-like architectures with larger qubit numbers, where the pseudo-realistic circuits are constructed based on the characteristics of widely existing realistic circuits, aiming to investigate the applicability of ADAC. Our findings highlight the potential of ADAC in quantum circuit compilation and the deployment of practical applications on near-term quantum hardware platforms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04752 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Qubit Mapping: The Adaptive Divide-and-Conquer Approach Huang, Yunqi Zhou, Xiangzhen Meng, Fanxu Li, Sanjiang Quantum Physics The qubit mapping problem (QMP) focuses on the mapping and routing of qubits in quantum circuits so that the strict connectivity constraints imposed by near-term quantum hardware are satisfied. QMP is a pivotal task for quantum circuit compilation and its decision version is NP-complete. In this study, we present an effective approach called Adaptive Divided-And-Conqure (ADAC) to solve QMP. Our ADAC algorithm adaptively partitions circuits by leveraging subgraph isomorphism and ensuring coherence among subcircuits. Additionally, we employ a heuristic approach to optimise the routing algorithm during circuit partitioning. Through extensive experiments across various NISQ devices and circuit benchmarks, we demonstrate that the proposed ADAC algorithm outperforms the state-of-the-art method. Specifically, ADAC shows an improvement of nearly 50\% on the IBM Tokyo architecture. Furthermore, ADAC exhibits an improvement of around 18\% on pseudo-realistic circuits implemented on grid-like architectures with larger qubit numbers, where the pseudo-realistic circuits are constructed based on the characteristics of widely existing realistic circuits, aiming to investigate the applicability of ADAC. Our findings highlight the potential of ADAC in quantum circuit compilation and the deployment of practical applications on near-term quantum hardware platforms. |
| title | Qubit Mapping: The Adaptive Divide-and-Conquer Approach |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2409.04752 |