Comment by vtomole | Hacker News Reader

Comment by vtomole | Hacker News Reader

Parent Full thread

> It is still open whether we can build quantum computers with sufficiently low noise to run Shor‘s algorithm.

This statement should delimit between theory and experiment.

Theoretically, the question of building a quantum computer with low enough noise to run Shor's has been solved. In fact it was solved by Shor himself in the 1990s: https://arxiv.org/abs/quant-ph/9605011.

Experimentally, we are just getting started with building quantum computers with low enough noise: https://blogs.microsoft.com/blog/2024/04/03/advancing-scienc....

Experimentally, it will always be open whether a quantum computer can run Shor's until it actually run Shor's. The point is that progress in the field has not stagnated since it's founding.

That paper of Shor just shows how a quantum computer with a large number of bad qubits can be the equivalent of a quantum computer with a small number of good qubits.

The paper does not prove anything about the upper limit for the number of bad qubits that are physically realisable.

There are doubts that this upper limit, which is unknown yet, is high enough for most practical applications.

> The paper does not prove anything about the upper limit

Nothing can prove how many qubits can be realizable except trying to realize them. There will never be a theorem that says "The maximum number of qubits that can ever be controlled in a lab is X". That's what experiment is for.

I will say, it's difficult to doubt that the upper limit to the number of qubits we can realize is infinity. We can now trap ~10 million atoms and efficiently control hundreds of them: https://www.nature.com/articles/s41586-023-06927-3. The question is not "Could we ever realize billions of qubits?". It's "When can we realize billions qubits?". The answer could be decades or centuries but as long as people are building these devices, it will happen eventually.

Yeah well you can rephrase my statement to say that the theory underlying quantum computers still hasn’t been validated experimentally, so it’s still open whether it models reality sufficiently well to allow us to run the algorithms it predicts on physical machines.

Reply on news.ycombinator.com