The Limits of Quantum Computing 228
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."
The last question... (Score:5, Interesting)
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
Re:Seems to me... (Score:5, Interesting)
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.
Protein's fold in real time. (Score:3, Interesting)
They solve the problem in real time (way better than Polynomial), by actually folding.
Therefore either
It is possible to solve NP-complete problems in better than polynomial time. We just have to figure out how. Quantum may be a solution
OR
Protein folding is not NP-complete problem.
Re:Seems to me... (Score:2, Interesting)
Something based on Quantum Cryptography [wikipedia.org] maybe?
NP complete is solved by nature (Score:2, Interesting)
NP completeness is only a problem for us because we don't understand the mechanics of the solution. It is not an unsolvable problem, just one that we don't know how to solve yet.
Re:The last question... (Score:3, Interesting)
Is there a limit? How many times can you go around a circle?
It's cycles all the way back.
Re:NP complete is solved by nature (Score:4, Interesting)
Re:Nothing in between???? (Score:3, Interesting)
If it means "someone who can break physical laws" then it's a non-concept, because the moment you learn of a way (any way!) to break a certain rule, that rule is no longer a "physical law". For example, we used to think that all conductors has resistance, but the first person to manage sending electricity trough a conductor with -zero- loss did not become a "God", instead we adjusted our understanding of physics.
In relative terms, "God-like" means someone who is capable of stuff that you aren't capable of, probably not even close to being capable of.
Compared to a cave-man we are ALREADY god-like. We can fly in the air in large mechanical machines. We can replace the heart of a living human being -- and have him/her live on. We carry devices which enable us to chat with people on the other side of the earth at will. We can travel to the moon. Either one of these would be the domain of Gods to a cave-man.
Compared to us, it's a fair bet that future humans will be god-like. We've changed our explanation-modus though. Earlier, if people saw something incomprehencible, they where likely to go "Magic!" or "God!" or "Prophet!" or such, today many people migth be more likely to go "High-Tech!", people are already accustomed to being surrounded by gadgets that do stuff that they don't really understand.
Re:Stupid much? (Score:1, Interesting)
Hold on there Sherlock. Factoring is definitely not known to be NP complete. For sure it is NP, but it is a strong candidate for a problem that is strictly between P and NP complete. But proving that would mean proving P != NP.
That's the whole premise of the SciAm article: just because a quantum computer can factor in P-time doesn't mean that the entire NP hierarchy is vulnerable to a quantum computer.
Re:As usual (Score:4, Interesting)
Re:NP complete is solved by nature (Score:3, Interesting)
What I believe the GP means is that using electricity as described earlier in the thread would be "poor" in a programmable sense because it would be rather difficult or tedious to recreate the physical maze ("using physics") to solve shortest path problems in a repeatable or generalized manner. In that light, it's clear you already understand this.
Complexity for a good number of types of problems is like a water balloon. You can squish the complexity in one way but it just pops up somewhere else. You can (sometimes) make an O(2) problem O(1) in time by parallelizing the problem with O(1) computers, that is rather than one computer doing V^2 steps have V computers do V steps simultaneously.
As GP described you could set up a network of strings and beads. Then the problem is solvable in O(c) time which is practically speaking instantaneous. Yippee. Now let's do it again for a similar but different problem. We can do it instantly too, right? Well... no. We have to get a lot more strings and beads. And guess what... Reconstructing the network is... O(2) in time (or O(1) in time with O(1) grad students) and O(2) in string.
It's easier to think about this with the string/bead example. But it is exactly the same with the maze and lightning example. If I gave you a new problem set, just how long would it take you to physically create this maze? Now how would this scale? If I gave you a problem set ten times as large, how much time (and material) to create that maze?
This approach may practically speaking be just GREAT for solving this rather specific sort of problem (shortest path through some sort of maze made from nonconducting material filled with air). As such it is indeed cool. But it says absolutely NOTHING about complexity of these sorts of problems in a generalized fashion.
Re:Nothing in between???? (Score:3, Interesting)
Response to an ironic accusation (Score:5, Interesting)
Re:Having actually read the article, a question (Score:1, Interesting)
Re:Response to an ironic accusation (Score:1, Interesting)
--The Happy Smacktard
For other problems... many of the same limits? (Score:3, Interesting)
This moves a huge class of problems from not solvable in less than millions of years to solvable in about one year, which seems like a pretty big impact to me...
I understand that as a complexity scientist, reduction that only halves the exponent of the number of operations is of merely practical importance and therefore barely worthy of notice, but to the rest of the world it could be a Big Deal.
Re:For other problems... many of the same limits? (Score:4, Interesting)