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 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."
You know, it's not impossible, but as someone who works in a field peripheral to quantum computing I would be surprised. There are two types of problems in science, the attrition kind where if you throw enough people and enough money at it you'll get it to work and the breakthrough kind where nothing will happen until some a-ha moment. I suspect quantum computing is more of the latter right now; there are just too many outstanding issues for a large-scale device. But who knows, I may be wrong.
Regarding D-Wave specifically, there's plenty of commentary around on what they're doing...
I'm not particularly well read on quantum computing, but it seems like we have reduced it to an engineering challenge at this point. We have already constructed and tested quantom computers with several quibits and (I am aware) of no theoretical limit to how many quibits we can have, so the problem is simply in engineering a device that can operate on all of them succesfully.
This is in contrast to most of the second type of breakthrough, where you typically have a theoretical revelation that opens previously closed doors.
> There are two types of problems in science, the attrition kind where if you throw enough people and enough money at it you'll get it to work and the breakthrough kind where nothing will happen until some a-ha moment.
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".
Since quantum cryptography requires a special physical connection between the two parties, it wouldn't be particularly effective at securing the all-important SSL traffic. Luckily, I highly doubt practical use of Shor's algorithm will be possible publicly in 5-10 years, but even if it will, it's not necessary to use quantum cryptography to defend against quantum computers:
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.
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.
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."