Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm

Abstract

We present a novel and efficient in terms of circuit depth design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a generic modular quantum multiplier which is the fundamental block for modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about $2000n^2$ and requires $9n+2$ qubits, where $n$ is the number of bits of the classical number to be factored. The total quantum cost of the proposed design is $1600n^3$. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.

To be published in Quantum Information and Computation, Vol. 14, No. 7&8 (2014) 0649-0682, 34 pages, 20 figures, 5 tables, revised October 2, 2013

Cited by in corpus (4)

• Toward the first quantum simulation with quantum speedup
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• A tree tensor network approach to simulating Shor's algorithm
• CNOT-count optimized quantum circuit of the Shor's algorithm