Comment by krastanov | Hacker News Reader

Comment by krastanov | Hacker News Reader

Parent Full thread

Two quick points on this:

- D-Wave do not claim to be building a general quantum computer (although they willfully muddy the water on this). Their machines in principle can not run something like Shor's algorithm. It is not clear whether in general they will ever be able to run anything better than a competitive classical computer. They are just interesting analog computers that happen to use some quantum effects (almost incidentally).

- Shor's algorithm can only run on an error-corrected quantum computer. This will most certainly not be the first "engineeringly useful" algorithm to run on a quantum computer. The a more informative milestone would be "can they run error correction over many rounds of computation". All cutsie examples of a quantum computer running Shor's algorithm on numbers like 21 are just cutesie tech demos that have no chance of scaling.

Simulation of quantum systems (drugs, new materials, solar cells, batteries) is a much more plausible near-term application of a quantum computer. If it ever happens it will probably happen many years before Shor's algorithm successfully runs.

> D-Wave do not claim to be building a general quantum computer (although they willfully muddy the water on this)

While currently the machines they are talking about are quantum annealing only, there is some indication they’re working towards a universal QC [1] [2].

> During the Qubits 2021 conference held by D-Wave, it was announced that the company is developing their first universal quantum computers, capable of running Shor's algorithm in addition to other gate-model algorithms such as QAOA and VQE.

As for your other point,

> Simulation of quantum systems (drugs, new materials, solar cells, batteries) is a much more plausible near-term application of a quantum computer. If it ever happens it will probably happen many years before Shor's algorithm successfully runs.

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

[1] https://www.theregister.com/2021/10/05/dwave_quantum_compute...

[2] https://en.wikipedia.org/wiki/Quantum_annealing

[3] https://www.nature.com/articles/d43747-023-00021-3

> 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).

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