Abstract: Quantum circuit is required to meet the nearest neighbor constraint, and interaction occurs only between the adjacent qubits. The linear quantum circuit is an important part of quantum circuit. Linear nearest neighbor quantum circuit can be represented by Boolean matrix, and the fast determination method for the validity of Boolean matrix is investigated. The time complexity is changed from n!(n-1) to O(n2). A parallel synthesis algorithm for large scale linear nearest neighbor quantum circuit based on the valid Boolean matrix is proposed, and the circuit synthesis is completed in less than 10 s for an arbitrary linear nearest neighbor quantum circuit with 128 lines. The proposed parallel method can not only guarantee accuracy, but also greatly reduce synthesis time of quantum circuit, and scale of the solved circuit is expanded.

Key words: quantum information; linear quantum circuit; linear nearest neighbor; valid Boolean matrix; parallel synthesis algorithm