4 ms·
A low-resource quantum factoring algorithm [pdf]
- swordswinger12 9y agoFrom 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.
- cromwellian 9y agoSo 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? :)
- SAI_Peregrinus 9y agoWell, since the difficulty of constructing (general purpose) quantum computers seems to be exponential in the number of bits, waiting for a 4k-bit one is likely the slower option.