Optimization for Gaussian Elimination-Based NNA-Compliant Circuit Synthesis Method by Inserting CN OT Gates

Quantum circuits should comply with the Nearest Neighbor Architecture (NNA), which primarily supports only two-qubit operations between adjacent qubits. Typically, con-verting 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, resulting in an 18% reduction in the number of CNOT gates by inserting CNOT gates, compared to the original GE-based method.