Effective Strategy for Non-adjacent Quantum Gates Transformation in Quantum Circuits

This paper proposes an approach to transform a quantum circuit which contains non-adjacent two-qubit gates to an efficient equivalent containing only the adjacent two-qubit gates. We show how to reduce the problem of transforming the quantum circuits into the problem of finding the shortest path in a layered directed acyclic graph. However, the available algorithms to find the shortest path are not efficient enough to solve this problem. Thus, a heuristic algorithm with the runtime of O(mn²) is proposed. Extensive simulations show that the algorithm is efficient and effective enough to find the shortest path, although it does not always guarantee the optimal solution.