Reseach On Quantum Circuits -Quantum Circuit Implementation Of The Fast Fermat Number Transform

The Shor’s algorithm can factor a large number in polynomial time, threatening the security of the popular RSA public key cryptosystem. Many efforts were made to improve Shor’s algo-rithm, among which Zalka’s used a modified version of Schonhage-Strassen algorithm to reduce the complexity of Shor’s algorithm, and a quantum circuit was introduced to compute the fast Fermat number transform used in the Schonhage-Strassen algorithm. Zalka’s circuit, however, produces garbage qubits. In quantum computing, uncleared garbage qubits are entangled with the computing results, and would lead to wrong results in worst case.A garbage-free quantum circuit for the fast Fermat number transform is created. The best know circuit costs 17/2 nblog b Toffoli gates and produce-3/2 blog b garbage bits for a Fermat num-ber transform on b integers of n+1 bits. Our circuit costs 19/2 nblog b Toffoli gates and produce no garbage for the same task. This is achieved by utilizing insights into the relationship between the garbage and result, and carefully choosing garbage-remove methods to reduce overhead. The circuit we propose can be used to reduce the complexity of Shor’s algorithm from O(n3) to O(n2 log n log log n).