Regev's factoring algorithm: a multidimensional take on Shor

Short answer: In 2023 Oded Regev described a quantum factoring algorithm that the paper presents as a multidimensional analogue of Shor's algorithm. It factors an n-bit integer by running a quantum circuit of about n to the power 3/2 gates roughly the square root of n times, then doing classical post-processing. It relies on a number-theoretic assumption, and the paper itself says it is not clear whether it leads to improved physical implementations in practice.

What the paper claims

The abstract says n-bit integers can be factorized by independently running a quantum circuit with a gate count of about n^(3/2), up to logarithmic factors, a number of times on the order of the square root of n (the arXiv version gives the count as the square root of n plus 4), and then using polynomial-time classical post-processing. The method uses a lattice reduction algorithm in the post-processing step.

In the version on arXiv, the author describes the algorithm as something that can be thought of as a multidimensional analogue of Shor's algorithm. Where Shor's algorithm works with one number, this approach works with several small integers at once, which the paper builds into a lattice.

What it assumes

The paper says the correctness of the algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. The ACM journal version describes this as relying on a certain number-theoretic conjecture. In plain terms, the algorithm is proven under an assumption, not unconditionally.

What it does and does not change

The abstract is direct about the practical question: it is currently not clear if the algorithm can lead to improved physical implementations in practice. A smaller circuit that has to be run more times is a trade-off, and whether that trade-off helps on real hardware depends on engineering details the paper does not claim to settle.

Nothing in the paper says that any RSA key has been or can currently be factored. Resource estimates for breaking RSA-2048 are a separate topic, covered in our article on qubit counts. Migration planning to post-quantum cryptography does not depend on this result.

How the two versions differ

The arXiv listing shows three versions of the paper, posted in August 2023 and January 2024, and the ACM journal version is a further revision. The wording of the headline claim differs slightly between them: an early version states the number of circuit runs as the square root of n plus 4 in the abstract and n plus 4 times the square root of n plus 4 in the introduction, and the journal version states the assumption as a conjecture. If you cite the result, check which version you are quoting.

What this does not tell you

This article summarises the abstract and introduction of one theory paper. We have not verified the proofs, and no implementation is described here. Check the paper and later follow-up work for the current state of the analysis.

FAQ

Who proposed this algorithm?

Oded Regev, in a 2023 paper titled "An Efficient Quantum Factoring Algorithm".

How is it related to Shor's algorithm?

The paper describes it as a multidimensional analogue of Shor's algorithm.

What is the claimed cost?

A quantum circuit with about n^(3/2) gates (up to logarithmic factors), run on the order of the square root of n times, plus polynomial-time classical post-processing.

What does it assume?

A number-theoretic heuristic assumption, described in the journal version as a conjecture.

Does it mean RSA is broken?

No. The paper itself says it is not clear whether the algorithm leads to improved physical implementations in practice.