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?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Hi wang1908! Welcome to QCSE! Your question seems similar to: How many logical qubits are needed to run Shor's algorithm efficiently on large integers ($n > 2^{1024}$)?. Can you consider revising your question in light of the other? $\endgroup$– Mark SpinelliApr 9, 2019 at 14:49
-
$\begingroup$ Mark S, I just rephrased the question in hope to get some more insights. The link answered half of the question. $\endgroup$– wang1908Apr 9, 2019 at 16:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Apr 9, 2019 at 18:09
-
1$\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$ Sep 15 at 15:08
$\begingroup$
$\endgroup$
Community Wiki
O. Regev has another algorithm posted on the arxiv here.
I quote the abstract directly:
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.
Aaronson briefly blogged about this, with some further clarifications from @CraigGidney.