Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Large-scale quantum chip validated

news.usc.edu

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Large-scale quantum chip validated

#21

Post by some_guy_there »

karpathy wrote: post #10
some_guy_there wrote: post #7

Earlier quoted context omitted.

The machine solves QUBO problem. You program in the Q_ij and a set of X's is returned as answer. http://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_...

(Also equivalently and more commonly known as the Ising Model). The D-wave chip is just a very fast hardware-based Ising model solver. You can use it to both find the minimum of a problem through cooling, or by controlling the temperature of the system you can also do sampling. And since so many important problems can be reduced to an Ising model, this is interesting. What I don't fully understand is why is it so imp…

Just to correct your first statement, in their recent article, they have ruled out idea that D-wave solves problems by cooling (otherwise known as simulated or classical annealing). Quantum annealing, a special case of Adiabatic Quantum Computing, is a completely different approach for solving Ising problems.

Unconstrained optimization is NP-hard problem, and quantum approaches won't change that. However, D-wave hopes they are faster in solving optimizations than classical solvers, something they haven't demonstrated yet. The fact whether D-wave is actually a Quantum machine is interesting to Computer Scientists and Physicist who care about accuracy of commercial hype, and also to D-wave's future customers.

Re: Large-scale quantum chip validated

#23

Post by gjm11 »

This is "validated" in a pretty weak sense.

I think the paper is (perhaps a slightly different version of) this one: http://arxiv.org/abs/1212.1739 in which the researchers found evidence that favours the hypothesis "the D-Wave device is doing quantum annealing" over the hypothesis "the D-Wave device is doing classical simulated annealing".

That's very interesting scientifically (though it's not clear to me how far they've ruled out other basically-classical processes) but it's important to notice what it isn't.

It isn't evidence that D-Wave's device can perform the operations usually denoted by the phrase "quantum computing". (So far as I know, no one thinks it can.) So, e.g., there is no known way to use it to break RSA encryption, no matter how well it does the things it does.

It isn't evidence that there is any problem D-Wave's device can actually solve faster than a classical computer.

It isn't evidence that there is any useful problem D-Wave's device can actually solve faster than a classical computer.

See http://www.archduke.org/stuff/d-wave-comment-on-comparison-w... for some comparisons between the published performance figures for D-Wave's device and simple software running on (one core of) an ordinary laptop. The laptop comes up faster every time, even solving the exact problem D-Wave's device is designed to solve.

That doesn't rule out the possibility that there may be other instances of that problem that D-Wave's device solves much faster than anything you can do on a laptop (but no one seems to have found any) nor the possibility that some future version of D-Wave's device may be much better because it scales better (though Alex Selby's figures aren't particularly encouraging on that score). But claims that D-Wave, now, have a useful quantum computer don't look very plausible.

Re: Large-scale quantum chip validated

#24

Post by frozenport »

frisco wrote: post #11

I've been thinking this for a while and have really come to believe it recently, but I'd be amazed if the NSA didn't have quantum computing down, either at scale or about to get there. Historically they've been, and similar organizations are perceived to be, 5-10 years ahead of public technology, so I'm going to go ahead and assume that all PKE is broken as far as the USG is concerned. I've heard from someone who'd k…

The same argument can be used for flying saucers, because hell maybe in the next 100 years we will have flying saucers.

Anyways, my field is likewise peripheral to quantum computing (computational E&M) but having worked in HPC OEM the NSA buys lots of equipments that would be used for conventional password cracking. We would expect them to stop buying that stuff when they broke the speed-of-light and got a quantum computer.

What they most likely have are novels ways to do collisions on different algorithms. Such as the MD5 collision scheme used by the recent 2 US/Israeli viruses.

Re: Large-scale quantum chip validated

#26

Post by jessriedel »

mtgx wrote: post #12
frisco wrote: post #11

I've been thinking this for a while and have really come to believe it recently, but I'd be amazed if the NSA didn't have quantum computing down, either at scale or about to get there. Historically they've been, and similar organizations are perceived to be, 5-10 years ahead of public technology, so I'm going to go ahead and assume that all PKE is broken as far as the USG is concerned. I've heard from someone who'd k…

Google got in on this early: > On February 13, 2007, D-Wave demonstrated the Orion system, running three different applications at the Computer History Museum in Mountain View, California. This marked the first public demonstration of, supposedly, a quantum computer and associated service. > On Tuesday, December 8, 2009 at the Neural Information Processing Systems (NIPS) conference, a Google research team led by Hart…

