The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth

Abstract

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor $n$-bit integers of the form $P^{2}Q$ with $\log Q=\Theta (n^a)$ for $a\in (2/3,1)$ in space and depth sublinear in n (specifically, $\tilde{O}(\log Q)$) using $\tilde{O}(n)$ quantum gates; for these integers, no known classical algorithms exploit the relatively small size of $Q$ to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.

STOC 2025; minor updates

References in corpus (14)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Networks for Elementary Arithmetic Operations
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Efficient Networks for Quantum Factoring
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Quantum algorithms for computing short discrete logarithms and factoring RSA integers
• Semi-Quantum Money
• Extending Regev's factoring algorithm to compute discrete logarithms
• A deterministic algorithm for finding $r$-power divisors
• Lattice-Based Quantum Advantage from Rotated Measurements
• On verifiable quantum advantage with peaked circuit sampling
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
• Hidden-State Proofs of Quantumness

Cited by in corpus (1)

• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth