Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

By Gushu Li, Yufei Ding, Yuan Xie. International Conference on Architectural Support for Programming Languages and Operating Systems, 2018

773 citations recorded by the source corpus.

Due to little considerations 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 control. 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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/40f3af4560bfb6b2509d5677c40a2ab439bf4f3a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

Qubit allocation (2018, methodology): “Figure 6 provides an in-depth comparison between BMT and Sabre (sbr) [Li et al. 2019] in two quantum architectures from IBM: the 16-qubit Albatross, and the 20-qubit Tokyo.”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, background): “Recently, approaches for compiling quantum circuits, including QAOA circuits, to realistic hardware have been explored [22,35,46], but that research direction remains open to innovation.”
QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits (2021, methodology): “Effect of Pruning Ratios.”
Demonstration of quantum volume 64 on a superconducting quantum computing system (2020, methodology): “state-of-the art SABRE algorithm [20] available in Qiskit, showing substantial improvement in both the mean and maximum number of uses of the entangling gate.”