SMT-Based Layout Synthesis Approaches for Quantum Circuits

The physical qubits in current quantum computers do not all interact with each other. Therefore, in executing a quantum algorithm on an actual quantum computer, layout synthesis is a crucial step that ensures that the synthesized circuit of the quantum algorithm can run smoothly on the quantum computer. In this paper, we focus on a layout synthesis problem for quantum circuits and improve a prior work, TB-OLSQ, which adopts a transition-based satisfiability modulo theories (SMT) formulation. We present how to modify TB-OLSQ to obtain an accelerated version for runtime reduction. In addition, we extend the accelerated version by considering gate absorption for better solution quality. Our experimental results show that compared with TB-OLSQ, the accelerated version achieves 121X speedup for a set of SWAP-free circuits and 6X speedup for the other set of circuits with no increase in SWAP gates. In addition, the accelerated version with gate absorption helps reduce the number of SWAP gates by 38.9% for the circuits requiring SWAP gates, while it is also 3X faster.