3 ms·

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

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.

xxs 1y ago
The infamous 21 (which is half of 42) was my 1st thought when I heard 'unpopular' which is of course a very popular opinion.
JohnKemeny 1y ago
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.
- teekert 1y ago
  It's 2 and 17, I asked Claude.
  - Lionga 1y ago
    Not sure if it was more wasteful of energy asking Claude or trying to solve it with Quantum.
    - solardev 1y ago
      A twelve year old could do it for 500 kcal of cookies.
      - tomashubelbauer 1y ago
        I volunteer as a tribute
        solardev 1y ago
        The twelve year old would probably be too full and tired after eating you to do any math.
        dontlaugh 1y ago
        Humans are typically paid for their labour after they have performed it.
      - pfdietz 1y ago
        Reminds me of the Groucho Marx line: "A child of five could understand this. Send someone to fetch a child of five."
    - rbanffy 1y ago
      At least quantum computers are cool.
    - RHSeeger 1y ago
      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.
    - _heimdall 1y ago
      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.
  - AndrewStephens 1y ago
    AI can do that now? Looks like I have to upgrade all of my 5-bit SSL keys.
    - xxs 1y ago
      >5-bit SSL keys. 34 requires 6 bits, though
      - Bootvis 1y ago
        Hence the urgency.
  - dreamcompiler 1y ago
    Gemini told me it was -12 and pi.
thesz 1y ago
https://eprint.iacr.org/2015/1018.pdf 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.
- EvgeniyZh 1y ago
  There was for this year's sigbovik [1] [1] https://fixupx.com/CraigGidney/status/1907199729362186309 https://fixupx.com/CraigGidney/status/1907199729362186309

xxs 1y ago

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

JohnKemeny 1y ago

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.

teekert 1y ago
It's 2 and 17, I asked Claude.
- Lionga 1y ago
  Not sure if it was more wasteful of energy asking Claude or trying to solve it with Quantum.
  - solardev 1y ago
    A twelve year old could do it for 500 kcal of cookies.
    - tomashubelbauer 1y ago
      I volunteer as a tribute
      - solardev 1y ago
        The twelve year old would probably be too full and tired after eating you to do any math.
        dontlaugh 1y ago
        Humans are typically paid for their labour after they have performed it.
    - pfdietz 1y ago
      Reminds me of the Groucho Marx line: "A child of five could understand this. Send someone to fetch a child of five."
  - rbanffy 1y ago
    At least quantum computers are cool.
  - RHSeeger 1y ago
    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.
  - _heimdall 1y ago
    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.
- AndrewStephens 1y ago
  AI can do that now? Looks like I have to upgrade all of my 5-bit SSL keys.
  - xxs 1y ago
    >5-bit SSL keys. 34 requires 6 bits, though
    - Bootvis 1y ago
      Hence the urgency.
- dreamcompiler 1y ago
  Gemini told me it was -12 and pi.

thesz 1y ago

https://eprint.iacr.org/2015/1018.pdf 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.

EvgeniyZh 1y ago
There was for this year's sigbovik [1] [1] https://fixupx.com/CraigGidney/status/1907199729362186309 https://fixupx.com/CraigGidney/status/1907199729362186309