Hacker News new | past | comments | ask | show | jobs | submit login
A low-resource quantum factoring algorithm [pdf] (iacr.org)
45 points by sigil on April 29, 2017 | hide | past | favorite | 3 comments

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? :)

Well, 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.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact