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).- A D-Wave quantum computer tested by Google (and hosted by NASA) has been demonstrated to outperform a traditional computer -- at least for one very specific task. Google has been trying to see what it can do with more and more qubits, and it looks like if Google and D-Wave can keep adding more qubits to their system, they might actually get a quantum computer that can beat our old digital computers (without rigging up a contrived test). [url]
- Cambridge Quantum Computing is working on a quantum computer operating system. It's a bit difficult to imagine how an operating system is created when the underlying hardware can potentially be built in numerous (and sometimes unproven) ways. [url]
- Curious folks can play with a virtual 22-qubit quantum computer -- the Quantum Computing Playground (from Google). This demo runs in a browser and just simulates how a quantum computer could work with a scripting language. This isn't going to print "Hello, World!" a gazillion times. [url]
- If you're wondering what quantum computers might be good for, one of the examples is "optimization problems" -- such as a class of math problems that are NP hard, like the traveling salesman problem. Some folks think quantum computing will unlock a breakthrough for artificial intelligence, allowing computers to "brute force" their way into tackling complex problems without having to invent faster and smaller semiconducting chips. (But there's a chance that we'll have to figure out how to invent ways to make more and more qubits?) [url]
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
I Think These Are Just Analog Computers
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 ]
Re: I Think These Are Just Analog Computers
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 ]
[ link to this | view in chronology ]
Re: Travelling Salesman
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 ]
Re: Re: Travelling Salesman
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 ]
Re: NP-complete means (simplified version)
[ link to this | view in chronology ]
Re: Re: NP-complete means (simplified version)
[ link to this | view in chronology ]
Re: Re: Re: Travelling Salesman
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 ]
[ link to this | view in chronology ]
I have to wonder where this is going...
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 ]
Re: I have to wonder where this is going...
[ link to this | view in chronology ]
Re: Re: I have to wonder where this is going...
[ link to this | view in chronology ]
Re: Re: I have to wonder where this is going...
[ link to this | view in chronology ]
Re: Re: Re: I have to wonder where this is going...
[ link to this | view in chronology ]
[ link to this | view in chronology ]
[ link to this | view in chronology ]
Like I'm a billionaire...
[ link to this | view in chronology ]