Fast quantum modular exponentiation architecture for Shor's factoring algorithm (pp0649-0682)
          Archimedes Pavlidis and Dimitris Gizopoulos
          doi: https://doi.org/10.26421/QIC14.7-8-8
Abstracts: 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 quantum modular multiplier which is the fundamental block for the 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 classic 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.
Key words: quantum circuits, Shor’s algorithm, quantum Fourier transform, quantum multiplier, quantum divider