REDUCING QUBIT REQUIREMENTS FOR SHOR’S FACTORIZATION ALGORITHM VIA LATTICE-BASED POST-PROCESSING

The practical implementation of Shor’s algorithm [Shor, 1999] represents one of the
greatest challenges in modern quantum computing. The primary obstacle to its execution is the
high number of qubits required for phase estimation with sufficient precision to recover the order
via continued fractions, demanding a control register of size 2n. This work proposes a methodology
to evaluate the potential reduction in these requirements by substituting standard post-processing
with a lattice reduction-based approach. By combining multiple lower-precision quantum runs
using the LLL (Lenstra–Lenstra–Lovász) algorithm, we demonstrate that factorization is feasible
with a significantly smaller number of qubits. The results confirm a favorable trade-off between
quantum space complexity and classical computational effort, indicating that registers with 60% of
the original size are sufficient when combined with at least 10 measurements and the LLL algorithm.
This approach constitutes a promising path for the early execution of Shor’s algorithm on NISQ
devices.