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.
> (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.
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 ?
I've heard from someone who'd know that a big driver of Google's purchase of the D-Wave was that, "if there's going to be a crypto breakthrough, [Google] would like to know about it early."
Regarding D-Wave specifically, there's plenty of commentary around on what they're doing...
This is in contrast to most of the second type of breakthrough, where you typically have a theoretical revelation that opens previously closed doors.
Thats interesting. What camp would you say flight fell under?
> 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 Hartmut Neven used D-Wave's processor to train a binary image classifier.
We can only hope quantum computers become commercially available as soon as possible, and many companies use them to encrypt the data and with perfect forward secrecy, that can at least provide some kind of protection against too many government abuses.
Because we're not going to be able to buy these ourselves in the next few decades, while the governments will be able to get as many as they want. So our only "hope" is that many companies can get them early, too, to protect their services against any type of "attacker".
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.
No speed up when compared to a classical machine (for much cheaper) emulating the exact same procedure:
The D-Wave processor probably isn't useful for cracking it. However, if you send RSA encrypted data, copies can be made of the encrypted data and cracked at a later date when better facilities or algorithms become available. If you wish to send a message that would make the NSA want to hunt you down and kill you if they decrypt it N years from now (and you plan to live >N years), you should probably be more careful. I don't think we have a good idea of what N is. It's probably pretty big, but it might not be.
What I don't fully understand is why is it so important to show that the device takes advantage of Quantum effects functionally? A classical super-efficient Ising Model solver is interesting enough.
Also, the video in the article is really quite terrible. I only half understood it because I know what they were trying to say, but if I didn't I think I'd be very confused at best, and amusingly misinformed at worst.
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.
Lots of interesting stuff about quantum computing and quantum algorithms in there. Some interesting tidbits:
- var x; var y = x
- print(x) <--- Impossible, quantum information can't be duplicated. x no longer exists.
- var y
- var x = f(y) <--- The value of y is now changed. You must undo f with f' to return y to it's original state.
(this is probably more directly relevant to programming though, and free: http://sneezy.cs.nott.ac.uk/qml/compiler/jjg-thesis.pdf)
 https://news.ycombinator.com/item?id=5957232 - comment https://news.ycombinator.com/item?id=5957686