The title of the article "Performance of quantum computer no better than ordinary PC" is just flat out wrong. The real issue that physicists are concerned about is whether the D-wave machine is a quantum computer or not. The issue is not whether quantum computers are "better" than classical ones.
Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases. This has been mathematically proven. (EDIT: No it hasn't apparently. See Michael Nielsen's response below.)
Your first paragraph is quite right. But the second paragraph is wrong: for (non-oracle) problems quantum computers are merely suspected to be faster in principle than conventional classical computers. It's never been proven.
I guess I'm confused then. I thought that quantum algorithms had been proven to be faster than the best known classical algorithms (for instance, Shor's factorization), assuming the correctness and completeness of the postulates of QM. In other words, the order of the algorithm is derivable from the postulates. Is that not the case?
I think there's a few people (t'Hooft if I remember correctly?) that believe a quantum computer will never be able to experimentally demonstrate this speed-up because some aspect of quantum mechanics is incomplete/incorrect.
Shor's algorithm is exponentially faster than the best existing classical algorithm for factoring. But that doesn't mean there's not an exponentially faster classical algorithm which would be comparable in speed to Shor's algorithm. Some noted experts believe this is possible, and even likely. Richard Lipton believes it, and claims that Peter Sarnak does too:
Yes, 't Hooft and others, including Leonid Levin and Oded Goldreich, believe that quantum computers won't function because of quantum mechanics breaking down. See, e.g.:
Aren't algorithms like Shor's essentially faster than others in their respected categories due to parallelization?
I.e. isn't quantum superposition just a form of parallelization? if the quantum step in Shor's algorithm is replaced with a classical step executed in parallel in many cpus, then the speed up would be of the same order of magnitude as when using a quantum step.
Not really, if that was the case, quantum computers really would be faster than classical computers. A qubit is basically a normal bit, with probability a that it's in the 0 state, and b that it's in the 1 state, with a^2 + b^2 = 1. If you do some clever maths, you can get these probabilities to cancel out, and give you something that will collapse to the proper state when read.
That's right. The search result, however, assumes the only way of accessing the database is through a black box oracle. That's why I wrote "non-oracle" in my previous comment. It's called an oracle because the internals of the black box are assumed to be unknown. That assumption is necessary in order to prove that classical computers need ~ N operations. If you know something about the internals of the oracle, then it may well be possible to exploit what you know to search faster.
The quantum search algorithm is very interesting. However, most people in the field would, I think, agree that a non-oracle separation between quantum and classical would be vastly more interesting. Oracle results feel a little too close to cheating.
There is, incidentally, a nice paper showing that for computing total Boolean functions the quantum oracle model can be no more than polynomially faster than a classical model. This means there can be no exponential speedup for such functions, which is a real pity.
Except no one, ever, would take "dog bites man" as "one dog bit all of mankind". The title is misleading and, at least one person (myself), took it to mean "quantum computing in general".
I think you misread "quantum computer" as "quantum computers." The headline is very clearly talking about a single specific computer that is marketed as a "quantum computer."
It's just a slight grammatical ambiguity in the title, worsened by the "headline grammar" and the fact that it's a newspaper with a general audience. The headline is intended to be interpreted as "the performance of a particular computer that is marketed as a quantum computer is no better than the performance of an ordinary PC."
But it's pretty easy to quickly read the headline and interpret it as "the performance of ideal quantum computers is no better than the performance of ordinary PCs."
> Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases.
I'm not sure about this part either. Some smart CS guys apparently think that quantum computing isn't even possible. Leonid Levin (yes, of the Cook-Levin theorem seems to be one of them: http://www.cs.bu.edu/fac/lnd/expo/qc.htm.
These machines are testing a completely new computing concept. We're trying to learn how they work so that we can apply that to building machines that can actually outperform traditional computers, and once that's achieved then the potential benefit will be enormous.
Maybe new materials need to be developed to see the full potential of these computers, lots of research needs to be done. Why are all of these articles so pessimistic?
NASA, Lockheed, and Google purchasing these multi-million dollar machines should indicate that there is at-least some potential and value in the D-Wave computers, even if in the end they just learn what D-Wave did wrong.
No, we don't have a perfect understanding of what's going on.
The qubit processor is like an intermediate step, instead of a traditional processor, the grunt of the work of special problems is handled by the qubit chip.
The data is put in and the results are as expected, but they are not as fast as modern computers, so now the challenge is figuring out if different types of calculations can increase that performance or what can be done to improve the chip or other methods.
The machine itself seems so simple though from a visible hardware perspective, most of the D-Wave Two is just to keep the main chip cool and shielded.
It's just experimenting right now. The internet was probably dismissed by many because of it's enormous expense to implement, but the value could be envisioned by many and it paid off.
There is potential for future versions of these quantum computers to be able to solve problems that massive amounts of supercomputers would have trouble solving, and the energy usage is enormously less (same for a small calculation as a huge calculation).
Encryption is one thing that could be hurt by this technology. Instead of millions of years to crack encryption it might be solvable instantly. That's all just what I remember reading about the subject, there's plenty of information out there that's probably more reliable that my babble.
So negative because there's still a non-zero probability that its not going to work at all, ever. That there's something about quantum computing we've figured out wrong, and no benefit is possible.
They're also negative because no one has actually proved that the D-Wave is, in fact, doing any actual quantum computing. That's been the issue all along with D-Wave: no one can prove that it's really doing anything with those qbits.
They're just getting started, this field is very new, very difficult, and there are a lot of very smart people trying to answer the what/how/why/where/when of "quantum" computers.
The hardware outperforms off-the-shelf solvers by a large margin
"In an early test we dialed up random instances and pitted the machine against popular of-the-shelf solvers -- Tabu Search, Akmaxsat and CPLEX. At 509 qubits, the machine is about 35,500 times (!) faster than the best of these solvers. (You may have heard about a 3,600-fold speedup earlier, but that was on an older chip with only 439 qubits." [1]
Yeah, and I've never seen anyone outside D-Wave show these types of speedups. Last article I read, in fact, was struggling really hard to even show that D-Wave was the same speed as traditional algos.
My point is that even if we can't prove the D-Wave Two is faster at any problem than a traditional computer that the massive amount of knowledge gained about quantum computers will outweigh the costs.
It's far too early to worry about a non-zero probability of it not working, just like fusion power. All it takes is one breakthrough and a revolution in computing will begin. Doing research on quantum computers is a low-risk and high-reward situation. None of these companies are betting everything on quantum computers.
Firstly, this is the first of a new class of computers, so I am not surprised it may be slow at first. Secondly, this machine uses a relatively small number of bits, compared to a classical computer. Lastly, they're throwing classical problems at a quantum processor and wondering why it's not magically faster. I would like to see how an optimized quantum algorithm performs.
A few other comments have pointed it out already, but how does this comparison actually mean anything? For example, multiplication with the first hole-punch computers was no faster than multiplying by hand and paper (probably slower), but look where we are now!
Are there others that you can buy? As far as I know, D-Wave is the only one out of the lab. I'm totally a D-Wave skeptic, but I do have to state that the scientists who tested this thing sound like idiots, unless they really did try quantum annealing. If the D-Wave guys say they tried the wrong set of equations for the device, I'm inclined to believe them.
Even though I don't even believe this thing is really a quantum computer, there are much more specific and defined ways to poke holes in D-Wave than just by running some tests and comparing speed. D-Wave has, very specifically, targeted this machine at one function: http://en.wikipedia.org/wiki/Quantum_annealing
Unless you're doing quantum annealing on the D-Wave, it might as well be a toaster, an Android phone, or a Windows PC. It's made to do only quantum annealing.
Did D-Wave 2 somehow expand its capabilities? I'm basing this on D-Wave 1 knowledge, but I cannot imagine anything really changed except the number of Qbits inside the thing.
All this having been said, the D-Wave has yet to prove that it is even doing Quantum Annealing, let alone that it's faster than a traditional computer at this problem set. No one has shown it to be faster than traditional outside of D-Wave.
Yes, of course they did what D-wave calls quantum annealing. As you say, that's all the D-Wave machines can do.
The D-Wave executive's claim that the problems used in the study are "not at all the right choice for probing a quantum speedup" is in reference to the specific subtypes of quantum annealing problems that this study looked at, not whether they were doing quantum annealing at all.
I'm not as up on Quantum Computing as I'd like to be, but the title seems to imply that QC as a concept is no faster than regular computing. Which may be true for general purpose computing, but that's never what QC was intended for.
What's the definition of "ordinary PC" being used? Not finding an answer to that in the article, which makes it difficult to get an idea of what the researchers are comparing this thing to.
So is that a brand-new Dell XPS machine? Is that my aging-not-too-well Compaq Presario 1210 with a Pentium? Is that a Macbook Air? Is that one of Oracle's $200,000 M-series servers? Is that some beige-box piece of junk that the researchers found in their neighbor's backyard? The category "personal computers which do not exploit quantum-mechanical principles of computation" is so mind-bogglingly vast that such a description alone is hardly useful.
Weird title. If someone built a quantum computer that performed remotely as well as a 2014-era classical machine, that would be huge news. Quantum computers are really hard to build.
Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases. This has been mathematically proven. (EDIT: No it hasn't apparently. See Michael Nielsen's response below.)