论文标题
通过MaxSat进行的量子映射和路由
Qubit Mapping and Routing via MaxSAT
论文作者
论文摘要
近期量子计算机将在嘈杂的环境中运行，而无需纠正错误。近期量子计算的一个关键问题是将逻辑电路铺设到量子位之间有限连接性的物理设备上。这被称为量子映射和路由（QMR）问题，这是一个棘手的组合问题。尽可能最佳地求解QMR以减少添加噪声的量很重要，这可能使量子计算变得无用。在本文中，我们提出了一种新颖的方法，可通过降低到最大满意度（MAXSAT）来最佳解决QMR问题。此外，我们提出了两个新颖的放松思想，它们通过利用量子电路的结构来缩小MaxSat约束的大小。我们彻底的实证评估表明（1）与最先进的最佳QMR技术相比，我们的方法可伸缩性（以40倍的加速求解了3倍以上的基准），（2）与最新的启发式方法相比（平均降低〜5倍SWAP）和（3）我们提出的约束的功率相比，大幅降低了成本。
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.
