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

Gregory D. Kahanamoku-MeyerMIT, Seyoon RagavanMIT, Vinod VaikuntanathanMIT, Katherine Van KirkHarvard · 2024

Read The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth by Gregory D. Kahanamoku-MeyerMIT, Seyoon RagavanMIT, Vinod VaikuntanathanMIT, Katherine Van KirkHarvard (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-12558.txt.

Introduction

Factoring large numbers is the hardness that underpins RSA encryption, and quantum circuits for it usually demand huge resources. Gregory Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, and Katherine Van Kirk present in 2024 a far leaner circuit. It factors a broad class of integers: numbers built as a squared prime times a smaller factor. Their classical hardness is expected to match RSA-type problems, though RSA numbers themselves are excluded.

For these numbers the circuit uses near-linear gate counts with space and depth below linear, a first for a classically hard factoring problem. The engine is a space-efficient quantum method for computing the Jacobi symbol in superposition, building on an older quantum squarefree-decomposition algorithm. The same trick extends to greatest common divisors and modular inverses. The authors note no classical shortcut exploits the small second factor, so the quantum speedup here is genuine.

Catalog record

CREATORGregory D. Kahanamoku-MeyerMIT, Seyoon RagavanMIT, Vinod VaikuntanathanMIT, Katherine Van KirkHarvard
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-12558

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth Gregory D. Kahanamoku-MeyerMIT, Seyoon RagavanMIT, Vinod VaikuntanathanMIT, Katherine Van KirkHarvard 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 n -bit integers of the form P 2 ​ Q P^{2}Q with log ⁡ Q = Θ ⁡ ( n a ) \log Q=\Theta(n^{a}) for a ∈ ( 2 / 3 , 1 ) a\in(2/3,1) in space and depth sublinear in n (specifically, O ~ ​ ( log ⁡ Q ) \widetilde{O}(\log Q) ) using O ~ ​ ( n ) \widetilde{O}(n) quantum gates; for these integers, no known classical algorithms exploit the relatively small size of Q 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 A mod B B , in the regime where B B is classical and much larger than A 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. 1 Introduction Shor’s discovery of a polynomial-time quantum algorithm for factoring numbers [ 80 ] jump-started the field of quantum computation. However, despite decades of intense research and development in quantum algorithms, quantum error correction, and quantum hardware, quantum factoring circuits remain out of reach for current devices. The difficulty is many-fold; a primary issue is that that the quantum circuits for factoring are still rather large, in terms of gate count, space complexity, and gate depth. For example, Shor’s algorithm seems to require quantum circuits of size \tilde{O}(n^{2}) to factor n -bit numbers [ 80 ] (where the notation \tilde{O} hides factors poly-logarithmic in n ); a recent improvement by Regev has reduced the asymptotic gate count to \tilde{O}(n^{3/2}) per run [ 73 ] , but the practical cost of achieving this improved scaling seems rather large [ 33 ] . Much effort has been applied to reducing the space-complexity of these circuits, for both Shor [ 9 , 84 , 79 , 29 , 27 , 8 , 82 , 87 , 35 , 37 , 43 , 38 , 36 , 48 ] and Regev’s algorithms [ 71 , 34 ] , achieving space as low as \widetilde{O}(n) or even O(n) qubits. Particularly notable is a recent work which reduced the space cost of Shor’s algorithm to n/2+o(n) qubits [ 25 ] . Yet there seems to be no fundamental obstacle preventing these costs from being improved further, and indeed if we are to have any hope of factoring classically-intractable integers on quantum computers in the near- or medium-term, it will be necessary to do so. Thus we arrive at two questions that are the focus of this paper: Are there quantum circuits for factoring with (near-)linear gate count? Could these be implemented with sub-linear space and depth? In a nutshell, our main contribution is to present the Jacobi factoring circuit , a quantum circuit for factoring a large class of integers for which efficient classical algorithms are not known. Our circuit completely factors any number N whose prime decomposition has distinct exponents, and finds at least one non-trivial factor if any exponent is \geq 2 (i.e. N is divisible by the square of some prime). Notably, this excludes RSA composites N=PQ that are a product of two primes. We state below the special case of N=P^{2}Q with P and Q prime. Theorem 1.1 (Informal, see Corollary 4.7 for formal statement) . There is a quantum circuit that factors any n -bit integer N=P^{2}Q (with P and Q prime, and Q<2^{m} for some m ) with \widetilde{O}(n) gates, \widetilde{O}(m) qubits, and \widetilde{O}(m+n/m) depth. The space and depth complexity are sublinear when m=\Theta(n^{a}) with a\in(0,1) . Algorithms to factor numbers of this form have been extensively studied in the cryptography and computational number theory literature [ 67 , 15 , 22 , 23 , 56 , 30 , 45 , 62 ] ; motivated in part by the fact that this problem’s hardness has been used as the basis of several cryptosystems [ 64 , 65 , 66 , 81 , 76 ] . Roughly speaking, to classically factor N=P^{2}Q where Q is the smaller of the two numbers, we have two choices. Either employ a class of special-purpose factoring algorithms along the lines of Lenstra’s elliptic curve method [ 53 ] , which run in time \exp(\tilde{O}(\sqrt{\log Q})) ; or use the fastest general-purpose factoring algorithm, namely the number field sieve [ 69 , 52 , 20 ] , which runs in time \exp(\tilde{O}((\log N)^{1/3})) . Which one is faster depends on how small Q is relative to N . As long as \log Q=\widetilde{\Omega}((\log N)^{2/3}) , there are no known classical algorithms that exploit the special structure in N to factor faster than general-purpose factoring algorithms. We refer the reader to Section 2.3 for more in-depth discussion on special-purpose factoring. Before proceeding further, let us mention that the other barriers to realizing integer factorization on a quantum computer come from the concrete costs of factoring circuits; from the overhead due to quantum error-correction [ 36 ] ; and from the difficulty in building quantum hardware [ 6 ] , none of which we address in this paper. We do note, however, that the Jacobi factoring circuit, appropriately instantiated, seems friendly enough to admit a concretely small realization that factors, say, 2048 -bit integers of the form stated in Theorem 1.1 , although we leave an exploration of the circuit’s concrete costs to future work. The Jacobi factoring circuit builds on the remarkable, but apparently little known, work of Li, Peng, Du and Suter [ 55 ] who constructed a quantum circuit to compute the squarefree decomposition of an integer. That is, given as input a positive integer N , find the unique A and B such that N=A^{2}B and B is not divisible by the square of any integer (greater than 1 ). The quantum part of the LPDS circuit computes a Jacobi symbol mod N , followed by a quantum Fourier transform mod N . Using the algorithm of Hales and Hallgren [ 41 ] , the quantum Fourier transform mod N can be computed (approximately) with near-linear size quantum circuits. We observe that using Schönhage’s GCD algorithm [ 77 , 83 , 7 , 58 ] , Jacobi symbols can be computed in near-linear time as well. Overall, this gives a near-linear size (and also near-linear space and depth) quantum circuit for squarefree decomposition which, in particular, factors numbers N=P^{2}Q where P,Q are prime numbers. Our Contributions. Building on the aforementioned work of Li, Peng, Du and Suter [

Read the complete text