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."
It can fix the NP problem.... but u cant look into the PC case or else its ruined.
The truth lies somewhere in between the two extremes..
which is totally what she said
ha!
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*
Seven Days with Ubuntu Unity
Answer: Yes, No, Maybe.
You forgot the CowboyNeal answer.
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'.
Just -1, Troll talking to another.
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
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?
These posts express my own personal views, not those of my employer
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.
..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.
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.
http://davesboat.blogspot.com/
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?
From scarped cliff or quarried stone she cries "A thousand types are gone, I care for nothing, no not one."
...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?
A good list of NP-complete problems can be found here.
____
~ |rip/\/\aster /\/\onkey
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?
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.
Those of us who think they know everything annoy those of us who do.
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.
EvilCON - Made Famous by
Physics doesn't exist at that scale! IT'S A LIE!!
Damn you science!
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.
"What's the use of a good quotation if you can't change it?" - Doctor Who
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.
P.S. - It sure is hot here! Why are all these flames around me? Oh hey, there's Mumia and Saddam!
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. 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
Given these problems, I view quantum computing with great skepticism.
YHBT, YHL, HAND.
Comment removed based on user account deletion
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.
Are we really so sure about the Laws of Physics?
The Turing test cuts both ways
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
http://www.ipmt-hpm.ac.ru/SecondLaw/part1.en.html
The Turing test cuts both ways
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.
From scarped cliff or quarried stone she cries "A thousand types are gone, I care for nothing, no not one."
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.
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.
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.
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...
What the fuck?! I would outraged when this was at +4, but +5?!
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.
This is factually incorrect. So far we have not found a quantum algorithm to solve any NP-complete problem in less than exponential time.
Ha!
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.
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, 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).
Non sequitur. It's not clear at this point. If you could answer that question, you'd probably be drowning in money right now.
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.
-Styopa
Dream on, kid. Users are a pain but the OS makes it easy for them to be so.
TWW
Jeez, haven't they heard of a Philotic Parallax Instantaneous Communicator?
The enemy's gate is down, fools.
My sig sucks.
No that is not what NP-completeness is at all; please don't try to speak authoritatively on matters you know nothing about.
The set NP-complete is a subset of NP. The set NP consists of all "algorithmic decision problems" (in fact, they're really defined as formal languages) whose solutions can be verified in polynomial time. All problems in NP are polynomial-time reducible to the NP-complete problems - the NP-complete problems being polynomial-time reducible to one another. An important result due to Cook and Levin is that NP-complete problems actually exist (i.e. satisfiability). Thus, if one can find an algorithm that solves an NP-complete problem in polynomial time, it follows that one can solve all problems in NP in polynomial time.
I am a specialist in the foundations of quantum mechanics and I have never read anything by those involved in quantum computing which indicates they understand what they are doing - this is not intended as a thunderous denouncement, but reflects they were preoccupied with other matters and were drawn to quantum computing as an afterthought. A brief discussion of what quantum theory is: start with an ordered set of events; the ordering is based on time (cause and effect) and an ordering in a set gives you a Boolean structure. From that logical structure, construct what would technically be called a realization of an equivalent of an algebra of probable inference in the sense of Cox. That is what quantum theory is: a system of Bayesian inference.
To put things cartoonishly, with a quantum computer you do not add 2 + 2 but compute the probable outcome of adding 2+2. Now, if you have set things up properly so that your spectrum of observables is restricted to the integers, you will get 4. However, if your spectrum is the real numbers you might get 3.97... So, how you phrase the problem matters, but what is relevant for true quantum computing is that you are solving a different problem than the given problem. I.e., what is the most likely decryption of this message may be the real question of the day rather than magically performing some brute force decryption. (Of course, some quantum computing is merely a new implementation of sequential Boolean logic - a new implementation of digital computers in much the same spirit as implementing, say, a nand gate with different numbers of transistors.)
Let me repeat that: quantum computers inherently solve different problems than digital computers. Their operation is based on a Boolean structure, so they have all the computability and decidability issues of digital computers, but they permit the translation of one problem type into another type of problem. And they may operate at a million more cycles per second than current digitals, but the key element of quantum computing is the transformation of the hard problems into another type which may be more amenable to solution. I'm not interested, however, in bringing them into the light.
Completely off topic, not to mention wrong.
.exe downloaded from any old website.
Err, I think the GP was probably trying to be funny (taking to extremes the 'always bring Linux into everything' motif).
However, since you mention
a stupid user could just as well download a deb/rpm/tarball for a linux smiley toolbar or something and run it...
Most Linux users can meet 98% of their software needs from the official repositories (I currently manage with 100%), or for paid commercial software will get it from the offcial source., which while both of these methods are not entirely immune to attack, are about 100 times less likely to contain malware than a windows
As far as malware floating about in non-repo RPMs/Debs from odd websites? Well, it's possible. But I've been running Linux and (intensively) reading about Linux related issues for about 6 years now and I'm yet to hear of such a thing. I'm sure you could find something if you were determined enough...
All the evidence points to Linux malware of this sort** being so rare as to almost not exist. Even the stupidest user can't download it if it's not there.
** Rootkits installed remotely etc. is a different category, not involving 'idiot' users downloading crap but instead those with enough knowledge to (say) want to open up remote access to their machine but not knwoing enough to properly secure that access.
actually if anything linux makes it easier or should, "Linux/UNIX doesn't stop people doing really stupid, things because it might stop them doing really clever stuff too".
The only thing that protects a user is using FOSS, this 'happends' to be common amongst Linux distributions, but end user software is so far removed from the kernel there's no reason it has to be.
But without giving a lot of power to somebody to choose what users should/shouldn't install malware can effect all OSs easily, and no os will ever give somebody all that power
IranAir Flight 655 never forget!
Writers on Star Trek, unlike Star Wars, take care not to violate physics. What they do is invent hypothetical addendums to physics that we have not discovered yet that support their own constructs. IE, "warp speed" does not violate special relativity, because they are not traveling through normal space time. They are traveling through another kind of spacetime (subspace) that we haven't discovered yet, where the constants that govern our laws of physics are different.
Not only is it "amazing" -- it's the reason why there will never be a 512 qbit quantum computer. Ever. Such a computer would require more resources than are present in our universe. Darn those laws of physics!
Ask Mr. S.'s cat.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
If somthing was able to communicate faster than light, how would be observe it happening ?
Wanna fight ? Bend over, stick your head up your ass, and fight for air.
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.
It's interesting that the Star Trek universe doesn't seem to have "money", yet, they do have scarcity. They often had shortages of starships, and they had limits as to how fast they could develop technology. And, there really doesn't seem to be much in the way of private spaceflight, outside of the TOS, in the Trek Universe.
Oddly, the Star Wars Republic had both money and a fair amount of spaceships. In Star Wars, just about everyone had a spaceship or access to a spaceship of some kind. With the vast resources of the Galaxy, the Galactic Empire was able to build an incredible number of Star Destroyers AND, at least two Death Stars, plus numerous other combatant vehicles. In fact, the Galaxy was so rich that a number of systems could band together and fund their own rebellion.
I guess what it boils down to, is that Star Trek might have had a more advanced technology in some ways, but Star Wars had the better economy.
This is my sig.
"Explanation for the man in the street" by Scott Aaronson,
http://scottaaronson.com/blog/?p=208
"Good question. The period-finding algorithm doesn't work for a function that's 0 almost everywhere, and 1 only in a few exponentially-far-apart places. For the quantum Fourier transform to tell you anything useful, you need a function whose periodic structure is "globally detectable." There's a paper by Hales and Hallgren from years ago where they made that intuition more precise."
"approved" by Peter Shor.
http://scottaaronson.com/blog/?p=208#comment-9958
(Shor wrote "Great article, Scott! That's the best job of explaining quantum computing to the man on the street that I've seen."). Scott Aaronson suggests the following 12 sites as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
http://en.wikipedia.org/wiki/Shor's_algorithm
Hi fellow slashdotters!!
You might be interested in knowing what the author of TFA thinks about his article and the discussion here
Don't quote me on this.
I'll have to change my license plate.
My blog
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.
"Giving a complete proof that no fast quantum
algorithm can solve these problems is out of the question, since we can't even prove that
no fast quantum algorithm can solve them."
Huh?
I re-read that sentance 20 times, and it still seems redundant and pointless.
In fact the entire article smacks of amateurism and sounds more like a rant than any form of insight.
I've been saying for years that any technology which has yet to characterize its physical limits is snake oil in training. I always read stories about quantum computing where it states "with enough qubits", but never yet read an account which explains what becomes more difficult as the qubits are piled high, and whether this difficulty increases linearly or exponentially. Perhaps qubits can be stacked arbitrarily high ... in an otherwise empty universe.
One upon a time thermodynamics was an open frontier. Actually, no. It turns out in most realistic scenarios you are lucky to extract 40% of the milk and honey. Thermodynamics, welcome to entropy.
What would obtaining 40% of a solution to the class of NP-complete problems look like? How many qubits can be stacked together before the computation interacts with statistically improbable vacuum states? What's the catch, and why do so few articles on the subject clearly elucidate the bounding condition? Worse, why do people who already understand the relationship between thermodynamics (greed) and entropy (death and taxes) fall for these one-sided journalistic prognostications?
Hasn't quantum physics already proven the ability to do faster-than-light communication using Quantum Entanglement?
http://en.wikipedia.org/wiki/Quantum_entanglement
It seems as if most of the readers of Slashdot think quantum computers are the same as nondeterministic computers. Well, they are not. Nondeterministic Turing Machines (NTMs) are those that follow every computational path simultaneously and accepts if any path accepts. Quantum computers are more like Probabilistic TMs, which take a random branch at every step. The problems solvable in polynomial time by NTMs define NP, and RTMs define RP. The classes x-complete are the "hardest" of the problems in the class x. It is believed to be highly unlikely that any NP-complete problems are polytime on QCs.
These are very informal definitions. Look at
http://en.wikipedia.org/wiki/Nondeterministic_Turing_machine
http://en.wikipedia.org/wiki/Probabilistic_Turing_machine
http://en.wikipedia.org/wiki/Quantum_computer#Quantum_computing_in_computational_complexity_theory
for more details.
And yes, I am a mathematician.
Nobody is obese because nobody has to be. Medicine in the Star Trek universe is IMHO far more advanced than their grasp of physics is.
Weaselmancer
rediculous.
The question "Will quantum computers let us transcend the human condition and become as powerful as gods?" is completely silly. Becoming "as gods" requires the ability to manipulate matter at the atomic level. It requires "real molecular nanotechnology" as promoted by Drexler, Merkle & Freitas. It requires actual general purpose molecular assemblers, nanorobots of various types (as described by extensive detail by Freitas in various papers and books) and general purpose macroscale nanofactories (Star Trek "replicators"). None of those things involve breaking any laws of physics or the type of computational capacity or teleportation communications that might be provided by pushing on the laws of physics through quantum mechanical waving of hands.
"Transcending the human condition" requires being able to manipulate real matter -- preferably, precisely at the atomic scale -- not being able to factor 1024 digit numbers.
When everyone is uploaded and expanded their intelligence by ~10^13 times their current level [1] -- *then* it may be time to worry about having to lean on quantum limits. And even then, the people left behind on the few planets, comets, etc. remaining may *still* have reason to consider the manipulation of molecules and atoms (energy, food, external hazards, etc.) as more important than the entanglement of particles at the quantum level. When you show me a quantum computer that can design *real* molecular machine parts (as Merkle & Drexler have done), then I'll be interested. Before then its sound and fury signifying nothing.
While exploring these areas may be of interest to a few theoretical physicists they are are little importance to millions around the world who lack clean water to drink or food to eat.
1. A Matrishoska Brain has ~10^24 times the computational capacity of the human brain. Matrioshka Brains are massive supercomputers operating within single solar system at a full Kardashev Type II civilization power consumption level. Assuming ~10^11 human minds, uploading (or linking) all of them allows each of them to expand their computational capacity 10^13 times (i.e. each individual has more thought capability than all of humanity currently has) [assuming of course the computational resources are distributed equally among current and near term future humans and run away absconding with the computational resources of the solar system by a runaway AI is prevented].
Forty two.
My amazing wife - Artist, Author, Philosopher - Laurie M
So if it can't solve NP complete problems can it at least play Crysis?
In reality, since quantum wavefunctions follow all possible paths they behave as the nondeterministic Turing machines you describe. And since they have the probability interpretation, via the norm squared thanks to Born, they have a probabilistic Turing machine- like aspect as well. So, they are really neither of these things, but have aspects that throwback to previuously established concepts.
If I recall correctly, Dijkstra's Algorithm is only solvable in P time if the edges of the graph are directional and the weight of all edges are non-negative. So, real world(For example, trying to get from A to B using a street map where streets are bi-directional.) shortest path problems are actually NP-complete. Of course, that's only if my memory serves me right. I'm not sure if the problem could really be solved correctly using electric fields, but it could provide a quick guess... I'd have to think about it.
What you're really dealing with is a network of resistors, where resistors are edges and interconnections are nodes and the "shortest path" would be the path with the greatest current. Except in the case of electrical arcs, the resistance decreases as current increases(arc plasma formation) along a path so that nearly all the current follows the path of the arc. Maybe if you ran several trials and averaged the result, but it still may not be "correct."
and because time does not exist in Heaven or hell, there is George Bush and Tony Blair too.
It looks to me as if Grover's Algorithm should allow solving every NP problem in time proportional to the square root of the minimum number of operations a classical computer would require.
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.
While we're on that question, how about this one - "Could God create a version of Microsoft Windows so stable that even He could not make it crash?"
It's about as relevant.
... and then they built the supercollider.
I see why it's a draft. On page 13, it says "all you can do pick a box", which clearly needs a verb, "is". A suboptimal version was picked from the Library of Babel. That's probably because a genetic algorithm was chosen to pick a pretty good paper, but it was caught at a local maximum fitness value...
-- Stephen.
Not quite. They act like an NTM until you try to actually measure it's final state, and then the waveform collapses. However, they differ from probabilistic TMs in that the "programmer" can manipulate the distribution in "more" ways. I _think_ BQP (quantum) actually contains BPP (probabilistic).
"the understanding we've achieved has barely filtered into the popular press, and has remained all but absent even from books dealing with 'complexity' (such as Stephen Wolfram's erroneously-titled A New Kind of Science)"
Fan of Asimov since I as was a kid.
So I thought I would respond to this.
(I am just having a little fun with this so please forgive me.)
It wouldn't take AC to recreate the universe.
The reset button is built in.
The real question is how would you fit all the matter of the universe into the big bang?
That single dimensional point that contains everything and nothing...
After entropy take its coarse, matter reaches a point where it no longer supports a dimensional universe.
At that point everything reverts to a single point, every where and no where that contains everything and nothing.
For a single moment a super atom or alpha particle exists.
Then it explodes into the big gang that we call the universe.
When did the last universe end?
About the same time ours began.
How long will ours last?
Until the beginning of the next one.
Yes, this is roughly what I was thinking when I read your original post. As you stated, "Quantum computers are more like Prob TM's [than NTM's]", this is what prompted my response. Now, in your reply, exists a contradiction with the original post, at least as worded, perhaps not as the thought. Moreover, in my reply, I alluded to the NTM to ProbTM aspects of Qcomp that you stated more explicitly in your reply. As for the BQP and BPP I can not comment about, since pure computer science is newer to me than mathematics and physics; i.e. I'm currently two out of three in the multidisciplinary math, physics, & compSci that is Qcomp.