4 ms·

With the D-Wave flavor of quantum computers, it is like solving every issue using a traveling salesman algorithm. It can be done, but you aren't using a genera

by IncRnd 6y ago

With the D-Wave flavor of quantum computers, it is like solving every issue using a traveling salesman algorithm. It can be done, but you aren't using a general purpose quantum computer to do so.

21eleven 6y ago
So it is more efficient at exploring the solution territory of traveling salesman type problems than classical computers?
- deleted 6y ago
  [deleted]
- reikonomusha 6y ago
  It has not been shown that it solves QUBO/NP hard problems any faster asymptotically.
- pyk 6y ago
  I would safely say that it does not solve TSP faster than the best TSP code available - Concorde. More info here, and note there is an iOS app too (Concorde TSP on the App Store) that you can play with that solves TSP to optimality: http://www.math.uwaterloo.ca/tsp/concorde.html http://www.math.uwaterloo.ca/tsp/concorde.html
reikonomusha 6y ago
More specifically, just to elaborate on your point, it purports to solve certain “quadratic unconstrained binary optimization” (QUBO) problems [1]. It’s not a “programmable computer” in the traditional sense we think. It’s more “tune a bunch of knobs and press ‘go’.” Quantum computers made by Rigetti, Google, and IBM are all programmable with some manner of programming language, and not coincidentally, the number of qubits is two orders of magnitude fewer. [1] https://en.m.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization https://en.m.wikipedia.org/wiki/Quadratic_unconstrained_bina...
- IncRnd 6y ago
  Yes. That is my point. I meant that it is not a general purpose quantum computer. There is no general purpose quantum computer that has 5,000 qubits. The D-Wave machines use quantum annealing. My reference was to the probabalistic gpc algorithm for solving TSP using annealing.
  - core-questions 6y ago
    It performs computations; it does so using quantum effects; therefore it is a quantum computer. Every single thread that discusses D-Wave ends up with this same talking point about "universal" quantum computing. Yes, it's not yet another vaporware gate-model QC toy like Rigetti or Google have; it's a very specific sort of accelerator, somewhat akin to a GPU or a vector processor - not in terms of what it does, but in terms of requiring specific programming to make it useful. It's simply a vastly different architecture than gate-model QC: in many ways, it's a descendant of the analogue computers of the 60s and 70s. The key differentiator here is that they've been able to scale their model from a couple hundred qubits to >5000, in production for anyone to use online. If you're a mathematician and you can actually model your problems this way, they have a nice SDK and it's very usable. There's every reason to assume that they'll have 10k qubits with even more connectivity in a few years, and they have this hybrid solver thing which takes in 10k+ variables already, so it's clear they believe in the problem model itself. I just wish I could make it do more - my layman's interest has only taken me far enough to get a basic idea of what's going on for curiosity's sake. I think you need to be a mathematician in order to be able to do anything serious with it, right now.
    - IncRnd 6y ago
      D-Wave doesn't make a general purpose quantum computer. The sense of that statement is that it cannot run Shor's algorithm, though it can factor integers, for example.
      - core-questions 6y ago
        Are you a bot? I'm literally responding to this exact criticism. Yes, it's not a general purpose QC. Does that somehow make it (a real product you can use) less useful than a hypothetical QC from some other company that doesn't actually exist yet? This is like complaining about GPUs not being general purpose. Sure, that's a criticism, but it's not actually that valid.

by IncRnd 6y ago

With the D-Wave flavor of quantum computers, it is like solving every issue using a traveling salesman algorithm. It can be done, but you aren't using a general purpose quantum computer to do so.

21eleven 6y ago

So it is more efficient at exploring the solution territory of traveling salesman type problems than classical computers?

deleted 6y ago
[deleted]
reikonomusha 6y ago
It has not been shown that it solves QUBO/NP hard problems any faster asymptotically.
pyk 6y ago
I would safely say that it does not solve TSP faster than the best TSP code available - Concorde. More info here, and note there is an iOS app too (Concorde TSP on the App Store) that you can play with that solves TSP to optimality: http://www.math.uwaterloo.ca/tsp/concorde.html http://www.math.uwaterloo.ca/tsp/concorde.html

reikonomusha 6y ago

More specifically, just to elaborate on your point, it purports to solve certain “quadratic unconstrained binary optimization” (QUBO) problems [1]. It’s not a “programmable computer” in the traditional sense we think. It’s more “tune a bunch of knobs and press ‘go’.” Quantum computers made by Rigetti, Google, and IBM are all programmable with some manner of programming language, and not coincidentally, the number of qubits is two orders of magnitude fewer. [1] https://en.m.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization https://en.m.wikipedia.org/wiki/Quadratic_unconstrained_bina...

IncRnd 6y ago
Yes. That is my point. I meant that it is not a general purpose quantum computer. There is no general purpose quantum computer that has 5,000 qubits. The D-Wave machines use quantum annealing. My reference was to the probabalistic gpc algorithm for solving TSP using annealing.
- core-questions 6y ago
  It performs computations; it does so using quantum effects; therefore it is a quantum computer. Every single thread that discusses D-Wave ends up with this same talking point about "universal" quantum computing. Yes, it's not yet another vaporware gate-model QC toy like Rigetti or Google have; it's a very specific sort of accelerator, somewhat akin to a GPU or a vector processor - not in terms of what it does, but in terms of requiring specific programming to make it useful. It's simply a vastly different architecture than gate-model QC: in many ways, it's a descendant of the analogue computers of the 60s and 70s. The key differentiator here is that they've been able to scale their model from a couple hundred qubits to >5000, in production for anyone to use online. If you're a mathematician and you can actually model your problems this way, they have a nice SDK and it's very usable. There's every reason to assume that they'll have 10k qubits with even more connectivity in a few years, and they have this hybrid solver thing which takes in 10k+ variables already, so it's clear they believe in the problem model itself. I just wish I could make it do more - my layman's interest has only taken me far enough to get a basic idea of what's going on for curiosity's sake. I think you need to be a mathematician in order to be able to do anything serious with it, right now.
  - IncRnd 6y ago
    D-Wave doesn't make a general purpose quantum computer. The sense of that statement is that it cannot run Shor's algorithm, though it can factor integers, for example.
    - core-questions 6y ago
      Are you a bot? I'm literally responding to this exact criticism. Yes, it's not a general purpose QC. Does that somehow make it (a real product you can use) less useful than a hypothetical QC from some other company that doesn't actually exist yet? This is like complaining about GPUs not being general purpose. Sure, that's a criticism, but it's not actually that valid.