Hacker News Reader

Comment by AndrewStephens | Hacker News Reader

In 2001, a pure quantum computer using Shor's algorithm correctly gave the prime factors of 15. In 2012 they managed to find the prime factors of 21. Since then, everyone has given up on the purely quantum approach by using lots of traditional CPU-time to preprocess the input, somewhat defeating the purpose.

Its a shame. I was really looking forward to finding out what the prime factors of 34 are.

View on HN

https://eprint.iacr.org/2015/1018.pdf

"As pointed out in [57], there has never been a genuine implementation of Shor’s algorithm. The only numbers ever to have been factored by that type of algorithm are 15 and 21, and those factorizations used a simplified version of Shor’s algorithm that requires one to know the factorization in advance..."

If you have a clue what these factors are, you can build an implementation of Shor's algorithm for them, I guess.

There was for this year's sigbovik [1]

[1] https://fixupx.com/CraigGidney/status/1907199729362186309

If I understand correctly, they didn't actually find the prime factors, they merely verified them, so it's unfortunately up to you to factor 34. Maybe some time in the future a quantum machine can verify whether you were right.

It's 2 and 17, I asked Claude.

Not sure if it was more wasteful of energy asking Claude or trying to solve it with Quantum.

A twelve year old could do it for 500 kcal of cookies.

I volunteer as a tribute

The twelve year old would probably be too full and tired after eating you to do any math.

Humans are typically paid for their labour after they have performed it.

Reminds me of the Groucho Marx line: "A child of five could understand this. Send someone to fetch a child of five."

At least quantum computers are cool.

We could ask Claude to generate the schematics for a quantum computer that can find the prime factors of 21. Then we get the best of both worlds.

I believe it was both at the same time, until you check the monthly bill at which point you forced one to become more wasteful.

AI can do that now? Looks like I have to upgrade all of my 5-bit SSL keys.

>5-bit SSL keys.

34 requires 6 bits, though

Hence the urgency.

Gemini told me it was -12 and pi.

The infamous 21 (which is half of 42) was my 1st thought when I heard 'unpopular' which is of course a very popular opinion.

Reply on news.ycombinator.com