一句话：提出一种理论上时间最优的 SWAP 插入方案，用于量子比特映射并给出可扩展启发式扩展。
在超导 NISQ 量子计算机中，量子比特仅与有限邻居相连，导致多数量子程序无法直接执行，编译时必须通过映射满足双量子比特门的邻接约束。已有方法多依赖插入 SWAP 门动态重映射，但往往缺乏时间最优性，或仅在特定约束下达到最优。本文提出一个理论上时间最优的 SWAP 插入方案来求解量子比特映射问题，该模型可扩展为实用启发式算法。作者利用该模型精确分析了具有重复执行模式的量子程序，首次发现二维最近邻架构上量子傅里叶变换（QFT）的最优量子比特映射模式，并给出可扩展扩展以处理大规模量子电路。
Rapid progress in the physical implementation of quantum computers gave birth to multiple recent quantum machines implemented with superconducting technology. In these NISQ machines, each qubit is physically connected to a bounded number of neighbors. This limitation prevents most quantum programs from being directly executed on quantum devices. A compiler is required for converting a quantum program to a hardware-compliant circuit, in particular, making each two-qubit gate executable by mapping the two logical qubits to two physical qubits with a link between them. To solve this problem, existing studies focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. However, most of the schemes lack the consideration of time-optimality of generated quantum circuits, or are achieving time-optimality with certain constraints. In this work, we propose a theoretically time-optimal SWAP insertion scheme for the qubit mapping problem. Our model can also be extended to practical heuristic algorithms. We present exact analysis results by using our model for quantum programs with recurring execution patterns. We have for the first time discovered an optimal qubit mapping pattern for quantum fourier transformation (QFT) on 2D nearest neighbor architecture. We also present a scalable extension of our theoretical model that can be used to solve qubit mapping for large quantum circuits.
DOI 原文 ·
@inproceedings{paperbot6118,
title = {Time-optimal Qubit mapping},
author = {Chi Zhang and Ari B. Hayes and Longfei Qiu and Yuwei Jin and Yanhao Chen and Eddy Z. Zhang},
booktitle = {ASPLOS},
year = {2021},
doi = {10.1145/3445814.3446706}
}