Compiling a high-level quantum circuit down to a low-level description that can be executed on state-of-the-art quantum computers is a crucial part of the software stack for quantum computing. One step in compiling a quantum circuit to some device is quantum circuit mapping, where the circuit is transformed such that it complies with the architecture's limited qubit connectivity. Because the search space in quantum circuit mapping grows exponentially in the number of qubits, it is desirable to consider as few of the device's physical qubits as possible in the process. Previous work conjectured that it suffices to consider only subarchitectures of a quantum computer composed of as many qubits as used in the circuit. In this work, we refute this conjecture and establish criteria for judging whether considering larger parts of the architecture might yield better solutions to the mapping problem. Through rigorous analysis, we show that determining subarchitectures that are of minimal size, i.e., of which no physical qubit can be removed without losing the optimal mapping solution for some quantum circuit, is a very hard problem. Based on a relaxation of the criteria for optimality, we introduce a relaxed consideration that still maintains optimality for practically relevant quantum circuits. Eventually, this results in two methods for computing near-optimal sets of subarchitectures$\unicode{x2014}$providing the basis for efficient quantum circuit mapping solutions. We demonstrate the benefits of this novel method for state-of-the-art quantum computers by IBM, Google and Rigetti.
翻译:将高水平量子电路归结为低水平的量子电路, 可以在高水平量子计算机上执行, 这是量子计算软件堆中的关键部分。 将量子电路编成某种设备的一个步骤是量子电路绘图, 电路的转换使其符合建筑中有限的qubit连接性。 由于量子电路绘图的搜索空间在Qqubit数量上成倍增长, 最好在工艺过程中尽可能考虑该设备的物理量方位的少。 先前的工作预测认为, 仅考虑由电路中使用的众多qubit组成的量计算机的亚表层结构。 在这项工作中, 我们反驳了这一推测, 并设定了判断考虑更大部分结构是否为绘图问题带来更好解决方案的标准。 我们通过严格的分析, 显示, 确定最小值的亚级结构, 也就是在不失去某种量子电路流的最佳绘制解决方案的情况下, 无法删除物理量子的量子。 仍然是一个非常硬的问题。 在这项工作中, 以最优的量的直值计算方法为最佳的直流计算结果, 提供了一种最优化的直径直径的直径的直径的直径标准。