Abstract: Linear nearest neighbor (LNN) quantum circuit is an important quantum circuit architecture, which lays a foundation for the physical realization of quantum circuit. In order to construct LNN quantum logic circuits, a linear nearest neighbor logic synthesis algorithm based on pre-evaluation is proposed. In this algorithm, partial non-nearest neighbor quantum circuits are globally reordered firstly, then the reordered quantum circuits are evaluated by heuristic method, and the set of quantum circuits with the lowest nearest neighbor cost is found by computing the minimum chaos value. Finally, SWAP gates are added to convert the quantum circuit to a nearest neighbor structure with the lowest quantum cost. Through pre-evaluation, on the one hand, the algorithm can accurately calculate whether there are redundant SWAP gates that can be deleted in the quantum circuit and delete them. On the other hand, it can minimize the number of SWAP gates added when each non-nearst neighbor quantum gate is converted into LNN quantum gate, and then the quantum circuit with the lowest quantum cost is obtained. The experimental results show that compared with the known algorithm, the proposed algorithm has less average gates, higher optimization rate of quantum cost and a wider application range.

Key words: quantum circuit, linear nearest neighbor, SWAP gate, quantum cost