Peter Shor’s quantum algorithm allows to factor a number of n binary digits using O(n) qubits connected by O(n^{2} log n) quantum logic gates (single operations), ending with O(1) quantum measurements (repeated executions) and classical polynomial-time postprocessing. Oded Regev published last year on arXiv a new factorization algorithm that requires O(n^{3/2}) quantum logic gates, although with O(n^{3/2}) cubits, O(n^{1/2}) quantum measurements and a new classical polynomial-time post-processing. Vinod Vaikuntanathan and Seyoon Ragavan published a few months later an improvement of this algorithm for which O(n) is sufficient^{3/2} log n) quantum logic gates, O(n log n) qubits, O(n^{1/2}) quantum measurements and the classical Regev post-processing. This last algorithm is more robust because it reduces the complexity constant that multiplies the number O(n^{1/2}) measures, thanks to its better tolerance of errors in logic gates. One might think that these new algorithms could be useful in fighting decoherence by reducing the computation time by decreasing the number of gates (operations). However, the new algorithms only succeed for large n; in fact, the complexity constants for these algorithms have not been calculated, so for small n Shor’s algorithm might still be more efficient. Still, factoring numbers of interest in current cryptography, such as 2048-bit RSA-2048, is beyond the realm of possibility in the next few decades, both with Shor’s algorithm and with the two new algorithms.

These two new algorithms are the first major advance in quantum number factorization in the last 30 years (several papers optimizing both algorithms have already been published). It should be remembered that the main factor limiting the power of current quantum computers is quantum volume, a measure of the maximum number of logic gates that can be contained in the quantum circuit representing an algorithm that runs correctly on the computer. The quantum volume of a computer depends on the error rates of its qubits and the error rates of its logic gates (the operations that can be performed on those qubits). With current technology (we are in the NISQ era, for example), the quantum volume of a computer depends on the error rates of its qubits and the error rates of its logic gates (the operations that can be performed on those qubits). *Noisy Intermediate-Scale Quantum era*), the quantum volume is very small; the current record (April 2024) is held by the 20-qubit H1-1 computer from the company Quantinuum, whose quantum volume reaches one mega (2^{20}), thanks to the use of binary logic gates with a fidelity of 99.914(3) % (the first time that three nines have been achieved). I am not aware of Shor’s algorithm having been run on such a computer, but it will only be able to factor a very small number.

It is perhaps worth noting that the largest number ever factored using Shor’s algorithm on a quantum computer was 21 = 7 × 3 in 2012. In 2019, an attempt was made to factor the number 35 = 7 × 5 using this algorithm on an IBM Q System One quantum computer (20 qubits), but this was impossible because it did not have enough quantum volume; the consolation prize was to factor the number 35 using a hybrid algorithm based on Shor’s. Using a hybrid algorithm, in 2022 a 48-bit number was successfully factored using 10 qubits (LCMF, 27 Dec 2022). Will Regev’s algorithm allow numbers larger than 21 to be factored on IBM or Quantinuum quantum computers? Regev himself says he does not know. I am optimistic and think so, so I hope that this milestone will be published later this year. Unfortunately, I don’t expect that numbers much larger than 35 can be factored. A number like RSA-2048 is still an “infinite” number for current NISQ computers.

The new algorithms have been published in Oded Regev, “An Efficient Quantum Factoring Algorithm,” arXiv:2308.06572 [quant-ph] (12 Aug 2023), doi: https://doi.org/10.48550/arXiv.2308.06572; Seyoon Ragavan, Vinod Vaikuntanathan, «Space-Efficient and Noise-Robust Quantum Factoring,» arXiv:2310.00899 [quant-ph] (02 Oct 2023), doi: https://doi.org/10.48550/arXiv.2310.00899. Más información divulgativa en Ben Brubaker, «Thirty Years Later, a Speed Boost for Quantum Factoring,» Quanta Magazine, 17 Oct 2023. También cito Craig Gidney, Martin Ekerå, «How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,» Quantum 5: 433 (2021), doi: https://doi.org/10.22331/q-2021-04-15-433, arXiv:1905.09749 [quant-ph] (23 May 2019); Cédric Pilatte, «Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms,» arXiv:2404.16450 [math.NT] (25 Apr 2024), doi: https://doi.org/10.48550/arXiv.2404.16450; Martin Ekerå, Joel Gärtner, «Extending Regev’s factoring algorithm to compute discrete logarithms,» PQCrypto 2024, Lecture Notes in Computer Science 14772: 211-242 (2024), doi: https://doi.org/10.1007/978-3-031-62746-0_10, arXiv:2311.05545 [cs.CR] (09 Nov 2023); ; .

In essence, Shor’s algorithm for factoring the number *N* part of a number *a* N that is co-cousin with *N* and look for the period *r* > 0 such that *a ^{r}* = 1 mod

*N*using the discrete quantum Fourier transform (QFT); once the period is obtained

*r*A classical polynomial-time post-processing is used to determine a prime factor of N. The key to the algorithm is the calculation of modulo products

*N*(to calculate

*a*mod

^{r}*N*) using unitary transformations. In a sense Shor’s algorithm is one-dimensional (as this figure attempts to illustrate).

*Quanta Magazine*). Regev’s idea is to use a multidimensional version of this algorithm (as the figure that opens this piece tries to illustrate, which I recommend you look at again). Instead of taking a number

*a*are taken

*d*> 0 numbers

*b*

_{1}…,

*b*and is defined

_{d}*a*=

_{i}*b*

_{i}^{2}; in two grids in

*d*dimensions