Optimizing Quantum Circuit Synthesis for Permutations on Limited Connectivity Topologies

Depth optimization of permutation circuits is an important problem because permutations can be used to map any circuit onto limited-connectivity hardware and shallower circuits take less time to execute, resulting in reduced decoherence. SAT solvers can find optimal-depth circuits, but cannot scale to large qubit numbers, and most existing depth-optimizing methods are restricted to certain topologies. We propose Left-Right Synthesis (LR-Synth), the first scalable SWAP-based depth-optimizing method for synthesizing permutations on any limited connectivity topology. LR-Synth is a divide and conquer approach that partitions the topology into two halves and moves qubits to the correct half using matchings. Its recursive nature makes it amenable for use in conjunction with exact methods to solve the small inner recursions and for parallelizing recursive calls. We benchmark LR-Synth against existing depth-optimizing methods and an optimal-depth SAT solver for topologies commonly found on physical devices such as trees, rings, and grids. LR-Synth scales better than SAT solvers, yet achieves close-to-optimal depths and outperforms in gate count. It is applicable to any connectivity topology, while achieving comparable results to best-known heuristics tailored to specific topologies.