DailyDirt: Quantum Computing Works Now (Sorta)

from the urls-we-dig-up dept

If you haven't heard about quantum computing, it's an alternative to "classical computing" that relies on some strange properties of quantum physics. Sure, the computer (or whatever device) you're reading this on also relies on physics a bit, but it stores information digitally as ones and zeroes -- and not some superposition of two states of matter in an array. A few organizations are working on quantum computers (e.g., Google, NASA, D-Wave, Cambridge Quantum Computing, Yale Quantum Institute, Microsoft, IBM, etc.), but the true potential is still just slightly out of reach (for now). After you've finished checking out those links, take a look at our holiday gift ideas for cool gadgets and other awesome stuff.
Hide this

Thank you for reading this Techdirt post. With so many things competing for everyone’s attention these days, we really appreciate you giving us your time. We work hard every day to put quality content out there for our community.

Techdirt is one of the few remaining truly independent media outlets. We do not have a giant corporation behind us, and we rely heavily on our community to support us, in an age when advertisers are increasingly uninterested in sponsoring small, independent sites — especially a site like ours that is unwilling to pull punches in its reporting and analysis.

While other websites have resorted to paywalls, registration requirements, and increasingly annoying/intrusive advertising, we have always kept Techdirt open and available to anyone. But in order to continue doing so, we need your support. We offer a variety of ways for our readers to support us, from direct donations to special subscriptions and cool merchandise — and every little bit helps. Thank you.

–The Techdirt Team

Filed Under: np hard, operating system, optimization, quantum computers, quantum computing playground, quantum physics, qubits, shor's algorithm
Companies: cambridge quantum computing, d-wave, google, ibm, microsoft, nasa, yale quantum institute


Reader Comments

Subscribe: RSS

