How many qubits and what is the minimum number of gate operations needed to factor an n-bit integer? Are there any other published algorithms that are simpler or more efficient?


2 Answers 2


Shor's algorithm is based on the gate model of quantum computation. However, there are alternatives to the gate model, such as quantum walks, etc. See all of the answers to this question for a nice summary of the different models of computation.

As to what I believe to be the implicit question "is Shor's the only known quantum factoring algorithm, or are there alternatives that use fewer qubits and/or fewer gate operations?" I refer you to "A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation" (link) by Peng, Liao, Xu, Zhou, Suter, and Du.

The adiabatic factoring algorithm paper notes that factoring can be recast as an optimization problem. More specifically, the adiabatic algorithm notes that in order to factor a number $N=p\times q$, it suffices to find an $(x,y)\in\mathbb{N}^2$ such that $f(x,y)=(N-xy)^2$ obtains a minimum.

The paper describes the preparation of a Hamiltonian whose lowest energy corresponds to this minimum. The first paragraph of the second page of the paper compares the qubit count of the adiabatic algorithm somewhat favorably to that of Shor's.

Because the adiabatic algorithm evolves adiabatically to the ground state, it does not really make sense to talk about the "total number" of gate operations; rather it makes more sense to talk about the length of time the adiabatic evolution takes. As I understand, the runtime of such adiabatic algorithms are notoriously difficult to describe exactly/analytically, or even to a first order, being based on the spectral gap of the problem Hamiltonian. So we may be left with only numerical simulations. That is, unlike counting gates in the gate model, in general it's very difficult (nay undecidable) to know how long the adiabatic evolution takes, but the paper claims that numerical simulations indicate that the running time (evolution time) grows only quadratically with the number of qubits.

Thus, to answer the questions, there are other quantum factoring algorithms that don't require the same repeated squaring/QFT/classical post-processing of Shor's algorithm, and that uses fewer qubits. The runtime may also grow polynomially as in s algorithm, but proving that the runtime is quadratic or even polynomial in the number of qubits (bits of $N$) is difficult.

  • 3
    $\begingroup$ I'm going to channel Scott Aaronson (scottaaronson.blog/?p=6957 scottaaronson.blog/?p=4447). Factoring algorithms based on optimization throw away the useful structure of the problem, so there's no good reason to expect them to work at scale. And there's a nasty tendency for these papers to ignore blatant problems that are going to prevent scaling, such as the number of samples required or the amount of preprocessing required. I don't trust them at all. $\endgroup$ Commented Sep 15, 2023 at 15:08

Community Wiki

Oded Regev has an improved algorithm posted on the arXiv here.

The abstract provides:

We show that n-bit integers can be factorized by independently running a quantum circuit with $O~(n^{3/2})$ gates for $\sqrt n+4$ times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

As explained in this presentation and panel discussion with the Simons institute, Regev's improvement is based on a modification of the repeated-squares portion of the algorithm. Regev uses classical post-processing based on the LLL algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.