D Wave has been iterating on their flagship machine for a few years now. The big argument is if entanglement is happening on a large enough scale in their system to enable the scaling laws that they claim they'll be able to hit. You can find plots floating around where they extrapolate to having a computer more powerful than a classical computer the size of the universe in ~2020. Right now it's barely comparable with a rack of servers IIRC, but the big claim is that quantum power scales much faster than classical power with number of bits (exponential vs linear) when full entanglement is achieved. I'm under the impression that the Googles and Boings and NASAs of the world want to get their feet wet in the field despite its infancy.
It's a good effort at any rate. There's a lot of strong negativity around DWave, which I find strange, given that it's existence isn't personally inconveniencing their critics in any way. If adiabatic quantum computing works it will really speed up the future tech timeline, so it's worth the effort.
Last I heard, it wasn't even any faster than a mid-range desktop PC at the class of problems it was optimised to solve most efficiently. Has this improved since then?
I think so, but not super significantly. I don't think that's so much the point though - the claim is that they'll scale much faster than moore's law. Given the likely end of moore's law, this is a pretty big deal. So even if they're mediocre now the claim is that they could be amazing in 5-10 years.
"I'm under the impression that the Googles and Boings and NASAs of the world want to get their feet wet in the field despite its infancy."
And note this is invariably trumpeted loudly as in current production commercial end user applications. There are obvious financial / stock market reasons for these wild claims. But if you clear away the PR haze, the field is actually in the earliest research mode.
By computer analogy, whats going on in reality is the first ENIAC has been partially wired although it doesn't work perfectly and may in fact never meet its goals and may or may not ever have any direct effect on anyone, although existing unit record equipment manufacturers are watching nervously. The analogy of whats being presented by PR as a completed accomplishment is Zilog having shipped their fifty millionth Z80 processor and the living rooms of America are stuffed with "1980s home computers" which pretty much did have at least some effect on everyone alive either then or later.
This flavour of quantum computing has no obvious implications for crypto, and the technology isn't transferrable to a computer which would.
The problem is that quantum annealing (basically, solving complex optimisation problems) is a small subset of what a full quantum computer can do. The algorithms we know can break crypto: Shor's algorithm (integer factorisation) and Grover's algorithm (database search) can only run on full quantum computers. eg. so far Shor's algorithm has only ever factored 21 into 3x7 (equivalent to breaking 5-bit RSA).
Things like Shor's are more obvious in gate based architectures, and would likely be faster - unfortunately there's not been as much as much scaling in building those architectures. DWave has stated that they're also less interested in these sorts of applications, probably for performance issues as well as actual value. Enabling the NSA to break crypto is ok, but selling 20 general purpose systems optimizers for drug manufacturers, engineering firms etc. might be more profitable or more interesting to them now. DWave addresses this distinction here: http://www.washingtonpost.com/blogs/the-switch/wp/2014/01/10...
Even assuming D-Wave actually achieves quantum annealing (a highly uncertain proposition at this point), the implications for cryptography are inexistent. Quantum algorithms relevant to cryptography (mostly Shor's and Grover's) require a general purpose quantum computer, which the D-Wave machine is emphatically not.
Quantum cryptography is in my opinion a bit of a rat race, you can make theoretically perfect systems, but the implementation will probably have some weakness.
One of the main problems with Quantum Crypto is it's implementation. You can make claims of infinite precision, and perfect entropy, etc. The problem is when you move beyond a blackboard you will be limited by the amount the amount that can be measured, which working with a classical computer ie IEEE754-128bit floating points are VERY finite.
The real arms race is between better detectors, and particle creators
No: so far there is some (but highly contested) evidence of a quantum effect, but no evidence of quantum speedup. And in general, there are very good reasons for betting ex ante that their particular approach (quantum adiabatic) is way off the mark and will never pan out.
Like other commenters wrote earlier [1,2], Aaronson has done an excellent job over the years of calling them out on their bullshit; so check out his blog and media appearances. Also, for some reason, the signal-to-noise ratio in this topic is unusually low even among 'expert opinion' (as you can tell from that BBC article), so keep that in mind.
The D-Wave implements, in hardware, a certain multivariable optimization algorithm. It is not a general purpose computer, and it has no implications for cryptography.
"MAGIC 8-BALL: THE RENEGADE MATH WHIZ WHO COULD CHANGE NUMBERS FOREVER
An eccentric billionaire, whose fascinating hobbies include nude skydiving and shark-taming, has been shaking up the scientific world lately with his controversial claim that 8+0 equals 17 [... six more pages about the billionaire redacted ...] It must be said that mathematicians, who we reached for comment because we're diligent reporters, have tended to be miffed, skeptical, and sometimes even sarcastic about the billionaire's claims. Not surprisingly, though, the billionaire and his supporters have had some dismissive comments of their own about the mathematicians. So, which side is right? Or is the truth somewhere in the middle? At this early stage, it's hard for an outsider to say. In the meantime, the raging controversy itself is reason enough for us to be covering this story using this story template. Stay tuned for more!"
And seriously:
"we have no idea yet whether adiabatic optimization (the technology used by D-Wave) is something where quantum computers can give any practically-important speedup."
And how the results match those of the machine based on the classical (that is, not quantum) model:
There is a history of literally many years of bombastic claims being made by D-Wave (especially in the popular press) without anything to back them up. Scott Aaronson (http://www.scottaaronson.com/blog/), an MIT professor who is one of the better-known scientists in the quantum computing field, has written reams of pages about this. I would recommend browsing his blog if you are really interested in the claims and counterclaims about this company.
As for me, I will not waste a single minute reading an article about them, until they can convince the sceptics first. This may seem unfair (if people aren't willing to give them a chance, then how will we know if they've really made a breakthrough), but this company has earned this kind of treatment by bamboozling journalists and getting breathless press coverage based on nothing. Briefly, for years, they failed to even demonstrate that their machine exhibits any quantum entanglement at all; this makes it meaningless to talk about quantum computing on that machine, which didn't prevent press stories touting it as the next revolution in all of human existence. Since then, there have been some articles claiming that possibly there is some kind of quantum behaviour in the machine, but there was still no evidence that this quantum behaviour is doing anything meaningful in the actual computations. At some point, I stopped following the story.
You are correct that they seem to have not yet built a proper adiabatic quantum computer (aren't even trying/capable of building a universal one). However I do think that the press around them is good for quantum computing in general.
I work trying to make the early stages of a qcomputer using semiconductor quantum dots and I definitely think that the press around DWave is helpful.
Firstly they are showing that there is a well defined commercial interest in such a computer. I also think that they are paving the path that other such companies will take in the future.
But yeah I agree, they have not yet shown much in terms of a real, useful quantum computer. There is a lot of unjustified hype in the technology, but at the same time I think its useful for this hype to exist for the q-tech industry in general.
I do not think that the press from D-Wave is good for quantum computing in general. For this reason:
" I predict that the very same people now hyping D-Wave will turn around and—without the slightest acknowledgment of error on their part—declare that the entire field of quantum computing has now been unmasked as a mirage, a scam, and a chimera." - Scott Aaronson
If D-Wave fails it will cause at least a decade of non existent funding to QC in general because it will be reduced to the level of cold fusion in the press.
So basically, D-Wave are working hard to make sure there will be a Quantum Computing Winter, two decades of darkness and cold for QC researchers before the field can eventually get going again.
Looks that way. They even wrote their machine's OS in Lisp, or so I hear, which probably doesn't bear directly on the question at hand but is certainly suggestive as anything.
There are some system utilities written in Lisp by one of the devs, but there is nothing like an OS written in Lisp. It's the same as saying that Linux is written in Haskell because of Xmonad.
And by the way, spreading stupid gossips like this is very suggestive on certain individual's intents.
Good to know; I haven't been able to find a lot of detail on the subject of how D-Wave uses Lisp, so I was just repeating what I've heard, which I concede I probably shouldn't have done.
(And I'm a Lisp hacker myself, so I'm not really interested in attempting to further wreck the reputation of that language family; indeed, I'm delighted to see projects like Clojure beginning to resurrect said reputation, and the only way I could be happier about that would be if Clojure did a better job living up to its predecessors.)
> The main processor doesn’t run an OS in the sense you’re thinking of. The OS is written in LISP and isn’t exposed to developers at this point.
> No, but the APIs we’ve got are basically wrappers around lisp, so it would be easy to make one. Just figured the number of lisp coders out there was probably pretty small.
I understand why the actual quantum effect is hard to observe, but I'm not sure I understand why the output is so hard to verify as being better or worse than a classical computer....
Can someone name the physical effect that this processor employs outside of any quantum effects that accounts for it possibly being faster than a room temperature "normal" computer?
What algorithms are they running to try to verify that the computer is quantum?
D-Wave's machine is running an approximate optimisation algorithm. It's like trying to solve a large Sudoku by filling in all of the squares randomly then adjusting them to make the solution better and better (ie. get fewer invalid squares).
They're using an 'annealing' algorithm to do this, which means that the squares are all adjusted concurrently, in a random way which is biased by how well each square's value fits with its neighbour's. D-Wave claimed that their machine is quantum, without much evidence. They've since shown reasonable evidence that their machine does indeed use quantum effects, so that it's running a 'quantum annealing' algorithm; that basically means there's some probability for non-neighbouring squares to interact, which may find better solutions faster.
However, 'quantum annealing' isn't difficult to calculate. Despite the name, it's easy for classical computers to implement it and they can do it faster than D-Wave's machine (thanks to decades of Moore's Law). So at this point D-Wave have a single-purpose ASIC which is more expensive and slower than regular computers. They're doing something quantum, but there doesn't seem to be much point.
Compare this to a "real" quantum computer, which would be general-purpose (rather than being restricted to one algorithm like D-Wave's machine) and would be able to efficiently run things like Shor's algorithm, which are known to be unscalable on classical computers.
"In other words, even if you could implement adiabatic optimization perfectly—at zero temperature, with zero decoherence -- we still don't know whether there's any quantum speedup to be had that way, for any of the nifty applications that the article mentions:
'software design, tumor treatments, logistical planning, the stock market, airlines schedules, the search for Earth-like planets in other solar systems, and in particular machine learning'"
Even a general purpose quantom computer would be hard/impossible to verify without studying the internals. For example, we have used a general quantom computer to preform shors algorithm and factor 21. I am not aware of how long the computer took to do so, but it would not suprise me if my cellphone would be faster using naive trial division.
Assuredly so. Why not? Journalism and Science are all about extrapolation, in part or whole. That's how you get good books, good inventions and good science.
No. The quantum mechanics that "supports" many-worlds (as in, many-worlds seems to be the simplest explanation for the observed effects) has been in the realm of "scientifically proven fact" for >70 years. D-wave will not add significantly to the pile of evidence that already exists.
As for time travel, I can't possibly imagine how you think the two are related. Bell's Theorem was verified 50 years ago. D-wave will not add to the pile of evidence that already exists for quantum non-locality, it will not contribute to exploiting quantum non-locality for the purposes of time travel (if such a thing is even possible -- as we understand it, non-locality can't even be used to transmit information femtoseconds back in time), and it will not contribute to proving or disproving alternative theories for non-locality.
What I was suggesting is that this would empirically favor quantum decoherence over waveform collapse.
The ability to subsequently control quantum decoherence allows for its patterns to be recorded and reproduced; i.e. an ability which would allow humans to eventually recreate entire quantum sections and perhaps eventually allow them to alter both the past, present and future states in-between the margins of quantum decoherence.
I'm not suggesting non-locality; I'm suggesting non-realism from a universal standpoint and thus the ability to control 'reality' lies in the ability of human beings to control quantum decoherence and quantum mechanics.
The ability to recreate a version of the past via quantum mechanics is, in effect, time travel.
We aren't too far away from full control of decoherence:
Even if it solves some optimization problems well, it's not worth $15m. You can come up with the same solutions by spending far less money on way more CPU power. Plus it's a black box which has totally proprietary content you are not allowed to investigate based on some magical functionality. High on the PT Barnum Scale.
As a relative layman, doesn't the interest from Google / NASA / Lockheed give some merit to their claims? Or at least move it from the 'PT Barnum' scale to some other speculative-but-feasible technology scale?
No. Once some entity has a lot of money to spend, it invests it in various directions "just in case it might work." It's inevitable process, as soon as there are a lot of people making decisions (or even a small number of them, when it reflects their preferences). The money is invested in very weird stuff and then even get to be used, "because it's there" even if it's not really what it claims to be.
48 comments
[ 4.0 ms ] story [ 122 ms ] threadAnd what are the implications for cryptography? (isn't that always the refrain, "until quantum computers this is safe?")
It's a good effort at any rate. There's a lot of strong negativity around DWave, which I find strange, given that it's existence isn't personally inconveniencing their critics in any way. If adiabatic quantum computing works it will really speed up the future tech timeline, so it's worth the effort.
And note this is invariably trumpeted loudly as in current production commercial end user applications. There are obvious financial / stock market reasons for these wild claims. But if you clear away the PR haze, the field is actually in the earliest research mode.
By computer analogy, whats going on in reality is the first ENIAC has been partially wired although it doesn't work perfectly and may in fact never meet its goals and may or may not ever have any direct effect on anyone, although existing unit record equipment manufacturers are watching nervously. The analogy of whats being presented by PR as a completed accomplishment is Zilog having shipped their fifty millionth Z80 processor and the living rooms of America are stuffed with "1980s home computers" which pretty much did have at least some effect on everyone alive either then or later.
The problem is that quantum annealing (basically, solving complex optimisation problems) is a small subset of what a full quantum computer can do. The algorithms we know can break crypto: Shor's algorithm (integer factorisation) and Grover's algorithm (database search) can only run on full quantum computers. eg. so far Shor's algorithm has only ever factored 21 into 3x7 (equivalent to breaking 5-bit RSA).
Things like Shor's are more obvious in gate based architectures, and would likely be faster - unfortunately there's not been as much as much scaling in building those architectures. DWave has stated that they're also less interested in these sorts of applications, probably for performance issues as well as actual value. Enabling the NSA to break crypto is ok, but selling 20 general purpose systems optimizers for drug manufacturers, engineering firms etc. might be more profitable or more interesting to them now. DWave addresses this distinction here: http://www.washingtonpost.com/blogs/the-switch/wp/2014/01/10...
One of the main problems with Quantum Crypto is it's implementation. You can make claims of infinite precision, and perfect entropy, etc. The problem is when you move beyond a blackboard you will be limited by the amount the amount that can be measured, which working with a classical computer ie IEEE754-128bit floating points are VERY finite.
The real arms race is between better detectors, and particle creators
Like other commenters wrote earlier [1,2], Aaronson has done an excellent job over the years of calling them out on their bullshit; so check out his blog and media appearances. Also, for some reason, the signal-to-noise ratio in this topic is unusually low even among 'expert opinion' (as you can tell from that BBC article), so keep that in mind.
[1] https://news.ycombinator.com/item?id=7771697
[2] https://news.ycombinator.com/item?id=7771684
The D-Wave implements, in hardware, a certain multivariable optimization algorithm. It is not a general purpose computer, and it has no implications for cryptography.
"MAGIC 8-BALL: THE RENEGADE MATH WHIZ WHO COULD CHANGE NUMBERS FOREVER
An eccentric billionaire, whose fascinating hobbies include nude skydiving and shark-taming, has been shaking up the scientific world lately with his controversial claim that 8+0 equals 17 [... six more pages about the billionaire redacted ...] It must be said that mathematicians, who we reached for comment because we're diligent reporters, have tended to be miffed, skeptical, and sometimes even sarcastic about the billionaire's claims. Not surprisingly, though, the billionaire and his supporters have had some dismissive comments of their own about the mathematicians. So, which side is right? Or is the truth somewhere in the middle? At this early stage, it's hard for an outsider to say. In the meantime, the raging controversy itself is reason enough for us to be covering this story using this story template. Stay tuned for more!"
And seriously:
"we have no idea yet whether adiabatic optimization (the technology used by D-Wave) is something where quantum computers can give any practically-important speedup."
And how the results match those of the machine based on the classical (that is, not quantum) model:
http://arxiv.org/abs/1401.7087
As for me, I will not waste a single minute reading an article about them, until they can convince the sceptics first. This may seem unfair (if people aren't willing to give them a chance, then how will we know if they've really made a breakthrough), but this company has earned this kind of treatment by bamboozling journalists and getting breathless press coverage based on nothing. Briefly, for years, they failed to even demonstrate that their machine exhibits any quantum entanglement at all; this makes it meaningless to talk about quantum computing on that machine, which didn't prevent press stories touting it as the next revolution in all of human existence. Since then, there have been some articles claiming that possibly there is some kind of quantum behaviour in the machine, but there was still no evidence that this quantum behaviour is doing anything meaningful in the actual computations. At some point, I stopped following the story.
I work trying to make the early stages of a qcomputer using semiconductor quantum dots and I definitely think that the press around DWave is helpful.
Firstly they are showing that there is a well defined commercial interest in such a computer. I also think that they are paving the path that other such companies will take in the future.
But yeah I agree, they have not yet shown much in terms of a real, useful quantum computer. There is a lot of unjustified hype in the technology, but at the same time I think its useful for this hype to exist for the q-tech industry in general.
" I predict that the very same people now hyping D-Wave will turn around and—without the slightest acknowledgment of error on their part—declare that the entire field of quantum computing has now been unmasked as a mirage, a scam, and a chimera." - Scott Aaronson
If D-Wave fails it will cause at least a decade of non existent funding to QC in general because it will be reduced to the level of cold fusion in the press.
There are some system utilities written in Lisp by one of the devs, but there is nothing like an OS written in Lisp. It's the same as saying that Linux is written in Haskell because of Xmonad.
And by the way, spreading stupid gossips like this is very suggestive on certain individual's intents.
(And I'm a Lisp hacker myself, so I'm not really interested in attempting to further wreck the reputation of that language family; indeed, I'm delighted to see projects like Clojure beginning to resurrect said reputation, and the only way I could be happier about that would be if Clojure did a better job living up to its predecessors.)
http://dwave.wordpress.com/2011/05/20/learning-to-program-th...
> The main processor doesn’t run an OS in the sense you’re thinking of. The OS is written in LISP and isn’t exposed to developers at this point.
> No, but the APIs we’ve got are basically wrappers around lisp, so it would be easy to make one. Just figured the number of lisp coders out there was probably pretty small.
Can someone name the physical effect that this processor employs outside of any quantum effects that accounts for it possibly being faster than a room temperature "normal" computer?
What algorithms are they running to try to verify that the computer is quantum?
They're using an 'annealing' algorithm to do this, which means that the squares are all adjusted concurrently, in a random way which is biased by how well each square's value fits with its neighbour's. D-Wave claimed that their machine is quantum, without much evidence. They've since shown reasonable evidence that their machine does indeed use quantum effects, so that it's running a 'quantum annealing' algorithm; that basically means there's some probability for non-neighbouring squares to interact, which may find better solutions faster.
However, 'quantum annealing' isn't difficult to calculate. Despite the name, it's easy for classical computers to implement it and they can do it faster than D-Wave's machine (thanks to decades of Moore's Law). So at this point D-Wave have a single-purpose ASIC which is more expensive and slower than regular computers. They're doing something quantum, but there doesn't seem to be much point.
Compare this to a "real" quantum computer, which would be general-purpose (rather than being restricted to one algorithm like D-Wave's machine) and would be able to efficiently run things like Shor's algorithm, which are known to be unscalable on classical computers.
"In other words, even if you could implement adiabatic optimization perfectly—at zero temperature, with zero decoherence -- we still don't know whether there's any quantum speedup to be had that way, for any of the nifty applications that the article mentions: 'software design, tumor treatments, logistical planning, the stock market, airlines schedules, the search for Earth-like planets in other solar systems, and in particular machine learning'"
As for time travel, I can't possibly imagine how you think the two are related. Bell's Theorem was verified 50 years ago. D-wave will not add to the pile of evidence that already exists for quantum non-locality, it will not contribute to exploiting quantum non-locality for the purposes of time travel (if such a thing is even possible -- as we understand it, non-locality can't even be used to transmit information femtoseconds back in time), and it will not contribute to proving or disproving alternative theories for non-locality.
The ability to subsequently control quantum decoherence allows for its patterns to be recorded and reproduced; i.e. an ability which would allow humans to eventually recreate entire quantum sections and perhaps eventually allow them to alter both the past, present and future states in-between the margins of quantum decoherence.
I'm not suggesting non-locality; I'm suggesting non-realism from a universal standpoint and thus the ability to control 'reality' lies in the ability of human beings to control quantum decoherence and quantum mechanics.
The ability to recreate a version of the past via quantum mechanics is, in effect, time travel.
We aren't too far away from full control of decoherence:
http://www.sciencemag.org/content/320/5876/638
As a relative layman, doesn't the interest from Google / NASA / Lockheed give some merit to their claims? Or at least move it from the 'PT Barnum' scale to some other speculative-but-feasible technology scale?
I thought the watershed between a Classical computer and Quantum one was the ability to solve some hard problems believed to be in both NP and co-NP.