Thirty Years Later, a Speed Boost for Quantum Factoring | Hacker News Reader

Thirty Years Later, a Speed Boost for Quantum Factoring

quantamagazine.org

53 pointsnsoonhui12 comments

Great.

You now only need O(n^1.5)* magic bits instead of O(n^2) magic bits.

* Or O(n) according to other comments

TLDR; They have knocked the Shors algorithm complexity to n^1.5 in time and space. (Correct me if I'm wrong)

N in space. There are two combined results in the article. The first was n^1.5 in space and time, the second reduced that to n in space. The original was n^2 in time and n in space.

What are the constant factors here? Could this be dropped in everywhere they are already using Shor's algorithm and just get a speed up? If so, this results seems incredibly influential.

No one is "already using Shor's algorithm". Wikipedia lists the largest numbers factored using Shor's algorithm on a real quantum computer as follows:

- The number 15 (5*3) was factored in 2001

- The number 21 (7*3) was factored in 2012

- An attempt to factor 35 (5*7) was made in 2019 but they didn't succeed because of accumulation of errors in the quantum computer.

Quantum computers today are very bad, so changing the algorithm probably won't change much.

There is an argument out there that the 15 and 21 factorizations involved built in knowledge of the answer. If you accept that then there has been zero progress demonstrated so far for factoring numbers using quantum effects, not just a ridiculously small amount of progress.

On the positive side, they haven't factored 17 and 19.

Is this a joke? Or...

So, less than one bit of progress per decade? That's not exactly huge progress...

At this rate, just 2510*1.5 years and we will crack all current AES. Hopefully we will be using 512 bit keys by then. 512 bits should be enough for anyone.

Shoes does not attack symmetric ciphers like AES.

Grover’s algorithm applies and will never be used against even AES 128.

You are wrong, but close. They show that you can split up the factoring problem so you may solve sqrt(n) smaller problems, all requiring n^1.5 quantum operations, instead of a single run taking n^2 operations. This reduction can be implemented on a classical computer in polynomial time.

They also require more qubits per run, n^1.5 instead of n but it is unclear to me whether this comes from n*sqrt(n), i.e., sqrt(n) paralel runs on n qubits, or that each run requires n^1.5 qubits. I would expect the first.

So, the quantum part of the algorithm still requires n^2 gates, but the improvement is that it is split up (and non-adaptability). This means that it can be run in parallel, and that the individual runs will have less problems with errors stacking due to circuit depth. Note that the classical overhead for the reduction might be relatively high.

Original paper: https://arxiv.org/pdf/2308.06572.pdf

Reply on news.ycombinator.com