A low-resource quantum factoring algorithm [pdf]

From the abstract: "The new time complexity is asymptotically worse than Shor’s algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner."

This is a nice result that shows how to speed up the best-known classical factorization algorithm using a quantum algorithm for one of the steps. Importantly, it does it using asymptotically fewer qubits than Shor's algorithm requires. However, the overall algorithm in the paper is still subexponential, not polynomial like Shor.

So to factor a 2048-bit number, Shor's algorithm would need about 4000 qubits, and this algorithm would need about 126 qubits (log(2^2048)^(2/3)). I wonder which would finish first: waiting for a 4000-qubit computer, and then factoring in exponentially faster time, or waiting for a 126-bit qubit computer, and then waiting for the sub-exponential algorithm to complete? :)