3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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