Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

Due to little consideration in the hardware constraints, e.g., limited connections between physical qubits to enable two-qubit gates, most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices. Dynamically remapping logical qubits to physical qubits in...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-05
Main Authors: Li, Gushu, Ding, Yufei, Xie, Yuan
Format: Article
Language:English
Subjects:
Algorithms
Controllability
Gates
Mapping
Qubits (quantum computing)
Search algorithms
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Due to little consideration in the hardware constraints, e.g., limited connections between physical qubits to enable two-qubit gates, most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices. Dynamically remapping logical qubits to physical qubits in the compiler is needed to enable the two-qubit gates in the algorithm, which introduces additional operations and inevitably reduces the fidelity of the algorithm. Previous solutions in finding such remapping suffer from high complexity, poor initial mapping quality, and limited flexibility and controllability. To address these drawbacks mentioned above, this paper proposes a SWAP-based BidiREctional heuristic search algorithm SABRE, which is applicable to NISQ devices with arbitrary connections between qubits. By optimizing every search attempt,globally optimizing the initial mapping using a novel reverse traversal technique, introducing the decay effect to enable the trade-off between the depth and the number of gates of the entire algorithm, SABRE outperforms the best known algorithm with exponential speedup and comparable or better results on various benchmarks.
ISSN:2331-8422