[Strilanc]

This was exactly the premise of my sigbovik April Fool's paper in 2025 [1]: for small numbers, Shor's algorithm succeeds quickly when fed random samples. And when your circuit is too long (given the error rate of the quantum computer), the quantum computer imitates a random number generator. So it's trivial to "do the right thing" and succeed for the wrong reason. It's one of the many things that make small factoring/ecdlp cases bad benchmarks for progress in quantum computing.

I warned the project11 people that this would happen. That they'd be awarding the bitcoin to whoever best obfuscated that the quantum computer was not contributing (likely including the submitter fooling themselves). I guess they didn't take it to heart.

[1]: https://sigbovik.org/2025/proceedings.pdf#page=146

[pseudohadamard]

You wrote that? Nice piece of work! Came here to post exactly this, that's the sigbovik paper in practice.

I'm still waiting for the Quantum Bogosort version of this "factorisation". For those not familiar with the algorithm, it relies on the many-worlds interpretation and is:

  Shuffle the list randomly
  If the list is sorted, stop
  If it isn’t sorted, destroy the entire universe

Adaptation of this algorithm to factorisation is left as a homework exercise for the student.

[cwillu]

Minor optimization: it is sufficient to merely destroy the user.