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?

  • 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. Commented Oct 24, 2012 at 13:58

2 Answers 2


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.

  • 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. Commented Oct 24, 2012 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. Commented Oct 24, 2012 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. Commented Oct 26, 2012 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. Commented Oct 26, 2012 at 14:40

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

  • 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
    Commented Oct 24, 2012 at 14:23
  • +1 Very short, but nailed exactly what I wanted to know when reading the question title ^^
    – Luc
    Commented Oct 24, 2012 at 16:52
  • 1
    @Ashwin What do you base that information on?
    – Jeff Ferland
    Commented Oct 24, 2012 at 17:56
  • @JeffFerland : See this -en.wikipedia.org/wiki/D-Wave_Systems
    – Ashwin
    Commented Oct 25, 2012 at 0:59
  • 2
    @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. Commented Oct 25, 2012 at 14:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .