Partition-based Surface Code Compilation

Surface codes are widely considered to be one of the most promising methods for achieving fault-tolerant quantum computation on noisy intermediate-scale quantum (NISQ) computers. One of the computational challenges involved is in transpiling the logical circuit to a form that is compatible with the physical hardware that has limited qubit connectivity. In particular, the goal is to first determine a mapping from the logical qubits in the input circuit to the surface code topology, and then route them via Bell pairs, in a manner that minimizes the total execution time. We refer to this problem as the surface code logical qubit mapping and routing problem. In this work, we formulate the mapping problem as a mixed integer program (MIP) and implement an edge-disjoint path algorithm for routing. In order to handle circuits with a larger number of qubits, we introduce a divide-and-conquer (DC) strategy for scalable mapping. We evaluate our MIP-based mapping approach against structural and random mapping baselines, demonstrating improved performance on both large-scale synthetic circuits and circuits from existing quantum algorithms.