←back to thread

Why haven't quantum computers factored 21 yet?

(algassert.com)
335 points ingve | 2 comments | 31 Aug 25 12:14 UTC | HN request time: 0s | source
Show context
Nevermark ◴[01 Sep 25 07:47 UTC] No.45090491[source]▶
I wonder if the circuit could be modularized into a quantum ALU. Where many of the otherwise identical components in the original layout, couldn't just be arranged as operations time, over a reduced number of distinct components.

Most digital algorithms would explode in terms of hardware needed, for increasing N, if we didn't distribute that computation in time, as well as across elements.

replies(3): >>45090824 #>>45093064 #>>45118736 #
adgjlsfhk1 ◴[01 Sep 25 14:47 UTC] No.45093064[source]▶
unfortunately this is kind of fundamentally impossible. the whole power of quantum computation is that big quantum computers can do computation on a massive state space "for free". that benefit only exists if you have enough qbits to hold the state space.
replies(1): >>45095090 #
1. Nevermark ◴[01 Sep 25 18:06 UTC] No.45095090[source]▶
Holding the state space and iteratively transforming it (in a reversible way, so the state space is preserved), seem like a solution to that.

This would still require more hardware than digital circuits (which can be made reversible for energy efficiency, but that is rarely done).

While still reducing the number of operation components, and reusing them.

replies(1): >>45096297 #
2. adgjlsfhk1 ◴[01 Sep 25 20:22 UTC] No.45096297[source]▶
This is already done. Qbits is the size of the state space and gates is the measure of operations (like flops but quantum operations). https://arxiv.org/pdf/2505.15917 shows a factoring algorithm using 1 million qbits and ~10^10 gates.