To emphasize what comex said: quantum cryptography is not an information theoretic defense against RSA-breaking quantum computers running Shor's algorithm. Not at all. It requires completely replacing the physical hardware connection between the two communicating parties.

Re: Large-scale quantum chip validated

#27

Post by jessriedel »

gjm11 wrote: post #23

This is "validated" in a pretty weak sense. I think the paper is (perhaps a slightly different version of) this one: http://arxiv.org/abs/1212.1739 in which the researchers found evidence that favours the hypothesis "the D-Wave device is doing quantum annealing" over the hypothesis "the D-Wave device is doing classical simulated annealing". That's very interesting scientifically (though it's not clear to me how far t…

> I think the paper is (perhaps a slightly different version of) this one: http://arxiv.org/abs/1212.1739 in which the researchers found evidence that favours the hypothesis "the D-Wave device is doing quantum annealing" over the hypothesis "the D-Wave device is doing classical simulated annealing".

> (though it's not clear to me how far they've ruled out other basically-classical processes)

According to my colleagues at IBM Research, not far:

> A pair of recent articles concluded that the D-Wave One machine actually operates in the quantum regime, rather than performing some classical evolution. Here we give a classical model that leads to the same behaviors used in those works to infer quantum effects. Thus, the evidence presented does not demonstrate the presence of quantum effects.

http://arxiv.org/abs/1305.4904

Re: Large-scale quantum chip validated

#28

Post by mitmatt »

jessriedel wrote: post #27
gjm11 wrote: post #23

This is "validated" in a pretty weak sense. I think the paper is (perhaps a slightly different version of) this one: http://arxiv.org/abs/1212.1739 in which the researchers found evidence that favours the hypothesis "the D-Wave device is doing quantum annealing" over the hypothesis "the D-Wave device is doing classical simulated annealing". That's very interesting scientifically (though it's not clear to me how far t…

> I think the paper is (perhaps a slightly different version of) this one: http://arxiv.org/abs/1212.1739 in which the researchers found evidence that favours the hypothesis "the D-Wave device is doing quantum annealing" over the hypothesis "the D-Wave device is doing classical simulated annealing". > (though it's not clear to me how far they've ruled out other basically-classical processes) According to my colleague…

The USC group has a response to Smolin and Smith which explains how some quantitative features are still best explained by a simulated quantum annealer: http://arxiv.org/abs/1305.5837. So there's still some potential for evidence of quantum effects (though "maybe doing something nonclassical" is a far cry from all the marketing talk, especially since annealing with stoquastic Hamiltonions with a fixed topology is already a far cry from any known-to-be-useful quantum computing model).

Re: Large-scale quantum chip validated

#29

Post by jessriedel »

mitmatt wrote: post #28
jessriedel wrote: post #27

Earlier quoted context omitted.

> I think the paper is (perhaps a slightly different version of) this one: http://arxiv.org/abs/1212.1739 in which the researchers found evidence that favours the hypothesis "the D-Wave device is doing quantum annealing" over the hypothesis "the D-Wave device is doing classical simulated annealing". > (though it's not clear to me how far they've ruled out other basically-classical processes) According to my colleague…

The USC group has a response to Smolin and Smith which explains how some quantitative features are still best explained by a simulated quantum annealer: http://arxiv.org/abs/1305.5837 . So there's still some potential for evidence of quantum effects (though "maybe doing something nonclassical" is a far cry from all the marketing talk, especially since annealing with stoquastic Hamiltonions with a fixed topology is al…

Ooh, thanks. I think John and Graeme have been working on a second version, presumably in response to this. The battle continues...

Re: Large-scale quantum chip validated

#30

Post by bsaul »

There's something i don't get with this debate around "is this quantum or classical" : i thought quantum computing meant breaking NP complexity. So, in order to determine if it "is" quantum computing, one would suppose that any big dataset would easily show the difference in computing time...

Now, if i understood correctly, the problem is that the algorithms compared (aka annealing) are of statistical nature, so we're not actually comparing "fully" NP complete algorithms, and so the expected difference is not as a big as between an O(n) and an O(x^n)) algorithm.

Could someone here confirm if this is correct ?

Post reply on HN