Optimization of CNOT circuits on limited connectivity architecture
arXiv:1910.14478 · doi:10.1103/PhysRevResearch.5.013065
Abstract
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 -qubit CNOT circuit on any connected graph with minimum degree , 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 -qubit CNOT circuit to below . 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 -qubit CNOT circuit can be optimized to be linear in 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.
arXiv comment24 pages, 13 figures
References in corpus (19)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Elementary gates for quantum computation
- Variational Quantum Algorithms
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Improved Simulation of Stabilizer Circuits
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Characterizing Quantum Supremacy in Near-Term Devices
- Synthesis of Quantum Logic Circuits
- Efficient decomposition of quantum gates
- Fault-tolerant quantum error detection
- A comparison of the Bravyi-Kitaev and Jordan-Wigner transformations for the quantum simulation of quantum chemistry
- Quantum circuit optimizations for NISQ architectures
- Experimental quantum coding against photon loss error
- Synthesis of Arbitrary Quantum Circuits to Topological Assembly
- Ancilla-based quantum simulation
- Term Grouping and Travelling Salesperson for Digital Quantum Simulation
- Effect of ancilla's structure on quantum error correction using the 7-qubit Calderbank-Shor-Steane code
- The asymptotic complexity of matrix reduction over finite fields