Performance of quantum computer no better than ordinary PC, say analysts | Hacker News Reader

Performance of quantum computer no better than ordinary PC, say analysts

csmonitor.com

46 pointsaasarava42 comments

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.

Edit: Here's the thread I was thinking of where t'Hooft and Shor discuss this http://physics.stackexchange.com/questions/34217/why-do-peop...

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:

http://rjlipton.wordpress.com/2013/04/27/sex-lies-and-quantu...

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

http://www.wisdom.weizmann.ac.il/~oded/on-qc.html

http://www.cs.bu.edu/fac/lnd/expo/qc.htm

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.

http://en.wikipedia.org/wiki/Shor's_algorithm#Finding_the_pe...

Shor's algorithm is still very theoretical though, we need to actually build a quantum computer to run it first.

What about searching an unsorted database? Quantum can do it in O(N^0.5). Hasn't it been proven that classical computers need O(N)?

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.

http://arxiv.org/abs/quant-ph/9802049

Calm down dude. "Quantum computer" in the title refers specifically to the D-wave. Headlines leave out specifiers all the time.

ex.: "Man bites dog" doesn't mean "all of mankind bit a dog", it means "this man bit a dog".

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

P.S. why did you go with "man bites dog"?

It's a saying.

http://en.wikipedia.org/wiki/Man_bites_dog_(journalism)

Ahhh, I'd never heard that before.

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

Obviously it's not "very clear" as I was not the only one who took at as a more general statement. Just read through this thread.

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.

For a performance reference similar to Moore's law, check out the quantum version (Rose's law): https://2.bp.blogspot.com/-AZFZhBUmwds/UHT2yF39AHI/AAAAAAAAI...

Here is another article today bashing the D-Wave Two computers: http://www.wired.com/2013/06/d-wave-quantum-computer-usc/

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.

According to http://www.dwavesys.com/d-wave-two-system as you scale up qubits the power demands do not increase. That alone has huge potential.

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.

https://www.youtube.com/watch?v=CMdHDHEuOUE

"We don't know the best questions to ask the quantum computers, that's what we're trying to find out now."

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.

It depends on your definition of quantum computing, the D-Wave does http://en.wikipedia.org/wiki/Quantum_annealing and has been faster in some applications.

https://plus.google.com/+QuantumAILab/posts

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]

[1] https://plus.google.com/+QuantumAILab/posts/DymNo8DzAYi

> The hardware outperforms off-the-shelf solvers by a large margin

But it doesn't outperform classical algorithms specifically written to solve the types of problems that the D-Wave machine accepts.

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.

Just like early digital computers couldn't out-perform specialized mechanical analog computers.

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.

Certainly, but maybe it's not a business yet?

>We're trying to learn how they work

Is the operation of the D-Wave an unknown? I don't know much about it.

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.

https://www.youtube.com/watch?v=HKUZ6IuJyHw

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.

This is the paper in question: http://www.sciencemag.org/content/early/2014/06/18/science.1...

Which appears (I can't tell, paywalled) to be an update or this one: http://arxiv.org/abs/1401.2910

I don't have to time to read the article properly right now, but doesn't look like they did anything ridiculous in their choice of testing algorithm.

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!

The title is slightly misleading. This article is only talking about the performance of one specific quantum computer. (The D-Wave Two).

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.

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.

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.

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.

One which doesn't exploit quantum-mechanical principles of computation.

Wouldn't that be a classical computer? PC is a weird term to use here.

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.

Also:

https://news.ycombinator.com/item?id=7917482

https://news.ycombinator.com/item?id=7917749

Original article: http://www.livescience.com/46414-first-quantum-computer-no-f...

Previously: https://news.ycombinator.com/item?id=7917749

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.

Reply on news.ycombinator.com