Factoring integers with sublinear resources on a superconducting quantum processor

Understand

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.