×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

The Limits of Quantum Computing

kdawson posted more than 6 years ago | from the floor-wax-and-dessert-topping dept.

Supercomputing 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."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

228 comments

Well...... (0)

Anonymous Coward | more than 6 years ago | (#22473092)

It can fix the NP problem.... but u cant look into the PC case or else its ruined.

Re:Well...... (5, Funny)

Thanshin (1188877) | more than 6 years ago | (#22473118)

It can fix the NP problem.... but u cant look into the PC case or else its ruined.
I blamed the dead cat I found inside.

Re:Well...... (1, Funny)

DigitAl56K (805623) | more than 6 years ago | (#22473282)

I blamed the dead cat I found inside.
Schrödinger's cat, eh?

Pics or it didn't happen! .. maybe!

Another victory for OSS (-1, Offtopic)

Anonymous Coward | more than 6 years ago | (#22473166)

It is totally pointless talking about quantum computers and such when you consider that most of these machines will be running proprietary, closed-source operating systems like Windows. Windows is an inferior operating system that does not scale well, and almost limitless scaling that quantum computing offers would be completely wasted even on Vista's poorly written, bloated and outdated kernel. Even if the clueless, drone-like engineers at Microsoft could figure out how to add scalability on the order required, it would become infected with spyware within minutes.

Where these machines to run an Open Source operating system, such as Ubuntu (Linux), then support for such scalability could be added by the users, as the source would be open to them to modify. What is more, the superior design of Open Source Software means that the computer would operate more efficiently, and be virtually unhackable - the design of the kernel makes it *impossible* for any kind of malware to exist on a Linux system.

Re:Another victory for OSS (1)

Brian Gordon (987471) | more than 6 years ago | (#22473224)

Completely off topic, not to mention wrong. Nearly all of the malware on Windows is stuff that stupid users install willingly.. a stupid user could just as well download a deb/rpm/tarball for a linux smiley toolbar or something and run it (typing in their password at the sudo prompt like hitting OK at UAC).. it's mostly the user's fault, not the OS's.

Re:Another victory for OSS (0)

Anonymous Coward | more than 6 years ago | (#22473772)

YHBT, YHL, HAND.

Re:Another victory for OSS (0)

Anonymous Coward | more than 6 years ago | (#22474590)

it's mostly the user's fault, not the OS's.

Dream on, kid. Users are a pain but the OS makes it easy for them to be so.

TWW

As usual (1)

somersault (912633) | more than 6 years ago | (#22473094)

The truth lies somewhere in between the two extremes..

Re:As usual (4, Funny)

Yetihehe (971185) | more than 6 years ago | (#22473128)

The truth is a superposition of this two, so thruth is quantum. So could quantum computer uncover the truth? A: Maybe.

Re:As usual (3, Insightful)

Brian Gordon (987471) | more than 6 years ago | (#22473244)

Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics
Is this supposed to be informative in any way? Yes, that's one of the angles on the P=NP problem. No, you still haven't made any progress on it so it doesn't matter what you "contend".

Re:As usual (1)

xZgf6xHx2uhoAj9D (1160707) | more than 6 years ago | (#22474028)

It was a bad summary (surprise, surprise). Most of the article was crap, but I quite liked the ending, when he got into relativistic computing. Relativistic computing isn't exactly novel, but he gave a good survey of the problems it (doesn't) solve.

Re:As usual (-1, Flamebait)

Anonymous Coward | more than 6 years ago | (#22474534)

Good job hijacking the thread. Douchebag.

NP complete is solved by nature (2, Interesting)

BadAnalogyGuy (945258) | more than 6 years ago | (#22473578)

When you see an electrical arc, you are seeing Nature taking the path of least resistance between two points. Interestingly, if you build a "maze" which requires the arc to pass around a corner, it does just that. In fact, the arc, given sufficient power, can find its way through a maze. Not only can it solve a maze, it can solve it for the shortest path essentially instantly.

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:NP complete is solved by nature (5, Informative)

kvezach (1199717) | more than 6 years ago | (#22473672)

Shortest path isn't NP-complete; Dijkstra's algorithm can solve shortest path in O(V^2) where V is the number of vertices in the graph.

Maybe you're thinking of the often repeated claim that one can find a Steiner tree (the determination of which is NP-complete) using soap and a physical setup. But that, too [scottaaronson.com], is false.

Kieu tried to find a way to make quantum trickery (in ordinary quantum computers) calculate NP-complete problems (and a lot more) in polynomial time, but his hypercomputation algorithm was later disproved. So just as P = NP in classical computing seems to be very hard to prove or disprove in the general case, so appears its quantum mechanical analog to be, as well. (But as the paper states, some computers using exotic physics could be able to solve NP-complete problems easily; for instance, a time-traveling computer could solve PSPACE-complete problems without much difficulty, and if loop quantum gravity is true, a computer making use of it might be able to solve NP-complete problems as well.)

Re:NP complete is solved by nature (4, Interesting)

Zencyde (850968) | more than 6 years ago | (#22473700)

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.

Re:NP complete is solved by nature (1)

somersault (912633) | more than 6 years ago | (#22473902)

It's been a while since I did information theory and all that, but wouldn't that be the same as going through an array of values and decrementing each one until one reaches zero? Not very efficient. I fail to see how it's an analogy for a decent algorithm.

Re:NP complete is solved by nature (1)

Zencyde (850968) | more than 6 years ago | (#22474170)

I'm merely pointing out that using electricity traveling down a path is a poor idea for a computer as it lacks decent programmability. : )

Re:NP complete is solved by nature (1, Insightful)

somersault (912633) | more than 6 years ago | (#22474372)

I .. fail to see how you can call it 'poor' until you have a better alternative? Electricity moves fast, is portable via batteries, can run at any scale from the power grid level down to the microprocessors.. there is no other mobile medium that we can control that would be better, other than light, other small particles, magnetism.. all would still require electricity in the system to control any mechanical parts or power whatever is generating the particles or forces involved. I'm trying to see your viewpoint but I just can't dismiss something a poor idea unless I know that there are better ways to do the same thing - unless perhaps the idea is life threatening or otherwise stupid, but in this case it's proven to be quite effective so far.

I quit! Sincerely, Fidel Castro (0)

Anonymous Coward | more than 6 years ago | (#22473702)

P.S. - It sure is hot here! Why are all these flames around me? Oh hey, there's Mumia and Saddam!

Re:As usual (1)

caramelcarrot (778148) | more than 6 years ago | (#22473726)

Having read the first part of the paper, it pretty much seems to be a strawman argument against quantum computing by complaining that the popular perception of it is impossible, then so must quantum computing. Bullshit, the real quantum computing that researchers are working on is based on extremely well tested theories and the main reason why it might not work is the difficulty in actually engineering the machine itself with reasonable tolerances.

faster than light first post! (0)

Anonymous Coward | more than 6 years ago | (#22473098)

ha!

Okay Then. (1)

AndGodSed (968378) | more than 6 years ago | (#22473112)

If Quantum Computers are a scientific impossibility, where does that leave us? There is only so much that current architectures can do. Does that mean we will hit the performance barrier and never be able to break through?

Byebye Star Trek future... *sobs*

Re:Okay Then. (4, Funny)

rucs_hack (784150) | more than 6 years ago | (#22473134)

We don't need Quantum computing for a Star Trek futre.

We need a way to disregard or at least completely reinterpret the laws of physics, and do without money, and all get on, and find entire worlds whose populations all conform to some stereotype.

And are green.

Re:Okay Then. (0)

Anonymous Coward | more than 6 years ago | (#22474072)

>>We don't need Quantum computing for a Star Trek futre.

We will need Quantum Torpedos though...

Re:Okay Then. (1)

NoobHunter (1090113) | more than 6 years ago | (#22474298)

I think that at the end of the day, we have to remember that the Laws of Physics and Thermodynamics and all that other good stuff was written with our level of technology. There should probably be an addendum on each one of the laws of science saying "With our current Knowlege and Technology, these laws are accurate." I remember a quote that I heard somewhere at some point that goes "If History is any sort of guide, almost everything we believe to be true is more than likely not. We once thought the world was flat and so on and so forth!"

Re:Okay Then. (1)

Workaphobia (931620) | more than 6 years ago | (#22474632)

Star Trek? Star Trek?! You're looking at the future of computing and using *that* as your measure of success? Have fun getting rid of analog distortions in the audio output of your holograms by "installing recursive algorithms", and try not to be overwhelmed by your AI's unstable recombinant subroutines. You'd best get a second computer, in case someone ties up your first single-tasking one by asking it to compute the last digit of pi. Bonus points if you manage to implement a sane security policy, putting you two steps ahead of any system to ever appear in the future.

Now if you'll excuse me, I'm going to solve string theory by getting all the infinities to cancel each other out.

Short answer (-1, Offtopic)

Anonymous Coward | more than 6 years ago | (#22473116)

or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine?

Answer: Yes, No, Maybe.

Re:Short answer (0, Offtopic)

Thanshin (1188877) | more than 6 years ago | (#22473132)

or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine?



Answer: Yes, No, Maybe.
 
You forgot the CowboyNeal answer.

Seems to me... (4, Insightful)

Smordnys s'regrepsA (1160895) | more than 6 years ago | (#22473154)

What does it matter if it is perfect or not? Seems to me that it is much better than what we're working with now.

If we want to start talking in that tone, well our "micro" processors and new fangled technologies didn't solve the mysteries of the universe, so we should have stuck with computers the size of buildings that have trouble doing more than adding, subtracting, and multiplying. Hell - they were good enough to design the atomic bomb and our space program, and that's good enough for me!


Besides, does anyone seriously think that we'll gain God-Like-Powers from quantum computing? The only God Mode I expect from the computer starts with the phrase 'iddqd'.

Re:Seems to me... (4, Insightful)

mrbluze (1034940) | more than 6 years ago | (#22473212)

Besides, does anyone seriously think that we'll gain God-Like-Powers from quantum computing? The only God Mode I expect from the computer starts with the phrase 'iddqd'.

If I were offered a single magic power over the physical world it would be either invisibility or the ability to see behind walls. If quantum computing means whoever has it can bust all the crypto's in a realistic time (eg: a second or two), then we have a problem, because that group of people will have God Mode when it comes to money, intelligence, all that. Worse is if we don't know they have quantum computing, then all our shit is belong to them.

If quantum computing means they can break a crypto in a month whereas before it took them forever, there is hope in that quantum computing will become prevalent before anyone is able to totally compromise all communications. Of course I'm guessing there is no such agency that can do this yet.

Re:Seems to me... (5, Funny)

Anonymous Coward | more than 6 years ago | (#22473248)

there is No Such Agency that can do this yet
Are you sure?

Re:Seems to me... (4, Interesting)

mrbluze (1034940) | more than 6 years ago | (#22473312)

Are you sure?

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.

Re:Seems to me... (2, Interesting)

Wodin (33658) | more than 6 years ago | (#22473462)

come up with a cryptographic algorithm that resists a quantum computer, whatever that happens to be.


Something based on Quantum Cryptography [wikipedia.org] maybe?

Re:Seems to me... (4, Informative)

kvezach (1199717) | more than 6 years ago | (#22473710)

Or Lamport signatures [wikipedia.org]. Well, for signing, at least.
If all else fails, it's back to the days of number stations and couriers, since symmetric crypto will resist quantum computers fairly well (just double the key size to thwart Grover's algorithm [wikipedia.org]).

Magic Power (1)

asifyoucare (302582) | more than 6 years ago | (#22473790)

If I were offered a single magic power over the physical world it would be either invisibility or the ability to see behind walls.

I'd choose the ability to make other people do as I wish.

Not all encryptions are prime-based (1)

yariv (1107831) | more than 6 years ago | (#22473856)

And I never heard of any way quantum computing will help breaking those "elliptic curves" based encryptions, and I'm not sure what can it do to the D-Log problem.
To me it seems we'll just have to change our encryptions mechanisms.

The last question... (5, Interesting)

siyavash (677724) | more than 6 years ago | (#22473186)

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 THAT on coal and uranium. Ask Multivac, if you don't believe me."

"I don't have to ask Multivac. I know that."

"Then stop running down what Multivac's done for us," said Adell, blazing up. "It did all right."

"Who says it didn't? What I say is that a sun won't last forever. That's all I'm saying. We're safe for twenty billion years, but then what?" Lupov pointed a slightly shaky finger at the other. "And don't say we'll switch to another sun."

There was silence for a while. Adell put his glass to his lips only occasionally, and Lupov's eyes slowly closed. They rested.

Then Lupov's eyes snapped open. "You're thinking we'll switch to another sun when ours is done, aren't you?"

"I'm not thinking."

"Sure you are. You're weak on logic, that's the trouble with you. You're like the guy in the story who was caught in a sudden shower and Who ran to a grove of trees and got under one. He wasn't worried, you see, because he figured when one tree got wet through, he would just get under another one."

"I get it," said Adell. "Don't shout. When the sun is done, the other stars will be gone, too."

"Darn right they will," muttered Lupov. "It all had a beginning in the original cosmic explosion, whatever that was, and it'll all have an end when all the stars run down. Some run down faster than others. Hell, the giants won't last a hundred million years. The sun will last twenty billion years and maybe the dwarfs will last a hundred billion for all the good they are. But just give us a trillion years and everything will be dark. Entropy has to increase to maximum, that's all."

"I know all about entropy," said Adell, standing on his dignity.

"The hell you do."

"I know as much as you do."

"Then you know everything's got to run down someday."

"All right. Who says they won't?"

"You did, you poor sap. You said we had all the energy we needed, forever. You said 'forever.'"

"It was Adell's turn to be contrary. "Maybe we can build things up again someday," he said.

"Never."

"Why not? Someday."

"Never."

"Ask Multivac."

"You ask Multivac. I dare you. Five dollars says it can't be done."

"Adell was just drunk enough to try, just sober enough to be able to phrase the necessary symbols and operations into a question which, in words, might have corresponded to this: Will mankind one day without the net expenditure of energy be able to restore the sun to its full youthfulness even after it had died of old age?

Or maybe it could be put more simply like this: How can the net amount of entropy of the universe be massively decreased?

Multivac fell dead and silent. The slow flashing of lights ceased, the distant sounds of clicking relays ended.

Then, just as the frightened technicians felt they could hold their breath no longer, there was a sudden springing to life of the teletype attached to that portion of Multivac. Five words were printed: INSUFFICIENT DATA FOR MEANINGFUL ANSWER.

"No bet," whispered Lupov. They left hurriedly.

By next morning, the two, plagued with throbbing head and cottony mouth, had forgotten about the incident.

Jerrodd, Jerrodine, and Jerrodette I and II watched the starry picture in the visiplate change as the passage through hyperspace was completed in its non-time lapse. At once, the even powdering of stars gave way to the predominance of a single bright marble-disk, centered.

"That's X-23," said Jerrodd confidently. His thin hands clamped tightly behind his back and the knuckles whitened.

The little Jerrodettes, both girls, had experienced the hyperspace passage for the first time in their lives and were self-conscious over the momentary sensation of inside-outness. They buried their giggles and chased one another wildly about their mother, screaming, "We've reached X-23 -- we've reached X-23 -- we've ----"

"Quiet, children," said Jerrodine sharply. "Are you sure, Jerrodd?"

"What is there to be but sure?" asked Jerrodd, glancing up at the bulge of featureless metal just under the ceiling. It ran the length of the room, disappearing through the wall at either end. It was as long as the ship.

Jerrodd scarcely knew a thing about the thick rod of metal except that it was called a Microvac, that one asked it questions if one wished; that if one did not it still had its task of guiding the ship to a preordered destination; of feeding on energies from the various Sub-galactic Power Stations; of computing the equations for the hyperspacial jumps.

Jerrodd and his family had only to wait and live in the comfortable residence quarters of the ship.

Someone had once told Jerrodd that the "ac" at the end of "Microvac" stood for "analog computer" in ancient English, but he was on the edge of forgetting even that.

Jerrodine's eyes were moist as she watched the visiplate. "I can't help it. I feel funny about leaving Earth."

"Why for Pete's sake?" demanded Jerrodd. "We had nothing there. We'll have everything on X-23. You won't be alone. You won't be a pioneer. There are over a million people on the planet already. Good Lord, our great grandchildren will be looking for new worlds because X-23 will be overcrowded."

Then, after a reflective pause, "I tell you, it's a lucky thing the computers worked out interstellar travel the way the race is growing."

"I know, I know," said Jerrodine miserably.

Jerrodette I said promptly, "Our Microvac is the best Microvac in the world."

"I think so, too," said Jerrodd, tousling her hair.

It was a nice feeling to have a Microvac of your own and Jerrodd was glad he was part of his generation and no other. In his father's youth, the only computers had been tremendous machines taking up a hundred square miles of land. There was only one to a planet. Planetary ACs they were called. They had been growing in size steadily for a thousand years and then, all at once, came refinement. In place of transistors had come molecular valves so that even the largest Planetary AC could be put into a space only half the volume of a spaceship.

Jerrodd felt uplifted, as he always did when he thought that his own personal Microvac was many times more complicated than the ancient and primitive Multivac that had first tamed the Sun, and almost as complicated as Earth's Planetary AC (the largest) that had first solved the problem of hyperspatial travel and had made trips to the stars possible.

"So many stars, so many planets," sighed Jerrodine, busy with her own thoughts. "I suppose families will be going out to new planets forever, the way we are now."

"Not forever," said Jerrodd, with a smile. "It will all stop someday, but not for billions of years. Many billions. Even the stars run down, you know. Entropy must increase."

"What's entropy, daddy?" shrilled Jerrodette II.

"Entropy, little sweet, is just a word which means the amount of running-down of the universe. Everything runs down, you know, like your little walkie-talkie robot, remember?"

"Can't you just put in a new power-unit, like with my robot?"

"The stars are the power-units, dear. Once they're gone, there are no more power-units."

Jerrodette I at once set up a howl. "Don't let them, daddy. Don't let the stars run down."

"Now look what you've done, " whispered Jerrodine, exasperated.

"How was I to know it would frighten them?" Jerrodd whispered back.

"Ask the Microvac," wailed Jerrodette I. "Ask him how to turn the stars on again."

"Go ahead," said Jerrodine. "It will quiet them down." (Jerrodette II was beginning to cry, also.)

Jarrodd shrugged. "Now, now, honeys. I'll ask Microvac. Don't worry, he'll tell us."

He asked the Microvac, adding quickly, "Print the answer."

Jerrodd cupped the strip of thin cellufilm and said cheerfully, "See now, the Microvac says it will take care of everything when the time comes so don't worry."

Jerrodine said, "and now children, it's time for bed. We'll be in our new home soon."

Jerrodd read the words on the cellufilm again before destroying it: INSUFFICIENT DATA FOR A MEANINGFUL ANSWER.

He shrugged and looked at the visiplate. X-23 was just ahead.

VJ-23X of Lameth stared into the black depths of the three-dimensional, small-scale map of the Galaxy and said, "Are we ridiculous, I wonder, in being so concerned about the matter?"

MQ-17J of Nicron shook his head. "I think not. You know the Galaxy will be filled in five years at the present rate of expansion."

Both seemed in their early twenties, both were tall and perfectly formed.

"Still," said VJ-23X, "I hesitate to submit a pessimistic report to the Galactic Council."

"I wouldn't consider any other kind of report. Stir them up a bit. We've got to stir them up."

VJ-23X sighed. "Space is infinite. A hundred billion Galaxies are there for the taking. More."

"A hundred billion is not infinite and it's getting less infinite all the time. Consider! Twenty thousand years ago, mankind first solved the problem of utilizing stellar energy, and a few centuries later, interstellar travel became possible. It took mankind a million years to fill one small world and then only fifteen thousand years to fill the rest of the Galaxy. Now the population doubles every ten years --"

VJ-23X interrupted. "We can thank immortality for that."

"Very well. Immortality exists and we have to take it into account. I admit it has its seamy side, this immortality. The Galactic AC has solved many problems for us, but in solving the problems of preventing old age and death, it has undone all its other solutions."

"Yet you wouldn't want to abandon life, I suppose."

"Not at all," snapped MQ-17J, softening it at once to, "Not yet. I'm by no means old enough. How old are you?"

"Two hundred twenty-three. And you?"

"I'm still under two hundred. --But to get back to my point. Population doubles every ten years. Once this Galaxy is filled, we'll have another filled in ten years. Another ten years and we'll have filled two more. Another decade, four more. In a hundred years, we'll have filled a thousand Galaxies. In a thousand years, a million Galaxies. In ten thousand years, the entire known Universe. Then what?"

VJ-23X said, "As a side issue, there's a problem of transportation. I wonder how many sunpower units it will take to move Galaxies of individuals from one Galaxy to the next."

"A very good point. Already, mankind consumes two sunpower units per year."

"Most of it's wasted. After all, our own Galaxy alone pours out a thousand sunpower units a year and we only use two of those."

"Granted, but even with a hundred per cent efficiency, we can only stave off the end. Our energy requirements are going up in geometric progression even faster than our population. We'll run out of energy even sooner than we run out of Galaxies. A good point. A very good point."

"We'll just have to build new stars out of interstellar gas."

"Or out of dissipated heat?" asked MQ-17J, sarcastically.

"There may be some way to reverse entropy. We ought to ask the Galactic AC."

VJ-23X was not really serious, but MQ-17J pulled out his AC-contact from his pocket and placed it on the table before him.

"I've half a mind to," he said. "It's something the human race will have to face someday."

He stared somberly at his small AC-contact. It was only two inches cubed and nothing in itself, but it was connected through hyperspace with the great Galactic AC that served all mankind. Hyperspace considered, it was an integral part of the Galactic AC.

MQ-17J paused to wonder if someday in his immortal life he would get to see the Galactic AC. It was on a little world of its own, a spider webbing of force-beams holding the matter within which surges of sub-mesons took the place of the old clumsy molecular valves. Yet despite it's sub-etheric workings, the Galactic AC was known to be a full thousand feet across.

MQ-17J asked suddenly of his AC-contact, "Can entropy ever be reversed?"

VJ-23X looked startled and said at once, "Oh, say, I didn't really mean to have you ask that."

"Why not?"

"We both know entropy can't be reversed. You can't turn smoke and ash back into a tree."

"Do you have trees on your world?" asked MQ-17J.

The sound of the Galactic AC startled them into silence. Its voice came thin and beautiful out of the small AC-contact on the desk. It said: THERE IS INSUFFICIENT DATA FOR A MEANINGFUL ANSWER.

VJ-23X said, "See!"

The two men thereupon returned to the question of the report they were to make to the Galactic Council.

Zee Prime's mind spanned the new Galaxy with a faint interest in the countless twists of stars that powdered it. He had never seen this one before. Would he ever see them all? So many of them, each with its load of humanity - but a load that was almost a dead weight. More and more, the real essence of men was to be found out here, in space.

Minds, not bodies! The immortal bodies remained back on the planets, in suspension over the eons. Sometimes they roused for material activity but that was growing rarer. Few new individuals were coming into existence to join the incredibly mighty throng, but what matter? There was little room in the Universe for new individuals.

Zee Prime was roused out of his reverie upon coming across the wispy tendrils of another mind.

"I am Zee Prime," said Zee Prime. "And you?"

"I am Dee Sub Wun. Your Galaxy?"

"We call it only the Galaxy. And you?"

"We call ours the same. All men call their Galaxy their Galaxy and nothing more. Why not?"

"True. Since all Galaxies are the same."

"Not all Galaxies. On one particular Galaxy the race of man must have originated. That makes it different."

Zee Prime said, "On which one?"

"I cannot say. The Universal AC would know."

"Shall we ask him? I am suddenly curious."

Zee Prime's perceptions broadened until the Galaxies themselves shrunk and became a new, more diffuse powdering on a much larger background. So many hundreds of billions of them, all with their immortal beings, all carrying their load of intelligences with minds that drifted freely through space. And yet one of them was unique among them all in being the originals Galaxy. One of them had, in its vague and distant past, a period when it was the only Galaxy populated by man.

Zee Prime was consumed with curiosity to see this Galaxy and called, out: "Universal AC! On which Galaxy did mankind originate?"

The Universal AC heard, for on every world and throughout space, it had its receptors ready, and each receptor lead through hyperspace to some unknown point where the Universal AC kept itself aloof.

Zee Prime knew of only one man whose thoughts had penetrated within sensing distance of Universal AC, and he reported only a shining globe, two feet across, difficult to see.

"But how can that be all of Universal AC?" Zee Prime had asked.

"Most of it, " had been the answer, "is in hyperspace. In what form it is there I cannot imagine."

Nor could anyone, for the day had long since passed, Zee Prime knew, when any man had any part of the making of a universal AC. Each Universal AC designed and constructed its successor. Each, during its existence of a million years or more accumulated the necessary data to build a better and more intricate, more capable successor in which its own store of data and individuality would be submerged.

The Universal AC interrupted Zee Prime's wandering thoughts, not with words, but with guidance. Zee Prime's mentality was guided into the dim sea of Galaxies and one in particular enlarged into stars.

A thought came, infinitely distant, but infinitely clear. "THIS IS THE ORIGINAL GALAXY OF MAN."

But it was the same after all, the same as any other, and Zee Prime stifled his disappointment.

Dee Sub Wun, whose mind had accompanied the other, said suddenly, "And Is one of these stars the original star of Man?"

The Universal AC said, "MAN'S ORIGINAL STAR HAS GONE NOVA. IT IS NOW A WHITE DWARF."

"Did the men upon it die?" asked Zee Prime, startled and without thinking.

The Universal AC said, "A NEW WORLD, AS IN SUCH CASES, WAS CONSTRUCTED FOR THEIR PHYSICAL BODIES IN TIME."

"Yes, of course," said Zee Prime, but a sense of loss overwhelmed him even so. His mind released its hold on the original Galaxy of Man, let it spring back and lose itself among the blurred pin points. He never wanted to see it again.

Dee Sub Wun said, "What is wrong?"

"The stars are dying. The original star is dead."

"They must all die. Why not?"

"But when all energy is gone, our bodies will finally die, and you and I with them."

"It will take billions of years."

"I do not wish it to happen even after billions of years. Universal AC! How may stars be kept from dying?"

Dee sub Wun said in amusement, "You're asking how entropy might be reversed in direction."

And the Universal AC answered. "THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER."

Zee Prime's thoughts fled back to his own Galaxy. He gave no further thought to Dee Sub Wun, whose body might be waiting on a galaxy a trillion light-years away, or on the star next to Zee Prime's own. It didn't matter.

Unhappily, Zee Prime began collecting interstellar hydrogen out of which to build a small star of his own. If the stars must someday die, at least some could yet be built.

Man considered with himself, for in a way, Man, mentally, was one. He consisted of a trillion, trillion, trillion ageless bodies, each in its place, each resting quiet and incorruptible, each cared for by perfect automatons, equally incorruptible, while the minds of all the bodies freely melted one into the other, indistinguishable.

Man said, "The Universe is dying."

Man looked about at the dimming Galaxies. The giant stars, spendthrifts, were gone long ago, back in the dimmest of the dim far past. Almost all stars were white dwarfs, fading to the end.

New stars had been built of the dust between the stars, some by natural processes, some by Man himself, and those were going, too. White dwarfs might yet be crashed together and of the mighty forces so released, new stars build, but only one star for every thousand white dwarfs destroyed, and those would come to an end, too.

Man said, "Carefully husbanded, as directed by the Cosmic AC, the energy that is even yet left in all the Universe will last for billions of years."

"But even so," said Man, "eventually it will all come to an end. However it may be husbanded, however stretched out, the energy once expended is gone and cannot be restored. Entropy must increase to the maximum."

Man said, "Can entropy not be reversed? Let us ask the Cosmic AC."

The Cosmic AC surrounded them but not in space. Not a fragment of it was in space. It was in hyperspace and made of something that was neither matter nor energy. The question of its size and Nature no longer had meaning to any terms that Man could comprehend.

"Cosmic AC," said Man, "How many entropy be reversed?"

The Cosmic AC said, "THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER."

Man said, "Collect additional data."

The Cosmic AC said, "I WILL DO SO. I HAVE BEEN DOING SO FOR A HUNDRED BILLION YEARS. MY PREDECESSORS AND I HAVE BEEN ASKED THIS QUESTION MANY TIMES. ALL THE DATA I HAVE REMAINS INSUFFICIENT."

"Will there come a time," said Man, "when data will be sufficient or is the problem insoluble in all conceivable circumstances?"

The Cosmic AC said, "NO PROBLEM IS INSOLUBLE IN ALL CONCEIVABLE CIRCUMSTANCES."

Man said, "When will you have enough data to answer the question?"

"THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER."

"Will you keep working on it?" asked Man.

The Cosmic AC said, "I WILL."

Man said, "We shall wait."

"The stars and Galaxies died and snuffed out, and space grew black after ten trillion years of running down.

One by one Man fused with AC, each physical body losing its mental identity in a manner that was somehow not a loss but a gain.

Man's last mind paused before fusion, looking over a space that included nothing but the dregs of one last dark star and nothing besides but incredibly thin matter, agitated randomly by the tag ends of heat wearing out, asymptotically, to the absolute zero.

Man said, "AC, is this the end? Can this chaos not be reversed into the Universe once more? Can that not be done?"

AC said, "THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER."

Man's last mind fused and only AC existed -- and that in hyperspace.

Matter and energy had ended and with it, space and time. Even AC existed only for the sake of the one last question that it had never answered from the time a half-drunken computer ten trillion years before had asked the question of a computer that was to AC far less than was a man to Man.

All other questions had been answered, and until this last question was answered also, AC might not release his consciousness.

All collected data had come to a final end. Nothing was left to be collected.

But all collected data had yet to be completely correlated and put together in all possible relationships.

A timeless interval was spent in doing that.

And it came to pass that AC learned how to reverse the direction of entropy.

But there was now no man to whom AC might give the answer of the last question. No matter. The answer -- by demonstration -- would take care of that, too.

For another timeless interval, AC thought how best to do this. Carefully, AC organized the program.

The consciousness of AC encompassed all of what had once been a Universe and brooded over what was now Chaos. Step by step, it must be done.

And AC said, "LET THERE BE LIGHT!"

And there was light----

Re:The last question... (3, Insightful)

sqrt(2) (786011) | more than 6 years ago | (#22473250)

Not the first time I've read this, and I'm sure most people here are already familiar with it along with Asimov's other works.

The obvious question would then be, that if all existence is cyclical, how many times has it been reset? And, what kicked it off to begin with? The biblical tie in is a convenient reconciliation of science and (mostly Christian creation myth) religion, but it's a cheat. It doesn't actually answer any questions at all. It is something interesting to think about though.

Re:The last question... (5, Funny)

z0idberg (888892) | more than 6 years ago | (#22473514)

The obvious question would then be, that if all existence is cyclical, how many times has it been reset? And, what kicked it off to begin with?

I don't think there is sufficient data to give a meaningful answer to these questions.

Re:The last question... (2, Interesting)

Jamu (852752) | more than 6 years ago | (#22473596)

The obvious question would then be, that if all existence is cyclical, how many times has it been reset?

Is there a limit? How many times can you go around a circle?

And, what kicked it off to begin with?

It's cycles all the way back.

Re:The last question... (0)

Anonymous Coward | more than 6 years ago | (#22473640)

Is the journey from begining to end to beginning always the same, or is their slight variations, or something completly different?

Re:The last question... (0)

Anonymous Coward | more than 6 years ago | (#22473870)

Don't you see? In the story, there is no God. None at all whatsoever. Even the God-like is not God. If it is a reconciliation, it is one that ends in the demise of the fundamental premise of religion. There is your answer.

Re:The last question... (0)

Anonymous Coward | more than 6 years ago | (#22474078)

I think what you should take away from this story is that Assimov thought the sun would last for 20 billion years and that we would still be burning massive amounts of coal in 2061. You have no idea what the future will bring, especially 100 years from now. We, today might not be able to design a viable quantum computer but our great-grandchildren will probably be solving NP problems for junior year math homework.

The gods (0, Flamebait)

courteaudotbiz (1191083) | more than 6 years ago | (#22473188)

Will quantum computers let us transcend the human condition and become as powerful as gods
You Americans always have to talk about god somewhere. Even when talking about computers.

Re:The gods (1)

phoenixwade (997892) | more than 6 years ago | (#22473956)

You Americans always have to talk about god somewhere. Even when talking about computers.
Well either "She's important to us", "Pasta is universally applicable in technical conversation", or "The Computer IS god, you infidel"

Nothing in between???? (4, Insightful)

syousef (465911) | more than 6 years ago | (#22473200)

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?

No, they won't let us defy physical laws and become omnipotent. No, quantum mechanics, being a whole class of physical laws, isn't going to have absolutely no practical use. How about something in between that doesn't come from the over-used plot of a bad sci-fi show?

Re:Nothing in between???? (2, Interesting)

Eivind (15695) | more than 6 years ago | (#22473842)

The term "God-like" is a relative term. Either that or it's nonsensical.

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.

I think the parent is being facetious, no? (1)

MrKane (804219) | more than 6 years ago | (#22473252)

..in order to draw attention to the actual maths problems for which quantum computational methods are one of many.
Evangelising, one might say?

Sorry haven't RTFA, but I'm guessing it's written as an explaination as to what type of problem quantum computation aim at solving, and is written for the lay person, and not for those who already study it, who probably already have a good idea. ;?)

Protein's fold in real time. (3, Interesting)

RationalRoot (746945) | more than 6 years ago | (#22473368)

Afair Protein folding is an NP-complete problem.

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:Protein's fold in real time. (2, Insightful)

snkline (542610) | more than 6 years ago | (#22473562)

You are confused as to what NP-complete means. It isn't that a protein folding is "NP-complete", but the algorithm for generally calculating protein folding is.

Re:Protein's fold in real time. (1)

RationalRoot (746945) | more than 6 years ago | (#22473644)

It's a while since I covered any of this in detail, so I could well be way off, but if all proteins fold in real time, there is a solution to the problem which can be "calculated" in real time for all proteins. If you take algorithm in the most general sense, then your algorithm is "watch the protein fold", then your algorithm is better than NPC. I do not see how this is any different than set up the following electrical charges in a peice of silicon and see what happens. You have a problem (possibly NPC), and a solution that you can find in real time. If you mean that there is a more general class of folding that is NPC and any protein that actually esists and folds is not part of that general problem, then you have moved beyond my understanding of protein folding.

Re:Protein's fold in real time. (1)

snkline (542610) | more than 6 years ago | (#22473728)

A problem that is NP-complete is simply an problem that is NP, for which a solving algorithm is generally applicable to all other NP problems. That is why the P = NP question is so important. So, lets step back abit to the superset of NPC and P, NP, since that is really what you are arguing is that if a protein can fold in real time, the protein folding problem isn't in NP, not just NPC.
This is where you make your mistake, the protein folding problem can be summarized as: What are the valid ways for a protein to fold? This is NP if it can be solved in polynomial time by a non-deterministic Turing machine. More importantly, for the problem to be in NP, the question: "Given *folded structure*, prove it was reachable from *unfolded structure*" must be solvable in polynomial time by a deterministic Turing machine (in other words the second question must be in P). You are using the second question (the fact that proteins do fold certain ways), which is not the protein folding problem. I hope that makes sense, it has been a decade since my CS theory classes, and I've never studied protein folding, but I'm pretty sure what I wrote above is fairly accurate, feel free to correct any errors I made.

Stupid much? (1, Informative)

SoapBox17 (1020345) | more than 6 years ago | (#22473396)

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.
Quantum computers have already proven they can do factoring (which is an NP-complete problem) in polynomial time. We know for sure that this is not a "violation of the laws of physics," because it has already been done!

Re:Stupid much? (5, Informative)

Anonymous Coward | more than 6 years ago | (#22473448)

No no no. Factoring is not NP-complete. Sure, its in NP since you can verify a factoring in polynomial time. But the complete part is kind of important, here! Go read a book on complexity theory :)

Re:Stupid much? (1)

TubeSteak (669689) | more than 6 years ago | (#22473494)

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.
Efficiently seems to be the key word there.
I'm not sure exactly what that means in this context, but does that mean there is an inefficient way to go about it?

Re:Stupid much? (1)

yariv (1107831) | more than 6 years ago | (#22473982)

Integer factorization isn't NP-complete. It is known to be NP, of course, and isn't known to be P, but it is not known to be NP-hard. It means that, unlike NP-complete problems, solving it in polynomial time won't give you a general algorithm for solving any NP problem in polynomial time (so, it doesn't mean P=NP). Integer factorization might be in P or out of it (as long as P!=NP, of course), and this is as correct for quantum computers as it is for normal ones.

Re:Stupid much? (0)

Anonymous Coward | more than 6 years ago | (#22474056)

This comment is incorrect and misleading. Factoring is not NP-complete! The quoted text is more or less an accurate statement of one of the hypotheses put forth by Aaronson in the article.

Re:Stupid much? (1, Interesting)

Anonymous Coward | more than 6 years ago | (#22474550)

Quantum computers have already proven they can do factoring (which is an NP-complete problem) in polynomial time.

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.

Having actually read the article, a question (1)

Kupfernigk (1190345) | more than 6 years ago | (#22473432)

I know this is a no-no for Slashdot, but I have one thought and one question.

The thought is that this is a sober and sensible article, free of hype, and does us all a favor. Thanks.

The question is this. In the article, Scott describes an imaginary quantum computer with 1000 electrons that can be spin up or spin down. I do not understand how this is different from the following conventional silicon scenario:

Imagine 1000 DRAM cells in a matrix. Each one consists, basically, of an insulated gate MOSFET. The charge between the gate and the source determines whether it is off or on, 1 or 0.
Now leave it alone for a while. Charge leakage causes the gates to drift to around the threshold voltage.
If you then bombarded the DRAM with low intensity UV light, some of the cells would switch states.
As a result, if you read out the states of the cells, some would read 1 and some would be 0.

How is this different from the quantum computer version? Again we seem to have a Schroedinger's Cat situation in which, until we connect to the drain lines, we do not know the state of the bits. There are 1000 of them, therefore the value when read is any one of 2^1000 values.

I know I am missing something important here, but nobody is explaining to me what feature it is of the electron array gedanken experiment that is different from the DRAM array, and enables it to do computation. Can anybody point to a clear explanation?

Re:Having actually read the article, a question (3, Informative)

QuantumG (50515) | more than 6 years ago | (#22473510)

http://en.wikipedia.org/wiki/Quantum_computer [wikipedia.org]

and lay off the trolling.

What an rude person you are (1)

Kupfernigk (1190345) | more than 6 years ago | (#22473958)

Other people managed to post polite and helpful explanations, as a result of which, I now get it. You appear to suffer a slight misconception about the clarity of quality of many articles on Wikipedia. Not all of us are quantum physicists, some of us are interested enough to read an article in Scientific American and want to know a bit more, but not with the implication of wading through pages of prose that badly needs editing.

Is there nothing you yourself know little about but would like your curiosity satisfied without becoming an expert? Or do you just have personal issues? I suspect the latter.

Re:Having actually read the article, a question (1)

badfish99 (826052) | more than 6 years ago | (#22473520)

The difference is that, in a classical system such as your DRAM array, the state of the cells before we read them is either 0 or 1: we just don't happen to know which. The switching between states happens at the time when the UV light hits the cell.

In the case of the electron, when we read the spin we always get either "up" or "down", but if we read "up" this doesn't mean that the spin was "up" immediately before we read it. Instead, the electron was in a weird condition where its spin was a mixture of "up" and "down", and the switching into a definite state only happens when we measure the state.

Re:Having actually read the article, a question (1)

00_NOP (559413) | more than 6 years ago | (#22473522)

Well, because in the quantum scenario the electrons would be in all the states at once (well, there would be a probablistic spread) while in the silcon one they would only ever be in the final state regardless of whether you'd actually measured them or not.

Granted, I didn't really grasp the point about how you collapse the probablistic distribution to the correct state unless you have a lot of these 1,000 electron computers. maybe somebody else could explain that? It's more than 20 years since I did the undergrad QM stuff.

Re:Having actually read the article, a question (5, Informative)

IWannaBeAnAC (653701) | more than 6 years ago | (#22473566)

The (fundamental) difference is that the bits in the DRAM cells are in a well-defined state of either 0 or 1, but you just haven't measured them yet. In the quantum computer, the qubits are in a superposition of 0 and 1 at the same time.

To be more precise, the 'state space' of a classical bit is, well, 1 bit. Either 0 or 1. In the scenario that you describe, you don't know what the bits are until you measure them, but that is nothing special (imagine another example: tossing a coin with your eyes closed. You don't know the outcome until you open your eyes, but that doesn't mean that anything quantum-mechanical is going on!).

The 'state space' of a qubit, on the other hand, is an angle. Put the '0' result along the x axis and the '1' result along the y axis. Angle 0 corresponds to '0', 90 degrees corresponds to '1', and so on. But the possible physical state is anywhere on the unit circle, not just '0' and '1'. If the physical state of the system is 45 degrees then it really is a mixture of '0' and '1', and you can do interesting things with this state. For example, you can add it to some other state (at a different angle) and get wave-like interference effects.

Re:Having actually read the article, a question (1)

Kupfernigk (1190345) | more than 6 years ago | (#22473846)

Thanks.

For some weird reason, someone else (above) accused me of trolling. However, IANA quantum physicist (obviously) and I actually wanted clarification on this point. You have provided it, and I will now slink off suitably ashamed of my ignorance.

On the other hand, now I think about it, why is it trolling on /. to admit to ignorance? "Read Wikipedia" is NOT the answer to everything.

NP-completeness (-1)

Peaker (72084) | more than 6 years ago | (#22473446)

NP-completeness relates to the scalability of the algorithm with the size of the input.
As far as I know, Quantum computers "solve" NP-complete questions in "Polynomial time" (actually constant time?), but they also limit the size of the input significantly.

Since Quantum Computers seem to run on inputs of a specific size, O() notation does not seem to apply at all. The input has a constant size, and the computation is bound by some constant time.

So "solving" NP-complete problems cannot really violate laws of physics in this sense.

Re:NP-completeness (1)

IWannaBeAnAC (653701) | more than 6 years ago | (#22473574)

What a load of nonsense! And it gets modded +3 ! Instead of sprouting "as far as I know" rubbish, why don't you RTFA, and you will learn that everything that you said in your post is wrong?

Re:NP-completeness (4, Insightful)

Trivial_Zeros (1058508) | more than 6 years ago | (#22473660)

The input has a constant size, and the computation is bound by some constant time.
If you want to be technical like that, your current computer is a finite state machine (it doesn't even support true Turing algorithms as these in the general case require an infinite tape). Any input/output to computations is bounded by the size of your cache, memory and disk space. You could try and say that net access grants more storage, but this is still technically a) finite and b) bound by low seek times.

The first generation of computers had low storage / computation space. They grew as engineering progressed. It's the same deal with quantum computers. Five to seven qbits today may turn into 32, 64.. and larger. A quantum computer with "only" 512 qbits could be solving a problem that would normally require 2^512 = 10^154 work (which is more atoms in the universe) is amazing.

Re:NP-completeness (0)

Anonymous Coward | more than 6 years ago | (#22473912)

It's a common misconception that quantum computers can solve NP-complete problems. Integer factorization is NOT an NP-complete problem, though it is in NP. To quote Wikipedia, the class of problems quantum computers solve is "suspected to be disjoint from NP-complete and a strict superset of P."

http://en.wikipedia.org/wiki/Quantum_computer [wikipedia.org]

Re:NP-completeness (1)

yariv (1107831) | more than 6 years ago | (#22474150)

Every physical computer is finite, if it is a quantum or regular one, O() notation is used only in theory. All practical problems are of finite size, however, and the O() notation is a good estimation for the size of problem a given computer can solve. If a 1K q-bits quantum computer is capable of solving problems a 1TB regular computer can, due to the fact it needs only as many q-bits as the input size, not 2^(input size), it is good enough for me.

Re:NP-completeness (0)

Anonymous Coward | more than 6 years ago | (#22474272)

Quantum computers run on inputs of a specific size? Huh? Aaronson is talking about theoretical quantum computing (i.e., quantum computers which could run on inputs of any size), not about the extremely limited quantum computers which have so far been built.

Re:NP-completeness (5, Informative)

xZgf6xHx2uhoAj9D (1160707) | more than 6 years ago | (#22474400)

What the fuck?! I would outraged when this was at +4, but +5?!

NP-completeness relates to the scalability of the algorithm with the size of the input.

This is misleading. NP-completeness relates to how other problems can be reduced to it. Currently we can't say much about how NP-completeness and complexity relate. We know that if a problem is NP-complete, it must take at least polynomial time and at most exponential time (on a classical computer), but beyond that, we know nothing.

Quantum computers "solve" NP-complete questions in "Polynomial time"

This is factually incorrect. So far we have not found a quantum algorithm to solve any NP-complete problem in less than exponential time.

(actually constant time?)

Ha!

they also limit the size of the input significantly.

This is factually incorrect. Perhaps you're getting confused by the fact that quantum algorithms are often described in circuit notation. Classical algorithms are also sometimes described in circuit notation, but this is much less common. In any case, quantum algorithms do not bound the size of the input any more than classical computers do.

For instance, quicksort on a classical computer might be "bounded" in that you cannot sort an array of 50 billion petabytes. This is not inherent in the algorithm; it's inherent in our inability to construct a computer with 50 billion petabytes of memory. Similarly, we have not been able to use quantum computers to date to factor integers larger than 15. This limit is not inherent in the algorithm; it's inherent in the fact that engineers have not been able to construct a viable quantum computer to date with more than 5 (if I remember correctly) qubits.

Again, quantum algorithms to not bound the size of their input.

Since Quantum Computers seem to run on inputs of a specific size, O() notation does not seem to apply at all.

This is factually incorrect. Almost all of the research into quantum computation in the past 10 years has been in the area of quantum complexity. Perhaps you have heard of the BQP complexity class [wikipedia.org], which was mentioned in the article you were supposed to have read. By the way, BQP can in some way be thought of as quantum computers' "P"; i.e., the class of problems which can viably be computed on a quantum computer in polynomial time.

Quantum complexity very much uses big-O notation (as well as big- notation and any other complexity notation used in classical complexity theory).

So "solving" NP-complete problems cannot really violate laws of physics in this sense.

Non sequitur. It's not clear at this point. If you could answer that question, you'd probably be drowning in money right now.

Guess I am one of the few who has RTFA (1)

00_NOP (559413) | more than 6 years ago | (#22473504)

...but could someone else who has explain the final par to me? Does he mean God will reveal the solution? Or have i just missed something obvious?

Re:Guess I am one of the few who has RTFA (0)

Anonymous Coward | more than 6 years ago | (#22474094)

He means that, if the "many worlds interpretation" of quantum physics is true, you'll only continue to exist in universes where you've got the answer to you problem, therefore it will be "solved".

Of course, in a very large part of all the universes, you'll just end up dead, but that won't matter to you.

Re:Guess I am one of the few who has RTFA (1)

00_NOP (559413) | more than 6 years ago | (#22474244)

well spotted Batperson.

Have to say I'd never have sussed it for that, but now you say so it is obviously correct.

Am I Missing Something Here? (1)

Comatose51 (687974) | more than 6 years ago | (#22473594)

From the summary:

"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."

I don't know much about Quantum Computing and it's been a while since I've studied algorithms and computability. However, NP-complete is an algorithm and complexity question, not necessarily one of speed and computation time. Even if your hardware is different, it doesn't mean you can solve the problem the polynomial time, unless your hardware can scale the same way as the problem itself. Can quantum computers just scale like that? Just because a problem is NP-complete doesn't mean it's unsolvable or can't be solved in a reasonable amount of time. If the dataset is small enough, they can be solved quite quickly. The problem is one of scaling and unless a quantum computer can scale the same way a NP-complete problem can scale in complexity, it won't solve them in polynomial time.

Take this as a question, not as a statement. Maybe someone can enlighten me on on this.

Oh who cares! (0)

Anonymous Coward | more than 6 years ago | (#22473628)

Physics doesn't exist at that scale! IT'S A LIE!!

Damn you science!

So uh, where do the wires go? (1)

LM741N (258038) | more than 6 years ago | (#22473688)

Any miniature electronic device is going to need fanout. Thats where the microscopic bond wires attach to lead frames which are soldered in the real world of motherboard, etc. How the hell do you go from a nanometer pad to a leadframe. What about current? Can you expect to run an amp through a nm wire? All of this doesn't seem very practical. But add the prefix "nano" to any wacky scheme these days and you get funding. Just like colloidal silver.The FDA said it was dangerous and didn't kill anything. Now they call it nanosilver and its the miracle disinfectant of the millenium, so powerful that the EPA is worried that waste water plants will get their bacteria killed off. I guess you just follow the money.

Re:So uh, where do the wires go? (1)

Jaysyn (203771) | more than 6 years ago | (#22474052)

Colloidal silver *is* dangerous in constant or high doses. It's a heavy metal that you are putting in your body after all. On the other hand it will kill the shit out of bacteria. I've used a diluted colloidal silver throat spray before to treat strep & it literally works in minutes. I thought it was snake oil too, before I tried it.

Re:So uh, where do the wires go? (1)

LM741N (258038) | more than 6 years ago | (#22474306)

I know that. Peoples' skin turns blueish grey. Silver wouldn't normally be absorbed into the body except for bacteria which conjugate it and it passes though the intestinal wall. From there is naturally migrates so the skin where some photochemical reaction makes it bluish grey.

Theory need not reflect reality (1)

Eukariote (881204) | more than 6 years ago | (#22473742)

The proposals and attempts at quantum computing are based on predictions made using quantum theory. But how well does quantum theory reflect reality? There is good reason to seriously question that, and by implication, question the fundamental feasibility of quantum computing.

The first problem with quantum theory is that the mathematical formalism leaves a lot of leeway in how to interpret it. There are many interpretations of it http://en.wikipedia.org/wiki/Interpretation_of_quantum_mechanics [wikipedia.org]. These mostly do not yield different predictions for the domain in which the theory has been matched with experiment. But they imply very different realities, and sometimes do yield different predictions for less basic phenomena, including the phenomena that are supposed to make quantum computing feasible.

The second problem is that quantum theory has made basic predictions that have been experimentally falsified. Specifically, quantum theory has yielded a very definite description of the ground state of atomic hydrogen. It is called the ground state because no lower energy levels are possible, within the framework of quantum theory. But such lower energy levels are exactly what has been observed experimentally in the past 15 years, in many different experiments. This one, for example: http://arxiv.org/ftp/physics/papers/0509/0509127.pdf [arxiv.org]

Given these problems, I view quantum computing with great skepticism.

Re:Theory need not reflect reality (1)

FooAtWFU (699187) | more than 6 years ago | (#22474074)

The proposals and attempts at quantum computing are based on predictions made using quantum theory. But how well does quantum theory reflect reality? There is good reason to seriously question that, and by implication, question the fundamental feasibility of quantum computing.

Quantum mechanics encompasses a variety of related theories, and some of those are very solid indeed. Wave-particle duality, the Heisenberg uncertainty principle, quantum state, interference, entanglement... These standbys of quantum computing are going nowhere. The underlying causes and specifics of energy states of hydrogen atoms that they predict may not yet be completely understood, but there's more than enough right now to build a few quantum number-crunchers off of.

Re:Theory need not reflect reality (1)

Eukariote (881204) | more than 6 years ago | (#22474560)

Quantum mechanics encompasses a variety of related theories, and some of those are very solid indeed.

The mathematical formalism may be very solid, but that does not imply that reality is like that. Only experiment can show how well theory reflects reality. And there is no such thing as proof by experiment since there always remain domains in which no experiment has tested the theory yet.

Let's take the Heisenberg uncertainty principle (HUP) you mention as an example. It can be derived from the commutation relations of operators (e.g.the position and momentum operators) used in quantum theory. Fine. But how well has it been tested experimentally? Consider the difficulty of that experiment. And consider that the experiments that have been done and are said to show aspects of the HUP were interpreted within the broader context of quantum theory. Will an interpretation of the same experimental data within the context of a different theory still be considered a validation of the HUP?

Does quantum computing create quantum errors (1)

LM741N (258038) | more than 6 years ago | (#22474080)

Errors so small that you would never be able to find them, yet they show up on the macro scale due to the zillions of calculations involved.

The last paragraph (0)

Anonymous Coward | more than 6 years ago | (#22474292)

Fascinating article, but I really don't understand how the last paragraph works:

"Of course, there is one fast and reliable method to solve NP-complete problems in
polynomial time: first generate a random solution, then kill yourself if the solution is
incorrect."

Can someone explain to me what the hell he is on about? I'm guessing it's a joke I don't get...

Another example of SciAm going down the tubes (1)

argStyopa (232550) | more than 6 years ago | (#22474466)

If indeed the question is posed in the form of "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?" this is just another sign that SciAm has become another hyperbolix Popular Science magazine, actual science is now optional.

Again, assuming that the summary is correct (I won't read SciAm again) what rational researcher would pose their hypothesis in such absurdly black or white terms? So if it doesn't give us the power of gods, it's an absurd triviality? I'm going to take a wild leap and suggest that it will come down somewhere between the two.
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...