一句话：提出SABRE——一种基于SWAP的双向启发式搜索算法，高效解决NISQ器件上的量子比特映射问题。
NISQ器件的物理量子比特连接受限，多数量子算法无法直接执行；编译器需动态重映射逻辑量子比特到物理量子比特以支持双量子比特门，但这会增加操作并降低保真度。已有方法复杂度高、初始映射质量差、灵活性有限。本文提出SABRE，一种基于SWAP的双向启发式搜索算法，适用于任意量子比特连接的NISQ设备。它优化每次搜索尝试，用反向遍历技术全局优化初始映射，并引入衰减效应权衡门深度与门数量。实验显示，SABRE相比最优已知算法取得指数级加速，并在多个基准上结果相当或更优。
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.
DOI 原文 ·
@inproceedings{paperbot4929,
title = {Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices},
author = {Gushu Li and Yufei Ding and Yuan Xie},
booktitle = {ASPLOS},
year = {2019},
doi = {10.1145/3297858.3304023}
}