QM-DLA: an efficient qubit mapping method based on dynamic look-ahead strategy

Quantum computing has already demonstrated great computational potential across multiple domains and has received more and more attention. However, due to the connectivity limitations of Noisy Intermediate-Scale Quantum (NISQ) devices, most of the quantum algorithms cannot be directly executed witho...

Full description

Saved in:
Bibliographic Details
Published in:Scientific reports 2024-06, Vol.14 (1), p.13118-13
Main Authors: Liu, Hui, Zhang, Bingjie, Zhu, Yu, Yang, Hanxiao, Zhao, Bo
Format: Article
Language:English
Subjects:
639/705/117
639/766/483/481
Algorithms
Dynamic look-ahead
Gates
Humanities and Social Sciences
Mapping
multidisciplinary
Quantum circuit
Quantum computing
Qubit mapping
Science
Science (multidisciplinary)
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Quantum computing has already demonstrated great computational potential across multiple domains and has received more and more attention. However, due to the connectivity limitations of Noisy Intermediate-Scale Quantum (NISQ) devices, most of the quantum algorithms cannot be directly executed without the help of inserting SWAP gates. Nevertheless, more SWAP gates lead to a longer execution time and, inevitably, lower fidelity of the algorithm. To this end, this paper proposes an optimized qubit mapping algorithm based on a dynamic look-ahead strategy to minimize the number of SWAP gates inserted. Firstly, a heuristic algorithm is proposed based on maximizing physical qubit connectivity to generate the optimal initial qubit mapping, which reduces the need for logical qubit shifts during subsequent SWAP gate insertion. Secondly, in the form of directed acyclic graphs, we identify quantum gates that violate the constraints of physical coupling and insert SWAP gates to remap qubits, thereby overcoming the limitations of qubit interactions. Finally, the optimal SWAP gate insertion strategy is built by comparing the cost of different SWAP gate insertion strategies through a multi-window look-ahead strategy to reduce the number of SWAP gates inserted. The experimental results show that the strategy in this paper decreases the number of SWAP gate insertions and significantly reduces the depth of quantum circuits when performing qubit mapping compared with state-of-the-art methods.
ISSN:2045-2322
2045-2322
DOI:10.1038/s41598-024-64061-0