Quantum routing for architecture-respecting circuit transformations

The connectivity between qubits is one of the many design aspects that go into building a quantum computer. Better connectivity makes it easier to perform arbitrary interacting operations in quantum algorithms, but it may also come with additional noise and may be costly to manufacture. Therefore, many proposals for scalable quantum computer architectures sacrifice connectivity to obtain better modularity and suppress noise. This poses a challenge to running quantum algorithms because simulating missing connectivity can come with significant overhead.

A natural stepping stone is permuting qubits on the architecture, a task we call quantum routing. We first give a rigorous analysis for the special case of classical routing using SWAP gates. Then we present a time-independent Hamiltonian protocol that reverses a chain of qubits asymptotically 3 times faster than classical routing. Using this protocol, we exhibit the first separation between classical and quantum routing time. This leads us to lower bound unitary quantum routing to be inversely proportional to the vertex expansion of the architecture graph in a gate model and inversely proportional to the edge expansion in a Hamiltonian evolution model. We rule out a superpolynomial separation between classical and quantum routing for architectures with poor expansion properties such as grid graphs.

We then show how to use routing to transform quantum circuits such that their interactions respect the architecture constraints while attempting to minimize the depth overhead. We benchmark the performance of our circuit transformations on grid and modular architectures.

Finally, we give a circuit transformation for fault-tolerant quantum computation in the surface code. We use a construction for parallel long-range operations in constant logical time that allows us to avoid the need for routing altogether. Our benchmarks show improved performance over our previous circuit transformations using classical routing.