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.
Hackernews
All GNU social JP content and data are available under the Creative Commons Attribution 3.0 license.