Quantum computer architectures impose restrictions on qubit interactions.
We propose efficient circuit transformations that modify a given quantum
circuit to fit an architecture, retaining the original function up to a
permutation of the qubits. To achieve this, we first consider the qubit
movement subproblem and propose the Routing via Matchings framework to
prove tighter bounds on parallel routing.
In practice, we need to perform partial permutations, so we generalize Routing via
Matchings to thatsetting. We give new routing procedures for common architecture
graphs andfor the generalized hierarchical product of graphs, which produces
subgraphs of the Cartesian product. Second, for serial routing we consider
the Token Swapping framework and extend a 4-approximation algorithm for
general graphs to support partial permutations.
Using various heuristic
gate placement subroutines, we apply these qubit routing procedures to give
several circuit transformations. 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