Abstract
Shor's algorithm has seriously challenged information security based on
public key cryptosystems. However, to break the widely used RSA-2048 scheme,
one needs millions of physical qubits, which is far beyond current technical
capabilities. Here, we report a universal quantum algorithm for integer
factorization by combining the classical lattice reduction with a quantum
approximate optimization algorithm (QAOA). The number of qubits required is
O(logN/loglog N), which is sublinear in the bit length of the integer $N$,
making it the most qubit-saving factorization algorithm to date. We demonstrate
the algorithm experimentally by factoring integers up to 48 bits with 10
superconducting qubits, the largest integer factored on a quantum device. We
estimate that a quantum circuit with 372 physical qubits and a depth of
thousands is necessary to challenge RSA-2048 using our algorithm. Our study
shows great promise in expediting the application of current noisy quantum
computers, and paves the way to factor large integers of realistic
cryptographic significance.