Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I saw this video on youtube on quantum computing. It says that a company called dwavesys has already made commercially available quantum computer. I checked on the website and it exists. I thought that this was still in theory and quantum computers are a distant future.
If what the video says is true, then the whole Public Key Infrastructure will collapse, right?

share|improve this question
1  
A bit off-topic: there is more and more evidence that the brain is actually working like quantum computer in way it process the information. This way, everything can be considered to be quantum computer. So basically making quantum computers is like making the nature again, no difference. –  Andrew Smith Oct 24 '12 at 13:58
add comment

2 Answers

up vote 18 down vote accepted

Yes, a fully functional quantum computer could solve the hard problems that are at the root of Public Key cryptography. And yes, D-Wave Systems have indeed produced a machine that seems to have some characteristics of quantum computing. But D-Wave have yet to demonstrate that their computer meets all the criteria of quantum computing needed to solve problems like the RSA problem or the discrete logarithm problem.

In fact some experts doubt if the D-Wave computer should be considered a quantum computer at all. MIT Associate Professor Scott Aaronson wrote on his blog:

For me, three crucial points to keep in mind are:

(1) D-Wave still hasn’t demonstrated 2-qubit entanglement, which I see as one of the non-negotiable “sanity checks” for scalable quantum computing. In other words: if you’re producing entanglement, then you might or might not be getting quantum speedups, but if you’re not producing entanglement, then our current understanding fails to explain how you could possibly be getting quantum speedups.

(2) Unfortunately, the fact that D-Wave’s machine solves some particular problem in some amount of time, and a specific classical computer running (say) simulated annealing took more time, is not (by itself) good evidence that D-Wave was achieving the speedup because of quantum effects. Keep in mind that D-Wave has now spent ~$100 million and ~10 years of effort on a highly-optimized, special-purpose computer for solving one specific optimization problem. So, as I like to put it, quantum effects could be playing the role of “the stone in a stone soup”: attracting interest, investment, talented people, etc. to build a device that performs quite well at its specialized task, but not ultimately because of quantum coherence in that device.

(3) The quantum algorithm on which D-Wave’s business model is based — namely, the quantum adiabatic algorithm — has the property that it “degrades gracefully” to classical simulated annealing when the decoherence rate goes up. This, fundamentally, is the thing that makes it difficult to know what role, if any, quantum coherence is playing in the performance of their device. If they were trying to use Shor’s algorithm to factor numbers, the situation would be much more clear-cut: a decoherent version of Shor’s algorithm just gives you random garbage. But a decoherent version of the adiabatic algorithm still gives you a pretty good (but now essentially ”classical”) algorithm, and that’s what makes it hard to understand what’s going on here.

So at least for now there is no practical quantum computer in existence that would undermine Public Key cryptography nor is one expected in the near future. Some experts believe that it's still a long way off.

BTW, for a great analysis of the impact of a future quantum computer on cryptography I would recommend Matthew Green's blog post on this subject.

share|improve this answer
    
Point (3) is fascinating - that one can set about building a quantum computer and have it compute stuff - but not be entirely sure that what you built is actually doing quantum computation. –  Mark Beadles Oct 24 '12 at 16:01
    
+1 for remembering Matthew Green's blog post from April! I couldn't find it again until now. (Thank you) Scott's Shtetl-optimized is of course a good choice too. –  Feral Oink Oct 24 '12 at 18:10
    
I don't understand how D-Wave gets so much venture funding! I read what David wrote, and I looked over D-Wave's website. They just got a HUGE glob of funding money from Jeff Bezos and the CIA's VC whatamcallit, um InkQuTel or IQ-U-Tel, I never can remember. Scott also posted a challenge on an IEEE Spectrum blog, that he'd pay anyone who had proof of a quantum computer, per criteria above (I guess?), and no one has claimed it yet. I'll find the link. –  Feral Oink Oct 26 '12 at 14:29
    
Sorry, Scott said he'd pay $100,000, not $5000, to anyone who could prove that a quantum computer was NOT possible. But that is the same thing, well sort of. Here's the URL spectrum.ieee.org/tech-talk/computing/hardware/… There's also a photo of Scott, for the curious. Read the comments for more details. –  Feral Oink Oct 26 '12 at 14:40
add comment

Sort of, a couple unis have made experimental quantum processors but they haven't managed to match the power of a pocket calculator yet.

share|improve this answer
    
Google is one of the companies using the quantum computers of the D-Waves. Google would not have used it if it did not even have the computing power of a calculator. –  Ashwin Oct 24 '12 at 14:23
    
+1 Very short, but nailed exactly what I wanted to know when reading the question title ^^ –  Luc Oct 24 '12 at 16:52
1  
@Ashwin What do you base that information on? –  Jeff Ferland Oct 24 '12 at 17:56
    
@JeffFerland : See this -en.wikipedia.org/wiki/D-Wave_Systems –  Ashwin Oct 25 '12 at 0:59
1  
@Ashwin There are a lot of doubts around whether the D-Wave One is actually a quantum computer or not. Considering Bristol Uni have only managed a very weak processor I really doubt a commercial company has managed to build a full quantum computer. –  Inverted Llama Oct 25 '12 at 14:25
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.