CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrained by their topological structures. To improve the performance of CNOT circuits on NISQ devices, we investigate the optimization of the size/depth of CNOT circuits under topological constraints. We firstly present a method that can optimize the size of any $n$-qubit CNOT circuit to less than $2n^2$ on any connected graph, which is optimal for sparsely connected structures. The simulation experiment shows that our method performs better than state-of-the-art results. Specifically, we present two detailed examples to illustrate the applicability of our algorithm. Furthermore, for the future device with a denser structure, we give a better optimization method that achieves $O(n^2/log delta)$ size on a graph with the minimum degree $delta$, which is optimal on the regular graph. Secondly, for the grid structure, which is commonly used in current quantum devices, we demonstrate that the depth of any $n$-qubit CNOT circuit can be optimized to be linear in $n$ with certain ancillary qubits (ancillas). Our experimental results indicate this method has significant improvements compared with all of the existing methods. We further implement the two circuits commonly used in quantum variational algorithms and quantum chemistry on the 5-qubit IBMQ devices by leverage of our optimization algorithm, the experimental results show the optimized circuit has far less error when there exists noise compared to IBM mapping method.
Download