CNOT-count optimized quantum circuit of the Shor's algorithm

Abstract

We present improved quantum circuit for modular exponentiation of a constant, which is the most expensive operation in Shor's algorithm for integer factorization. While previous work mostly focuses on minimizing the number of qubits or the depth of circuit, we try to minimize the number of CNOT gate which primarily determines the running time on a ion trap quantum computer. First, we give the implementation of basic arithmetic with known lowest number of CNOT gate and the construction of improved modular exponentiation of a constant by accumulating intermediate date and windowing technique. Then, we precisely estimate the number of improved quantum circuit to perform Shor's algorithm for factoring a $n$-bit integer, which is $217\frac{n^3}{{\log }_{2}n}+4n^2+n$. According to the number of CNOT gates, we analyze the running time and feasibility of Shor's algorithm on a ion trap quantum computer. Finally, we discuss the lower bound of CNOT numbers needed to implement Shor's algorithm.

References in corpus (16)

• Quantum Networks for Elementary Arithmetic Operations
• High-fidelity quantum logic gates using trapped-ion hyperfine qubits
• High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Semiclassical Fourier Transform for Quantum Computation
• Quantum Circuits Architecture
• A new quantum ripple-carry addition circuit
• Halving the cost of quantum addition
• Efficient Networks for Quantum Factoring
• Quantum circuit optimizations for NISQ architectures
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Fast versions of Shor's quantum factoring algorithm
• Factoring in a Dissipative Quantum Computer
• Comparison of Cloud-Based Ion Trap and Superconducting Quantum Computer Architectures
• Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm
• On the post-quantum security of encrypted key exchange protocols