Abstract
Due to the short decohorence time of qubits available in the NISQ-era, it is essential to pack (minimize the size and or the depth of) a logical quantum circuit as efficiently as possible given a sparsely coupled physical architecture. In this work we introduce a locality-aware qubit routing algorithm based on a graph theoretic framework. Our algorithm is designed for the grid and certain 'grid-like' architectures. We experimentally show the competitiveness of algorithm by comparing it against the approximate token swapping algorithm, which is used as a primitive in many state-of-the-art quantum transpilers. Our algorithm produces circuits of comparable depth (better on random permutations) while being an order of magnitude faster than a typical implementation of the approximate token swapping algorithm.
| Original language | English |
|---|---|
| Title of host publication | Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022 |
| Pages | 607-613 |
| Number of pages | 7 |
| ISBN (Electronic) | 9781665497473 |
| DOIs | |
| State | Published - 2022 |
| Event | 36th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022 - Virtual, Online, France Duration: May 30 2022 → Jun 3 2022 |
Publication series
| Name | Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022 |
|---|
Conference
| Conference | 36th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022 |
|---|---|
| Country/Territory | France |
| City | Virtual, Online |
| Period | 5/30/22 → 6/3/22 |
Bibliographical note
Publisher Copyright:© 2022 IEEE.
Keywords
- grid graphs
- parallel token swapping
- qubit routing
ASJC Scopus subject areas
- Artificial Intelligence
- Computer Networks and Communications
- Hardware and Architecture
- Information Systems
- Software
- Control and Optimization