5 ms·

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

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.

vlovich123 2y ago
> 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_computer/ https://www.theregister.com/2021/10/05/dwave_quantum_compute... [2] https://en.wikipedia.org/wiki/Quantum_annealing https://en.wikipedia.org/wiki/Quantum_annealing [3] https://www.nature.com/articles/d43747-023-00021-3 https://www.nature.com/articles/d43747-023-00021-3
- krastanov 2y ago
  > 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).
  - vlovich123 2y ago
    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).
    - krastanov 2y ago
      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.
  - l33tman 2y ago
    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.

vlovich123 2y ago

> 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_computer/ https://www.theregister.com/2021/10/05/dwave_quantum_compute... [2] https://en.wikipedia.org/wiki/Quantum_annealing https://en.wikipedia.org/wiki/Quantum_annealing [3] https://www.nature.com/articles/d43747-023-00021-3 https://www.nature.com/articles/d43747-023-00021-3

krastanov 2y ago
> 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).
- vlovich123 2y ago
  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).
  - krastanov 2y ago
    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.
- l33tman 2y ago
  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.