Quantum computer architectures impose restrictions on qubit interactions. We
propose efficient circuit transformations that modify a given quantum circuit
to fit an architecture, allowing for any initial and final mapping of circuit
qubits to architecture qubits. To achieve this, we first consider the qubit
movement subproblem and use the routing via matchings framework to prove
tighter bounds on parallel routing. In practice, we only need to perform
partial permutations, so we generalize routing via matchings to that setting.
We give new routing procedures for common architecture graphs and for the
generalized hierarchical product of graphs, which produces subgraphs of the
Cartesian product. Secondly, for serial routing, we consider the token swapping
framework and extend a 4-approximation algorithm for general graphs to support
partial permutations. We apply these routing procedures to give several circuit
transformations, using various heuristic qubit placement subroutines. We
implement these transformations in software and compare their performance for
large quantum circuits on grid and modular architectures, identifying
strategies that work well in practice.

本文提出了一种基于路由替换框架的量子计算机电路变换方法，用于解决电路与体系结构之间的差异，通过采用不同的启发式置换子例程来提高性能，实现了在网格和模块化体系结构上进行大型量子电路比较的策略。