Locality-Aware Qubit Routing for the Grid Architecture
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.
Recommended Citation
A. Banerjee et al., "Locality-Aware Qubit Routing for the Grid Architecture," Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022, pp. 607 - 613, Institute of Electrical and Electronics Engineers (IEEE), Jan 2022.
The definitive version is available at https://doi.org/10.1109/IPDPSW55747.2022.00103
Department(s)
Computer Science
Keywords and Phrases
Grid Graphs; Parallel Token Swapping; Qubit Routing
International Standard Book Number (ISBN)
978-166549747-3
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2022 Institute of Electrical and Electronics Engineers, All rights reserved.
Publication Date
01 Jan 2022
