The Jacobi factoring circuit, and other developments in quantum factoring

Greg Kahanamoku-Meyer (MIT) https://simons.berkeley.edu/talks/greg-kahanamoku-meyer-mit-2025-05-27 Quantum Algorithms, Complexity, and Fault Tolerance Reunion Since Shor published his famous algorithm 30 years ago, it has seemed that integer factorization requires relatively large quantum circuits, and thus will be a medium- to long-term application of quantum computing. But just in the past year or two, the cost landscape for integer factorization has changed dramatically. The main focus of this talk will be the Jacobi factoring circuit, which factors integers of the form N=P^2 Q in a qubit count and depth roughly proportional to O(log Q). For appropriately chosen parameters, we argue that this circuit may actually provide the first efficiently verifiable proof of quantumness. Given sufficient time I will also survey an array of other very recent results improving the circuit costs for integer factorization, including circuits applicable to RSA integers of the form N=PQ.