Optimization for Gaussian Elimination-based NNA-compliant Circuit Synthesis method by Inserting CNOT Gates

Quantum circuits ought to comply with the Nearest Neighbor Architecture (NNA), which primarily supports two-qubit operations only between adjacent qubits. Typically, converting a quantum circuit to an NNA-compliant circuit involves the insertion of SWAP gates. However, employing Gaussian Elimination often results in a smaller NNA-compliant quantum circuit. If we fix the order of qubits to apply Gaussian Elimination (GE), it appears there is no room to improve the GE-based synthesis method. This paper reveals that we can enhance the GE-based method by inserting CNOT gates before and/or after a target circuit in many cases. As a result, we achieve a reduction of approximately 16% in the number of CNOT gates by inserting CNOT gates into the target circuits, compared to the original GE-based method. Additionally, we utilize a Simulated Annealing (SA)-based method to achieve an optimal circuit and achieve an 18% reduction in the number of CNOT gates by inserting CNOT gates, compared to the original GE-based method.