Become a fan of Slashdot on Facebook

 



Forgot your password?
typodupeerror
Supercomputing Science

The Limits of Quantum Computing 228

Posted by kdawson
from the floor-wax-and-dessert-topping dept.
The Narrative Fallacy writes "Scott Aaronson has posted a draft of his article from this month's Scientific American on the limitations of quantum computers (PDF) discussing the question: Will quantum computers let us transcend the human condition and become as powerful as gods, or are they a physical absurdity destined to be exposed as the twenty-first century's perpetual-motion machine? Aaronson says that while a quantum computer could quickly factor large numbers, and thereby break most of the cryptographic codes used on the Internet today, there's reason to think that not even a quantum computer could solve the crucial class of NP-complete problems efficiently. Aaronson contends that any method for solving NP-complete problems in polynomial time may violate the laws of physics and that this may be a fundamental limitation on technology no different than the second law of thermodynamics or the impossibility of faster-than-light communication."
This discussion has been archived. No new comments can be posted.

The Limits of Quantum Computing

Comments Filter:
  • The truth lies somewhere in between the two extremes..
    • Re:As usual (Score:5, Funny)

      by Yetihehe (971185) on Tuesday February 19, 2008 @06:03AM (#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 (Score:4, Insightful)

        by Brian Gordon (987471) on Tuesday February 19, 2008 @06:25AM (#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 (Score:4, Interesting)

          by kalirion (728907) on Tuesday February 19, 2008 @10:12AM (#22474962)
          Besides, I thought that "NP-complete" was a pure math term. Since when has pure math had anything to do with physics? I can understand that solving an NP-complete problem in polynomial time could be mathematically/logically impossible, but calling it "violating the laws of physics" should be a misnomer. Would a number that's greater than 2 and less than 1 violate the laws of physics? How about a triangle with 4 sides?
          • by pnewhook (788591)

            Would a number that's greater than 2 and less than 1 violate the laws of physics? How about a triangle with 4 sides?

            How about a trilogy in five books? Don't Panic.

          • Re: (Score:2, Informative)

            by k.ovaska (752790)

            I can understand that solving an NP-complete problem in polynomial time could be mathematically/logically impossible, but calling it "violating the laws of physics" should be a misnomer.

            From a mathematic point of view, solving an NP-complete problem in polynomial time is not a problem at all. The class NP is defined as the set of problems that a non-deterministic Turing machine can solve in polynomial time.

    • 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,
      • by kvezach (1199717) on Tuesday February 19, 2008 @07:54AM (#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.)
        • 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 abo
      • by Zencyde (850968) <Zencyde@gmail.com> on Tuesday February 19, 2008 @08:00AM (#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.
        • 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.
        • by evanbd (210358) on Tuesday February 19, 2008 @09:54AM (#22474784)

          All you've done is parallelize the problem. Each string is its own highly limited computer. You'll note that to scale to larger graphs, you need to scale the number of strings. That is, you kept the running time the same but had to increase the power of the computer in proportion to the number of edges. Each bead, as a place where forces are summed, also represents a limited power computer. Diskstra's algorithm runs in roughly O(V^2) time when E is comparable to V^2, or O(E*log(V)) time when it's much lower. Not coincidentally, your physical computer's computational power grows at comparable rates.

          Physics doesn't make a particularly more or less efficient computer than a Turing machine; there's no good comparison. What it does do is provide ways to massively parallelize some problems. The shortest path algorithm can be done in O(edges in path) time on a conventional computer with unlimited processors and no communications bottlenecks, which is very similar to what you have described.

      • Complexity classes in general are defined on Universal Turing Machines. What we can say with complete confidence is that problems outside of P are not solvable in polynomial time on such a machine, as thus on any classical computers. The question then becomes whether UTMs are truly ideal computers, as Turing hypothesized, or if we can somehow build a better system.

        As mentioned, the shortest path algorithm is polynomial. Perhaps you were thinking of the NP complete Traveling Salesman Problem? Even if it coul
    • 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.
  • 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*
    • by rucs_hack (784150) on Tuesday February 19, 2008 @06:03AM (#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.
      • by Dutch_Cap (532453) on Tuesday February 19, 2008 @07:14AM (#22473468)
        Luckily, though, tight spandex is a reality today!
      • Did you ever notice, that there are no fat humans in the Star Trek future? Where did the obese 1/3rd of humanity go? Did they use transporters to beam the fat out?
        • by TheSpoom (715771) *
          To be fair, we are mostly looking at the equivalent of a naval vessel most of the time, so one assumes they have to maintain a certain physical discipline.

          (But yeah, it's a TV show, they're stupid like that.)
        • 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.

      • 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.
      • 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 m
    • 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
  • Seems to me... (Score:5, Insightful)

    by Smordnys s'regrepsA (1160895) on Tuesday February 19, 2008 @06:08AM (#22473154) Journal
    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... (Score:5, Insightful)

      by mrbluze (1034940) on Tuesday February 19, 2008 @06:19AM (#22473212) Journal

      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.

      • by Anonymous Coward on Tuesday February 19, 2008 @06:26AM (#22473248)

        there is No Such Agency that can do this yet
        Are you sure?
        • Re:Seems to me... (Score:5, Interesting)

          by mrbluze (1034940) on Tuesday February 19, 2008 @06:42AM (#22473312) Journal

          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.

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

  • The last question... (Score:5, Interesting)

    by siyavash (677724) on Tuesday February 19, 2008 @06:13AM (#22473186) Journal
    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
    • by sqrt(2) (786011) on Tuesday February 19, 2008 @06:27AM (#22473250) Journal
      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.
      • by z0idberg (888892) on Tuesday February 19, 2008 @07:24AM (#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.
        • I don't think there is sufficient data to give a meaningful answer to these questions.

          Not unless we find some ``counter++'' variable, somewhere in physical laws, that only gets executed during boot.
        • I like to think of it like this...

          1 + 1 = 2

          Beauty is in the eye of the beholder, as is existence.

          Everything is math...

          It's all just an equation...
        • Don't Panic! (Score:3, Insightful)

          by LrdDimwit (1133419)
          Forty two.
      • Re: (Score:3, Interesting)

        by Jamu (852752)

        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.

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

        An infinite number of times.

        What kicked it off to begin with?

        Nothing. It has always been.

        Religion doesn't help, at least not for me. (Where does God come from? Same thing.) You can't solve these questions thinking about the physical world. Think abstract. Car analogies are doomed. Maybe try math.

        For how long have pi been pi? How many times has sinusoid function peaked and what started it? How may times has "2 + 2" equaled "4", and since when did it start doing so?

    • Thank you for that. I hadn't read any Asimov before this, but it was far better than I expected. I especially like the poignant twist around the part with Zee, where it became less about exponential expansion and worrying about the future, and more about remembrance of a past that could never be recaptured.

      It's funny how broad such writings are - that I can scoff at antiquated terms like "analog computer" and "microvac", and be moved by aggregation of all thought and matter, in the same piece.
  • by syousef (465911) on Tuesday February 19, 2008 @06:16AM (#22473200) Journal
    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: (Score:3, Interesting)

      by Eivind (15695)
      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-
    • Re: (Score:3, Interesting)

      by SpinyNorman (33776)
      I think the "transcend the himan condition" comment may have been inspired by Roger Penrose's book "The Emperors New Mind", or a reaction to it. Penrose wants to believe that computers arn't capable of human thought, and supports this by claiming (against all evidence to the contrary) that the human brain and conciousness work at a quantum level rather than in the realm of classical physics and neuro transmitters. Quantum computers would at least remove this source of "incapable of human level thought &
  • by RationalRoot (746945) on Tuesday February 19, 2008 @06:54AM (#22473368) Homepage
    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: (Score:3, Insightful)

      by snkline (542610)
      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.
  • 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

    • by QuantumG (50515) <qg@biodome.org> on Tuesday February 19, 2008 @07:23AM (#22473510) Homepage Journal
      http://en.wikipedia.org/wiki/Quantum_computer [wikipedia.org]

      and lay off the trolling.
      • 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 sa

        • I think his comment was some sort of odd joke. "Lay of the trolling" was a ludicrously non-applicable response that IMO needs no further attention.
    • by badfish99 (826052)
      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"
    • by 00_NOP (559413)
      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 und
    • by IWannaBeAnAC (653701) on Tuesday February 19, 2008 @07:34AM (#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.

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

  • ...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?
  • NP-Complete Problems (Score:4, Informative)

    by TripMaster Monkey (862126) on Tuesday February 19, 2008 @07:32AM (#22473552)
    A good list of NP-complete problems can be found here [liv.ac.uk].
  • 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
  • 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
  • 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 most

    • by FooAtWFU (699187)

      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.

      • by Eukariote (881204)

        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 commutatio

  • 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.
  • 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 ab
  • 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've never been one to completely adhere to laws, but that last one sticks out to me.

    If somthing was able to communicate faster than light, how would be observe it happening ?

  • I'll have to change my license plate [markpneyer.com].
  • by Scott Aaronson (1242356) on Tuesday February 19, 2008 @12:23PM (#22476698)
    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.
    • It looks to me as if Grover's Algorithm [wikipedia.org] 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 b
      • by Scott Aaronson (1242356) on Tuesday February 19, 2008 @03:59PM (#22480042)
        Yes, Grover's algorithm is important. As my article discusses, if all you're doing is brute-force search, then Grover's algorithm effectively doubles the size of the instances that you can solve with a given number of steps. But there's a further wrinkle: in practice, people trying to solve difficult optimization problems on a classical computer usually use some sort of local search heuristic, which is much, much faster than brute-force. And while we do have a quantum analogue of local search (called the "quantum adiabatic algorithm"), it's not at all clear how much of a speedup it will give over classical local search on practical instances. Even the square-root speedup of Grover's algorithm might not be achievable in general (on the other hand, it's also conceivable that the speedup could be more than quadratic). If you're interested in this issue, see the original papers on the adiabatic algorithm by Farhi, Goldstone, Gutmann et al., as well as papers by van Dan, Mosca, and Vazirani and by Reichardt about the limitations of the adiabatic algorithm.
  • 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.
  • Background Info (Score:5, Informative)

    by Skavookie (3659) on Tuesday February 19, 2008 @01:06PM (#22477404)
    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 [wikipedia.org]
    http://en.wikipedia.org/wiki/Probabilistic_Turing_machine [wikipedia.org]
    http://en.wikipedia.org/wiki/Quantum_computer#Quantum_computing_in_computational_complexity_theory [wikipedia.org]
    for more details.

    And yes, I am a mathematician.
  • 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

"Consider a spherical bear, in simple harmonic motion..." -- Professor in the UCB physics department

Working...