The Jacobi Factoring Circuit: Classically Hard Factoring in Sublinear Quantum Space and Depth | Quantum Colloquium

In this talk, we present a compact quantum circuit for factoring n-bit integers of the form P^2 Q. When log Q = O(n^a) for 2/3 < a < 1, the space and depth of this circuit are sublinear in n (specifically, Otilde(log Q)) and the number of gates is Otilde(n); at the same time, 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. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known. 

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. Finally, we note that 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.

Joint work with Gregory D. Kahanamoku-Meyer, Vinod Vaikuntanathan, and Katherine Van Kirk: https://arxiv.org/abs/2412.12558.

Panel Discussion: Zvika Brakerski (Weizmann Institute of Technology), Martin Ekerå (KTH), Antoine Joux (Sorbonne Université)