View by: Time | Thread


  • identicon
    Lawrence D’Oliveiro, 10 Dec 2015 @ 6:44pm

    I Think These Are Just Analog Computers

    Up to around the middle part of the 20th century, when digital electronics were much slower, there were “analog” computers. These implemented electronic analogs of the physical models they were trying to solve. While being much faster than the digital computers of the time, they also gave much less accuracy (maybe 3-4 significant figures).

    I have a feeling the D-Wave is the same sort of thing. It may be 100 million times than conventional digital electronics, but I don’t think it can match the accuracy of the latter.

    link to this | view in chronology ]

    • icon
      Richard (profile), 11 Dec 2015 @ 2:39am

      Re: I Think These Are Just Analog Computers

      YOu are right - although of course one has to be clear what analog actually means - it DOESN'T mean "continuous" it means "by analogy" as you sort of point out.

      To talk about quantum computers "outperforming" classical computers is of course nonsense. Quantum computers are horrendously difficult to "program" effectively. The entire research community has managed to create a set of algorithms that you can count on the fingers of one hand in the last 20 years.

      What they can do is provide effective simulation for quantum mechanical systems.

      For some reliable - hype free - information look at Scott Aaronson's blog - here:

      http://www.scottaaronson.com/blog/?p=2555

      link to this | view in chronology ]

  • identicon
    Glenn, 10 Dec 2015 @ 7:27pm

    Only one of the "traveling salesmen" is real; any others are imaginary (more like fantasy than virtual). Quantum computing, per se, may turn out to be just as imaginary... but that's science for ya.

    link to this | view in chronology ]

    • icon
      Richard (profile), 11 Dec 2015 @ 2:45am

      Re: Travelling Salesman

      Actually the idea that quantum computing can solve the travelling salesman or other similar problems is a myth mostly propagated by journalists and others with a poor understanding of the subject. Some QC researcher cynically avoid undermining this myth because the myth is good for their funding!

      Famously QC CAN factor big numbers very fast - but that is only because factorisation is NOT one of the general set of problems to which the travelling salesman belongs. Factoring has more structure than NP complete problems and hence is "easier". It is this structure that Shor's algorithm exploits. So I'd say that the final link in the article is misleading rubbish.

      link to this | view in chronology ]

      • icon
        Mason Wheeler (profile), 11 Dec 2015 @ 7:07am

        Re: Re: Travelling Salesman

        Well, there are NP-complete problems and NP-hard problems. NP-complete means (simplified version) that it's very difficult to compute, but easy to verify the right answer once you see it. Factorization belongs to this category: once you have the factors, it's simple arithmetic to verify that they are indeed the factors of the number in question.

        The Traveling Salesman problem, on the other hand, is not easy to verify. It asks which permutation of possible routes the salesman may take is the fastest, and this necessarily requires you to compute every possible permutation of routes (or at least a significant percentage of them, if you're clever enough to find a way to prove some of them can be pruned early) and then see which of them is the shortest. A problem that's very difficult to both compute and verify is called NP-hard, and they're significantly worse than ordinary NP-complete problems.

        link to this | view in chronology ]

        • identicon
          Lawrence D’Oliveiro, 11 Dec 2015 @ 1:14pm

          Re: NP-complete means (simplified version)

          “NP-complete” has to do with the “P = NP” conjecture. NP-complete problems are NP-hard; they just have the additional property that, if any of them can be proven to be of the easier class P (solvable in deterministic polynomial time) instead of NP (solvable in non-deterministic polynomial time), then there is no such thing as a separate class NP, all such problems actually being in class P.

          link to this | view in chronology ]

          • icon
            Mason Wheeler (profile), 14 Dec 2015 @ 6:58am

            Re: Re: NP-complete means (simplified version)

            Yes, I know, but that was a deliberately simplified post for the benefit of people without a background in computer science and complexity theory. :P

            link to this | view in chronology ]

        • icon
          Richard (profile), 17 Dec 2015 @ 7:56am

          Re: Re: Re: Travelling Salesman

          NP-complete means (simplified version) that it's very difficult to compute, but easy to verify the right answer once you see it. Factorization belongs to this category:

          No it doesn't! In this diagram - assuming as most do that the left side is correct:
          https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg

          then factoring is in NP but not in NP complete. You can't use Shor's algorithm to solve 3sat.

          link to this | view in chronology ]

  • identicon
    Anonymous Coward, 10 Dec 2015 @ 7:57pm

    We know you typed the word "yes" in Word. And we're telling you, there's a 50% chance it will come out "no". That's just Microsoft Windows works at the quantum level. Yes, the upgrade is mandatory. (Or maybe no?)

    link to this | view in chronology ]

  • icon
    Coises (profile), 10 Dec 2015 @ 11:21pm

    I have to wonder where this is going...

    This could be just dystopian fantasy, but somehow I suspect that one of the kinds of problems quantum computing will be set to solve will be cracking encryption that is presently computationally unfeasible to break.

    Possibly we’re seeing the first steps toward what will be the end of privacy and security based on mathematics.

    link to this | view in chronology ]

    • identicon
      Fin, 11 Dec 2015 @ 12:23am

      Re: I have to wonder where this is going...

      Anything that has enough power to decrypted keys can create keys as strong, and thanks to data speeds a bigger key aint too much of an issue :)

      link to this | view in chronology ]

      • icon
        Richard (profile), 11 Dec 2015 @ 2:46am

        Re: Re: I have to wonder where this is going...

        Actually not true - but quantum encryption - which is closer to feasible than quantum factoring - also fixes the problem.

        link to this | view in chronology ]

      • identicon
        Anonymous Coward, 11 Dec 2015 @ 10:00am

        Re: Re: I have to wonder where this is going...

        Anything that has enough power to decrypted keys can create keys as strong
        I don't think this is true. Post-quantum cryptography generally involves different algorithms, not just larger keys. Some of the algorithms do have huge keys/signatures, but you can't just switch to a huge RSA key to get security (and I don't know of any reason why a quantum computer would be better at modular exponentiation than a classical one).

        link to this | view in chronology ]

  • identicon
    Anonymous Coward, 11 Dec 2015 @ 1:24am

    Looking forward to the quantum cat vids - i can haz existenz?

    link to this | view in chronology ]

  • identicon
    Rekrul, 11 Dec 2015 @ 10:30am

    Fully working quantum computers already exist. I saw one on the show Scorpion. It's based on a real person's life, they wouldn't just make something like that up...

    link to this | view in chronology ]

  • identicon
    Anonymous Coward, 11 Dec 2015 @ 11:56am

    Like I'm a billionaire...

    sorta.

    link to this | view in chronology ]


Follow Techdirt
Essential Reading
Techdirt Deals
Report this ad  |  Hide Techdirt ads
Techdirt Insider Discord

The latest chatter on the Techdirt Insider Discord channel...

Loading...
Recent Stories

This site, like most other sites on the web, uses cookies. For more information, see our privacy policy. Got it
Close

Email This

This feature is only available to registered users. Register or sign in to use it.