8 ms·

I found this remark from the linked pdf[1] very interesting: "...it has also been shown that for the class of problems used in initial benchmarks,the performan

I found this remark from the linked pdf[1] very interesting: "...it has also been shown that for the class of problems used in initial benchmarks,the performance of the devices also correlates well with a classical(meanfield) approximation of quantum annealing [4],which raises questions about whether the devices can outperform classical optimizers." In other words, if you ran a simulation of this device on a normal computer and gave it the same problem to solve, you will get basically the same efficiency. [1] http://www.scottaaronson.com/troyer.pdf http://www.scottaaronson.com/troyer.pdf

SilasX 11y ago
So ... more proof that D-Wave is fluff.
- oh_sigh 11y ago
  Or proof that classical computers and algorithms have decades of optimizations behind them and quantum computers and algorithms only have years.
  - colanderman 11y ago
    They're measuring asymptotic performance (scale), not wall clock time, and testing quantum algorithms with known better asymptotic performance than the equivalent classical ones. They could run the classical algorithms a factor of 1,000,000× slower and reach the same conclusion, that the D-Wave's quantum annealing process is asymptotically equivalent (scales equivalently) to classical algorithms.
    - oh_sigh 11y ago
      I understand the difference between the two(yay, CS degree! and/or wikipedia), but from what I could read of the two posts, there is no indication that the asymptotic performance was being measured to any significant extent.
  - letstryagain 11y ago
    That should not matter. Quantum computers promise to do things that classical computers will never be able to do. A 'proper' QC with on the order of a few thousand qubits can perform calculations that even a known-universe-sized classical computer will find intractable. Optimisation quickly becomes irrelevant when you scale these problems just a little bit more.
    - dvanduzer 11y ago
      I do not believe there are any problems known to be solvable by QC, and unsolvable by classical computers. edit: I was trying to be polite, but Scott Aaronson has spilled quite a lot of blog ink denouncing remarks like the parent post as utter nonsense.
      - deleted 11y ago
        [deleted]
      - letstryagain 11y ago
        You might have misunderstood my comment (or Scott's writings?) Classical computers are limited by what they can compute because the universe has limits. A 10,000 qubit quantum computer can factor fairly large numbers. 10,000 qubits is pretty small, one day hopefully it will fit inside a small room. To factor those same numbers using a classical computer you'd have to make a computer the size of the entire known universe and run that computer until the heat death of the universe. Obviously this is not possible, even in principal. Theoretically any QC computation can be simulated by a classical computer but in our limited universe you quickly run into the wall where the classical computer just becomes too big (bigger than the entire universe) and too slow (slower than the life of the universe).
        dvanduzer 11y ago
        I definitely reread your comment several times and kept stewing on the word "intractable" since I'd seen it used somewhere else to talk about problems in NP-Complete. I assumed if I was misinterpreting what you were saying, it would hinge on that word. Aside from factoring, what kinds of things do we think will meaningfully change if we get general QC? Cryptographers are already preparing for the post-quantum world. Who else needs to be preparing? Everything I think I understand about QC suggests that a practical breakthrough will not cause any changes in society, other than the abandonment of RSA. Am I missing something?
tormeh 11y ago
So there are huge algorithmic speedups just sitting there for the taking? And no one has used these? Color me skeptical.
- erikpukinskis 11y ago
  No, they're saying it's not actually faster. The purpose of this research is to experiment with problems and push the hardware to discover limitations that can inform their design of the next generation of hardware. Quantum computing is a lot like fusion research. Nothing we know how to build will break even but we still need to build something so we can learn how to build something that could break even.
  - fleitz 11y ago
    Why? We have plenty of better energy technologies than what we have, but we don't implement those, so why bother building an even better technology that we also likely won't build. It's like the dev team that won't refactor but thinks its new design will be perfect and also not need refactoring. The new project invariably needs refactoring which they don't do, leading to another ground up rewrite. I'm pretty sure by the year 2200, we'll have a coffee cup sized zero point energy device but still get our power from coal.
    - Lazare 11y ago
      > We have plenty of better energy technologies than what we have, but we don't implement those, Well, why don't you do it then? The potential profits are absurd; don't you want to be the world's first trillionaire? > I'm pretty sure by the year 2200, we'll have a coffee cup sized zero point energy device but still get our power from coal. You're suggesting that people will choose to consume expense goods and services over otherwise identical cheaper goods and services? This does not seem to mesh well with observed human behaviour.
      - pfisch 11y ago
        I mean I don't really agree with fleitz necessarily, but any power source can be very cheap/free at the consumer/market level when the government is subsidizing all the costs. The government is not really a rational actor in economic markets and is often guided by other factors like popular vote, corruption, etc. It is hard to explain why we don't use more nuclear power from an economic standpoint, but it is easy to understand how politicians and lobbyists have capitalized on fear mongering to create our current energy markets.
BrainInAJar 11y ago
Not only that, the classical simulation of the machine is faster than the real thing, because the simulation simulates an ideal error-free machine, which is not the case
mtgx 11y ago
The question is can they still say that when D-Wave reaches say 4,000 qubits? What I'm asking is will classical optimizers and classical computers always be able to be "roughly as fast" as D-Wave for that work, or will D-Wave inevitably surpass them by orders of magnitude in future iterations?
- johncolanduoni 11y ago
  That is the central open question. That's what Scott means when he talks about asymptotics, and the conclusion of the Google paper is that we have probable evidence that with enough qubits and a big enough problem it will be faster for a very specific problem compared to a non-optimal classical algorithm (we have ones that are for sure better). This probably sounds like a somewhat useless result (quantum computer beats B-team classical algorithm), but it is in fact interesting because D-Wave's computers are designed to perform quantum annealing and they are comparing it to simulated annealing (the somewhat analogous classical algorithm). However they only found evidence of a constant (i.e. one that 4000 qubits wouldn't help with) speed up (though a large one) compared to a somewhat better algorithm (Quantum Monte Carlo, which is ironically not a quantum algorithm), and they still can't beat an even better classical algorithm (Selby's) at all, even in a way that won't scale. Scott's central thesis is that although it is possible there could be a turning point past 2000 qubits where the D-Wave will beat our best classical alternative, none of the data collected so far suggests that. So it's possible that a 4000 qubit D-Wave machine will exhibit this trend, but there is no evidence of it (yet) from examining a 2000 qubit machine. Scott's central gripe with D-Wave's approach is that they don't have any even pie-in-the-sky theoretical reason to expect this to happen, and scaling up quantum computers without breaking the entire process is much harder than for classical computers so making them even bigger doesn't seem like a solution. My personal frustration with D-Wave's marketing is that the fact that their computers are super specialized often gets lost; these computers fail the equivalent quantum notion of a complete set of digital logic gates.
  - jacquesm 11y ago
    But that's the wrong comparison. The right one would be a special purpose FPGA or ASIC based computer built specifically for the simulated annealing problem.

SilasX 11y ago

So ... more proof that D-Wave is fluff.

oh_sigh 11y ago
Or proof that classical computers and algorithms have decades of optimizations behind them and quantum computers and algorithms only have years.
- colanderman 11y ago
  They're measuring asymptotic performance (scale), not wall clock time, and testing quantum algorithms with known better asymptotic performance than the equivalent classical ones. They could run the classical algorithms a factor of 1,000,000× slower and reach the same conclusion, that the D-Wave's quantum annealing process is asymptotically equivalent (scales equivalently) to classical algorithms.
  - oh_sigh 11y ago
    I understand the difference between the two(yay, CS degree! and/or wikipedia), but from what I could read of the two posts, there is no indication that the asymptotic performance was being measured to any significant extent.
- letstryagain 11y ago
  That should not matter. Quantum computers promise to do things that classical computers will never be able to do. A 'proper' QC with on the order of a few thousand qubits can perform calculations that even a known-universe-sized classical computer will find intractable. Optimisation quickly becomes irrelevant when you scale these problems just a little bit more.
  - dvanduzer 11y ago
    I do not believe there are any problems known to be solvable by QC, and unsolvable by classical computers. edit: I was trying to be polite, but Scott Aaronson has spilled quite a lot of blog ink denouncing remarks like the parent post as utter nonsense.
    - deleted 11y ago
      [deleted]
    - letstryagain 11y ago
      You might have misunderstood my comment (or Scott's writings?) Classical computers are limited by what they can compute because the universe has limits. A 10,000 qubit quantum computer can factor fairly large numbers. 10,000 qubits is pretty small, one day hopefully it will fit inside a small room. To factor those same numbers using a classical computer you'd have to make a computer the size of the entire known universe and run that computer until the heat death of the universe. Obviously this is not possible, even in principal. Theoretically any QC computation can be simulated by a classical computer but in our limited universe you quickly run into the wall where the classical computer just becomes too big (bigger than the entire universe) and too slow (slower than the life of the universe).
      - dvanduzer 11y ago
        I definitely reread your comment several times and kept stewing on the word "intractable" since I'd seen it used somewhere else to talk about problems in NP-Complete. I assumed if I was misinterpreting what you were saying, it would hinge on that word. Aside from factoring, what kinds of things do we think will meaningfully change if we get general QC? Cryptographers are already preparing for the post-quantum world. Who else needs to be preparing? Everything I think I understand about QC suggests that a practical breakthrough will not cause any changes in society, other than the abandonment of RSA. Am I missing something?

tormeh 11y ago

So there are huge algorithmic speedups just sitting there for the taking? And no one has used these? Color me skeptical.

erikpukinskis 11y ago
No, they're saying it's not actually faster. The purpose of this research is to experiment with problems and push the hardware to discover limitations that can inform their design of the next generation of hardware. Quantum computing is a lot like fusion research. Nothing we know how to build will break even but we still need to build something so we can learn how to build something that could break even.
- fleitz 11y ago
  Why? We have plenty of better energy technologies than what we have, but we don't implement those, so why bother building an even better technology that we also likely won't build. It's like the dev team that won't refactor but thinks its new design will be perfect and also not need refactoring. The new project invariably needs refactoring which they don't do, leading to another ground up rewrite. I'm pretty sure by the year 2200, we'll have a coffee cup sized zero point energy device but still get our power from coal.
  - Lazare 11y ago
    > We have plenty of better energy technologies than what we have, but we don't implement those, Well, why don't you do it then? The potential profits are absurd; don't you want to be the world's first trillionaire? > I'm pretty sure by the year 2200, we'll have a coffee cup sized zero point energy device but still get our power from coal. You're suggesting that people will choose to consume expense goods and services over otherwise identical cheaper goods and services? This does not seem to mesh well with observed human behaviour.
    - pfisch 11y ago
      I mean I don't really agree with fleitz necessarily, but any power source can be very cheap/free at the consumer/market level when the government is subsidizing all the costs. The government is not really a rational actor in economic markets and is often guided by other factors like popular vote, corruption, etc. It is hard to explain why we don't use more nuclear power from an economic standpoint, but it is easy to understand how politicians and lobbyists have capitalized on fear mongering to create our current energy markets.

BrainInAJar 11y ago

Not only that, the classical simulation of the machine is faster than the real thing, because the simulation simulates an ideal error-free machine, which is not the case

mtgx 11y ago

The question is can they still say that when D-Wave reaches say 4,000 qubits? What I'm asking is will classical optimizers and classical computers always be able to be "roughly as fast" as D-Wave for that work, or will D-Wave inevitably surpass them by orders of magnitude in future iterations?

johncolanduoni 11y ago
That is the central open question. That's what Scott means when he talks about asymptotics, and the conclusion of the Google paper is that we have probable evidence that with enough qubits and a big enough problem it will be faster for a very specific problem compared to a non-optimal classical algorithm (we have ones that are for sure better). This probably sounds like a somewhat useless result (quantum computer beats B-team classical algorithm), but it is in fact interesting because D-Wave's computers are designed to perform quantum annealing and they are comparing it to simulated annealing (the somewhat analogous classical algorithm). However they only found evidence of a constant (i.e. one that 4000 qubits wouldn't help with) speed up (though a large one) compared to a somewhat better algorithm (Quantum Monte Carlo, which is ironically not a quantum algorithm), and they still can't beat an even better classical algorithm (Selby's) at all, even in a way that won't scale. Scott's central thesis is that although it is possible there could be a turning point past 2000 qubits where the D-Wave will beat our best classical alternative, none of the data collected so far suggests that. So it's possible that a 4000 qubit D-Wave machine will exhibit this trend, but there is no evidence of it (yet) from examining a 2000 qubit machine. Scott's central gripe with D-Wave's approach is that they don't have any even pie-in-the-sky theoretical reason to expect this to happen, and scaling up quantum computers without breaking the entire process is much harder than for classical computers so making them even bigger doesn't seem like a solution. My personal frustration with D-Wave's marketing is that the fact that their computers are super specialized often gets lost; these computers fail the equivalent quantum notion of a complete set of digital logic gates.
- jacquesm 11y ago
  But that's the wrong comparison. The right one would be a special purpose FPGA or ASIC based computer built specifically for the simulated annealing problem.