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...
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.
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.
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.
"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.
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.
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
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.
Comments
Ok HN, for those skilled in the art, is this real?
And what are the implications for cryptography? (isn't that always the refrain, "until quantum computers this is safe?")
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).
I'm under the impression that quantum annealing is quantum turing complete - see: https://physics.stackexchange.com/questions/11063/can-quantu...
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...
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.
[1] https://news.ycombinator.com/item?id=7771697
[2] https://news.ycombinator.com/item?id=7771684
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.
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.
"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.
Yeah, the PR is pretty extreme. I like to think that this is more for public buzz and doesn't affect the decision makers, so I sort of disregard it.
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.
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.
Thank you.
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
http://cr.yp.to/talks/2008.10.18/slides.pdf
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.