Qubit Mapping and Routing via MaxSAT

Molavi, Abtin, Xu, Amanda, Diges, Martin, Pick, Lauren, et al. · 2022 · 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)

| 编号 NA117 | 主题 线路综合与等价验证 | DOI 10.1109/micro56248.2022.00077 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

2022 · 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO) Near-term quantum computers will operate in a noisy environment, without error correction. A critical problem for near-term quantum computing is laying out a logical circuit onto a physical device with limited connectivity between qubits. This is known as the qubit mapping and routing (QMR) problem, an intractable combinatorial problem. It is important to solve QMR as optimally as possible to reduce the amount of added noise, which may render a quantum computation useless. In this paper, we present a novel approach for optimally solving the QMR problem via a reduction to maximum satisfiability (MAXSAT). Additionally, we present two novel relaxation ideas that shrink the size of the MAXSAT constraints by exploiting the structure of a quantum circuit. Our thorough empirical evaluation demonstrates (1) the scalability of our approach compared to state-of-the-art optimal QMR techniques (solves more than 3x benchmarks with 40x speedup), (2) the significant cost reduction compared to state-of-the-art heuristic approaches (an average of ~5x swap reduction), and (3) the power of our proposed constraint relaxations.

全文共 14 页；文本提取件位于 .extracted/papers/NA117.txt（不随站点发布）。

本站词条在引用该文献时，会以 wikilink（sources/NA117）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。