Quantum Factoring Algorithm: Resource Estimation and Survey of Experiments

Abstract

It is known that Shor’s algorithm can break many cryptosystems such as RSA encryption if large-scale quantum computers are realized. So far, several factorization experiments of the small composite such as 15 and 21 have been conducted by small-scale quantum computers. We investigate the details of quantum circuits used in the experiments for factoring. We then point out that some of the circuits have been constructed under the condition that the order of an element modulo a target composite is a priori known. Since the order must be unknown between the experiment, it is inappropriate as the quantum circuit for Shor’s factoring algorithm. We also point out that the circuits in the other experiments are constructed heavily relying on the composite number to be factorized.