Slashdot Mirror
The Limits of Quantum Computing
The Narrative Fallacy writes "Scott Aaronson has posted a draft of his article from this month's Scientific American on the limitations of quantum computers (PDF) discussing the question: Will quantum computers let us transcend the human condition and become as powerful as gods, or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine? Aaronson says that while a quantum computer could quickly factor large numbers, and thereby break most of the cryptographic codes used on the Internet today, there's reason to think that not even a quantum computer could solve the crucial class of NP-complete problems efficiently. Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics and that this may be a fundamental limitation on technology no different than the second law of thermodynamics or the impossibility of faster-than-light communication."
This really have touched me deeply, specially the ending. Somewhat related to the article and perhaps one day it actually happens.
:
Following by Isaac Asimov
The last question was asked for the first time, half in jest, on May 21, 2061, at a time when humanity first stepped into the light. The question came about as a result of a five dollar bet over highballs, and it happened this way:
Alexander Adell and Bertram Lupov were two of the faithful attendants of Multivac. As well as any human beings could, they knew what lay behind the cold, clicking, flashing face -- miles and miles of face -- of that giant computer. They had at least a vague notion of the general plan of relays and circuits that had long since grown past the point where any single human could possibly have a firm grasp of the whole.
Multivac was self-adjusting and self-correcting. It had to be, for nothing human could adjust and correct it quickly enough or even adequately enough -- so Adell and Lupov attended the monstrous giant only lightly and superficially, yet as well as any men could. They fed it data, adjusted questions to its needs and translated the answers that were issued. Certainly they, and all others like them, were fully entitled to share In the glory that was Multivac's.
For decades, Multivac had helped design the ships and plot the trajectories that enabled man to reach the Moon, Mars, and Venus, but past that, Earth's poor resources could not support the ships. Too much energy was needed for the long trips. Earth exploited its coal and uranium with increasing efficiency, but there was only so much of both.
But slowly Multivac learned enough to answer deeper questions more fundamentally, and on May 14, 2061, what had been theory, became fact.
The energy of the sun was stored, converted, and utilized directly on a planet-wide scale. All Earth turned off its burning coal, its fissioning uranium, and flipped the switch that connected all of it to a small station, one mile in diameter, circling the Earth at half the distance of the Moon. All Earth ran by invisible beams of sunpower.
Seven days had not sufficed to dim the glory of it and Adell and Lupov finally managed to escape from the public function, and to meet in quiet where no one would think of looking for them, in the deserted underground chambers, where portions of the mighty buried body of Multivac showed. Unattended, idling, sorting data with contented lazy clickings, Multivac, too, had earned its vacation and the boys appreciated that. They had no intention, originally, of disturbing it.
They had brought a bottle with them, and their only concern at the moment was to relax in the company of each other and the bottle.
"It's amazing when you think of it," said Adell. His broad face had lines of weariness in it, and he stirred his drink slowly with a glass rod, watching the cubes of ice slur clumsily about. "All the energy we can possibly ever use for free. Enough energy, if we wanted to draw on it, to melt all Earth into a big drop of impure liquid iron, and still never miss the energy so used. All the energy we could ever use, forever and forever and forever."
Lupov cocked his head sideways. He had a trick of doing that when he wanted to be contrary, and he wanted to be contrary now, partly because he had had to carry the ice and glassware. "Not forever," he said.
"Oh, hell, just about forever. Till the sun runs down, Bert."
"That's not forever."
"All right, then. Billions and billions of years. Twenty billion, maybe. Are you satisfied?"
Lupov put his fingers through his thinning hair as though to reassure himself that some was still left and sipped gently at his own drink. "Twenty billion years isn't forever."
"Will, it will last our time, won't it?"
"So would the coal and uranium."
"All right, but now we can hook up each individual spaceship to the Solar Station, and it can go to Pluto and back a million times without ever worrying about fuel. You can't do
Well considering it's rumoured (and probable) that electricity was used and available significantly before its public demonstration, also with radio communications and other groundbreaking technology, one can reasonably predict that a whole lot of people are up to stuff which the public will find out about only when too many other people know how its done. A bit like the situation with audio bugs. Once bugging of meetingrooms and so on became too easy, people just decided to make all the basic tech public so everyone can see how trivial it is and take appropriate precautions when necessary to counter the possibility. But before that, for decades, bugs were tinfoil hat fodder and most people didn't believe in them. People tend only to look behind doors if they have stood there themselves.
I suppose its time for someone to sit on the toilet for a week and come up with a cryptographic algorithm that resists a quantum computer, whatever that happens to be.
Do it yourself, because no one else will do it yourself. [beta blockade 10-17 Feb]
Your idea of "instantly" is confusing. Albeit, physics makes for an amazing computer; the problem lies in constructing the algorithm. Take, for example. a bunch of beads sitting on a counter. Each of these beads is connect by many strings of various lengths. Treat each bead as a waypoint and each string as the length between each waypoint. If I were to take two random beads and pull on them until one of the series of strings became taught, the first set to become taught is automatically the shortest path. Of course, it's best to assume that each string lacks the ability to produce resistance and is infinitesimally small. This system can scale to an infinite number of dimensions and can also allow for the idea of wormholes. It completely lacks a coordinate system as it doesn't need one. Essentially, it's a perfect waypoint-based pathfinding algorithm. The problem is, though, one has to reconstruct it each time. To reclarify my point, physics makes a stupendously efficient computer; but, lacks the programmability of logic-based circuitry.
What day is it? Could you please tell me?
Author here. I thought those who accuse me of drawing a false dichotomy -- between quantum computers as "godlike" on the one hand or a hoax on the other -- might be interested in the following quotes from the actual published article. "although we should not accept the usual hype, in my view it is equally misguided to dismiss quantum computing as science fiction. Instead we should find out what the limits of quantum computers are and what we could really do if we had them." (p. 63) "According to our current understanding, [quantum computers] would provide dramatic speedups for a few problems -- such as breaking the cryptographic codes that are widely used for monetary transactions on the Internet. For other problems, however -- such as playing chess, scheduling airline flights and proving theorems -- evidence now strongly suggests that quantum computers would suffer from many of the same algorithmic limitations as today's classical computers." (p. 63) "If a large, ideal quantum computer would face most of the same limitations as our present-day classical computers do, should the physicists working on the extraordinarily hard task of building even rudimentary quantum computers pack up and go home? I believe the answer is no, for four reasons..." (p. 65) "To some, the apparent limitations of quantum computers might come as a letdown. One can, however, give those same limitations a more optimistic spin. They mean that although certain cryptographic codes could be broken in a world with quantum computers, other codes would probably remain secure..." (p. 69) In short, the precise misconception that I wrote my article to try to combat, is the one I then get accused of! Reading an article can, indeed, provide useful clues about its contents.
Yes, Grover's algorithm is important. As my article discusses, if all you're doing is brute-force search, then Grover's algorithm effectively doubles the size of the instances that you can solve with a given number of steps. But there's a further wrinkle: in practice, people trying to solve difficult optimization problems on a classical computer usually use some sort of local search heuristic, which is much, much faster than brute-force. And while we do have a quantum analogue of local search (called the "quantum adiabatic algorithm"), it's not at all clear how much of a speedup it will give over classical local search on practical instances. Even the square-root speedup of Grover's algorithm might not be achievable in general (on the other hand, it's also conceivable that the speedup could be more than quadratic). If you're interested in this issue, see the original papers on the adiabatic algorithm by Farhi, Goldstone, Gutmann et al., as well as papers by van Dan, Mosca, and Vazirani and by Reichardt about the limitations of the adiabatic algorithm.