Optimization of CNOT circuits on limited connectivity architecture
A 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 {limited connectivity architecture}. To
improve the performance of CNOT circuits on NISQ devices, we investigate the
optimization of the size/depth of CNOT circuits under the limited connectivity
architecture. We present a method that can optimize the size of any $n$-qubit
CNOT circuit $O\left(\frac{n^2}{\log \delta}\right)$ on any connected graph
with minimum degree $\delta$, and prove this bound is optimal for the regular
graph. For the near-term sparsely connected structure, we additionally present
a method that can optimize the size of any $n$-qubit CNOT circuit to below
$2n^2$. The numerical experiment shows that our method performs better than
state-of-the-art results. Specifically, we present an example to illustrate the
applicability of our algorithm. 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). Experimental results indicate that this method has significant
improvements compared with all of the existing methods. We additionally test
our algorithms on the five-qubit IBMQ devices, and the experiments show that
the measurement results of the optimized circuit with our algorithm are more
robust to noise compared with the IBM mapping method.
Bujiao Wu Xiaoyu He Shuai Yang Lifu Shou Guojing Tian Jialin Zhang Xiaoming Sun