An Algorithm of Optimization for Linear Nearest Neighbor Quantum Circuits by Parallel Processing

In order to realize the linear nearest neighbor(LNN) of quantum circuits and reduce the quantum cost of the linear reversible quantum circuits, a method of synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication is proposed. This method shows the matrix representation of linear quantum circuits by proposing the matrix representation of the CNOT gate and the SWAP gate. The rule of judging whether a two-qubit quantum circuit is in LNN state is proposed. The LNN realization by adding SWAP gates is proposed and the equivalence of two ways of adding SWAP gates is proved. The elimination rules of SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose a particular algorithm to realize the LNN, which can effectively reduce the quantum cost and improve calculation efficiency by inserting the SWAP gates on parallel computing devices. Experiments show that the quantum cost can be improved by 34.31% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm.