Shallow Depth Factoring Based on Quantum Feasibility Labeling and Variational Quantum Search

Large integer factorization is a prominent research challenge, particularly in the context of quantum computing. The classical computation of prime factors for an integer entails exponential time complexity. Quantum computing offers the potential for significantly faster computational processes compared to classical processors. We proposed a new quantum algorithm, Shallow Depth Factoring (SDF), to factor an integer. SDF consists of three steps. First, it converts a factoring problem to an optimization problem without an objective function. Then, we use a Quantum Feasibility Labeling (QFL) to label every possible solution according to whether it is feasible or infeasible for the optimization problem. Finally, the Variational Quantum Search (VQS) is used to find all feasible solutions. The SDF algorithm utilizes shallow-depth quantum circuits for efficient factorization, with the circuit depth scaling linearly as the integer to be factorized increases. Through minimizing the number of gates in the circuit, the algorithm enhances feasibility and reduces vulnerability to errors.