Locality-aware Qubit Routing for the Grid Architecture

Avah Banerjee, Xin Liang, R. Tohid

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

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 languageEnglish
Title of host publicationProceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022
Pages607-613
Number of pages7
ISBN (Electronic)9781665497473
DOIs
StatePublished - 2022
Event36th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022 - Virtual, Online, France
Duration: May 30 2022Jun 3 2022

Publication series

NameProceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022

Conference

Conference36th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022
Country/TerritoryFrance
CityVirtual, Online
Period5/30/226/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

Fingerprint

Dive into the research topics of 'Locality-aware Qubit Routing for the Grid Architecture'. Together they form a unique fingerprint.

Cite this