Hacker News Reader

Comment by krastanov | Hacker News Reader

> Isn’t this exactly the kind of stuff that annealing can be applied to?

Yes, but there is just no evidence that annealers are better at this kind of stuff than classical algorithms. They are "just" an interesting analog computer that can be applied to this type of problems, without a reason to believe that they will be drastically better (in terms of complexity theory).

On the other hand, circuit-based digital quantum computers and error-corrected adiabatic quantum computers (which are similar but sufficiently different from annealers) can run algorithms that are better than all known classical algorithms at this kind of stuff (modulo the fact that such computers do not exist yet).

View on HN

The analog computer is a quantum system (of atoms for example), and your argument rests in that the complexity of simulating a system of atoms is not high and that nature (i.e. the "analog computer") isn't performing something better from a complexity standpoint.

While I agree that there are pretty efficient algorithms to simulate systems of atoms behaving like Newtonian bodies (like molecular dynamics) it quickly falls apart when you need to include more "quantum like" effects.

The digital quantum computer is itself built out of atoms, so if you could simulate an analog computer (which derives its properties from QM) efficiently, you could then also simulate the digital quantum computer efficiently.

I guess it's a question of semantics - like what properties of nature are an "analog computer" allowed to tap. My point is, I think, that you kind of downplay the capabilities of what an analog computer is capable of by saying it's "just" an analog computer. But any small molecule whizzing around is in some sense a very difficult to simulate analog computer from another point of view.

> your argument rests in that the complexity of simulating a system of atoms is not high and that nature ...

No, that is not what I am going for. I completely agree with the rest of your post, given the premise you are taking.

All I am saying is that, while analog computers are cool and frequently "better" in various ways than digital computers (and it does not matter whether we are talking about quantum or classical ones), analog computers inherently can not scale. Without error-correction codes there is always a limit of size at which noise destroys the result of your computation and error-correction codes exist only for digital quantum and classical computers, not for analog quantum or classical computers.

That is why we use scale models of rivers and gulfs less and less. Even wind-tunels, the last analog computers still in use, are fading in utility.

By the way, in the abstract sense of computational complexity (in the absence of noise and in the presence of infinitely precise measurements), "scalable" classical and quantum analog computers are equally powerful and are both more powerful than "scalable" classical and quantum digital computers. They just can not exist in principle (while "scalable" quantum digital computers are only "difficult", not "in-principle impossible").

Adiabatic quantum computers (the error-corrected version of quantum annealers) on the other hand are a very neat "analog-looking but actually digital" type of computers that are equally powerful to the gate-based model of quantum computers.

And modulo the fact that we don’t even know that we can build ones that are actually faster than classical computers (at meaningful qubit sizes).

That is true -- all we can show is sustained exponential improvement in figures of merit like qubit lifetime and coherence, scalability, gate fidelity over the span of 25 years. As long as this exponential pace of improvement does not stop (we are far from fundamental limits) we should be able to build these machines.

Then there is the question of what they can be used for. Their applicability probably will remain niche, as only very special problems are solvable better on a quantum computer than on a classical one.

Reply on news.ycombinator.com