Image: ILLUSTRATION BY DUSAN PETRICIC
In Brief
- Quantum computers would exploit the strange rules of quantum mechanics to process information in ways that are impossible on a standard computer.
- They would solve certain specific problems, such as factoring integers, dramatically faster than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly.
- Exotic alterations to the known laws of physics would allow construction of computers that could solve large classes of hard problems efficiently. But those alterations seem implausible. In the real world, perhaps the impossibility of efficiently solving these problems should be taken as a basic physical principle.
Haggar Physicists Develop ‘Quantum Slacks,’ ” read a headline in the satirical weekly the Onion. By exploiting a bizarre “Schrödinger’s Pants” duality, the article explained, these non-Newtonian pants could paradoxically behave like formal wear and casual wear at the same time. Onion writers were apparently spoofing the breathless articles about quantum computing that have filled the popular science press for a decade.
A common mistake—see for instance the February 15, 2007, issue of the Economist—is to claim that, in principle, quantum computers could rapidly solve a particularly difficult set of mathematical challenges called NP-complete problems, which even the best existing computers cannot solve quickly (so far as anyone knows). Quantum computers would supposedly achieve this feat not by being formal and casual at the same time but by having hardware capable of processing every possible answer simultaneously.
This article was originally published with the title The Limits of Quantum Computers.
Already a Digital subscriber? Sign-in Now
If your institution has site license access, enter here.
See what we're tweeting about
2 Comments
Add CommentSince this article has a section about "Magical Theories", here's a thought: If there is a parallel universe where our NP problems are P problems there and vice versa, on the surface, it might seem that if we can communicate with them, we get them to solve our NP problems and then get them to tell us the solution. However, further examination tells us even if such a universe exists, it would be impossible to communicate with them because our communication which is P here will be NP there! However, if I suppose that there are universes where only a subset of our NP problems are P there, then there is a possibility of communication. Of course, it behooves us to construct how such a universe looks like.
Reply | Report Abuse | Link to thisSince this article mentions prime numbers and their use in cryptology, I had to chime in with something I have known since I was in grade school. (Well updated a little since the TRS80 hadn't been invented yet at that time...)
Reply | Report Abuse | Link to thisIt does not take anything more than a decent home computer, a simple program, and maybe a couple of hours to break many encryptions used today. What seems complex is really simple when you look at the problem from a different point of view.
Brute force (ie. qubits/number crunching) can do the job if you have enough time, but why go to the trouble when the solution has never changed?