Follow Slashdot blog updates by subscribing to our blog RSS feed

 



Forgot your password?
typodupeerror
×
Supercomputing News Science Technology

$100,000 Prize: Prove Quantum Computers Impossible 324

mikejuk writes "Quantum computing is currently a major area of research — but is this all a waste of effort? Now Scott Aaronson, a well-known MIT computer scientist, has offered a prize of $100,000 for any proof that quantum computers are impossible: 'I'm now offering a US$100,000 award for a demonstration, convincing to me, that scalable quantum computing is impossible in the physical world.' Notice the two important conditions — 'physical world' and 'scalable.' The proof doesn't have to rule out tiny 'toy' quantum computers, only those that could do any useful work."
This discussion has been archived. No new comments can be posted.

$100,000 Prize: Prove Quantum Computers Impossible

Comments Filter:
  • by tomhudson ( 43916 ) <barbara@hudson.barbara-hudson@com> on Saturday February 04, 2012 @11:40AM (#38927519) Journal
    Just point a gun at his head and ask him "Convinced?"
    • by Haven ( 34895 ) on Saturday February 04, 2012 @11:44AM (#38927569) Homepage Journal

      Just point a gun at his head and ask him "Convinced?"

      This is the most concise explanation of a quantum computer I have ever read.

    • by Taco Cowboy ( 5327 ) on Saturday February 04, 2012 @12:17PM (#38927887) Journal

      Ever try proving something that is not going to happen?

      Try it, and you'll know that it's impossible to prove something that is negative - like proving quantum computer impossible

      • Please read the original summary (because we all know that you haven't really read it properly) - you don't have to provide 100% proof it impossible - just convincing the person offering the money that it is probably not practical for most real-world situations, which is a whole other kettle of fish.

        Hence my whole "just point a gun at him and ask if he's convinced" argument - it works on 2 levels:

        1. At the quantum level, both he and the gunholder could be considered in a quantum state - any outside observer cannot state definitively whether he is dead or alive until he either pays the $100,000, or gets shot.

        2. The whole "there are no atheists in foxholes" argument.

        Also, it is definitely possible to prove a negative. I can prove that there are no lions in my refrigerator, no elephants hiding behind my couch, and no dead zombie typing this comment, to most people's satisfaction, for starters.

        • by snowgirl ( 978879 ) on Saturday February 04, 2012 @12:51PM (#38928217) Journal

          Also, it is definitely possible to prove a negative. I can prove that there are no lions in my refrigerator, no elephants hiding behind my couch, and no dead zombie typing this comment, to most people's satisfaction, for starters.

          The lions in your refrigerator are microscopic. The elephants hiding behind your couch are invisible, and you actually are a dead zombie. You just don't realize it, because of a psychological hallucination that you are not actually dead.

          • by gd2shoe ( 747932 ) on Saturday February 04, 2012 @02:56PM (#38929091) Journal

            The lions in your refrigerator are microscopic. The elephants hiding behind your couch are invisible, and you actually are a dead zombie. You just don't realize it, because of a psychological hallucination that you are not actually dead.

            In which case you actually can't prove anything at all... ever. For instance, the entire world (yourself included) could be figments of my imagination. Or maybe we're both characters in a book, and just don't know it.

            If you can prove anything, you can prove some negatives. Of course, you do need to accept some axioms on faith, or you'll be checked into a mental institution. (no offence intended)

            • by snowgirl ( 978879 ) on Saturday February 04, 2012 @03:19PM (#38929245) Journal

              In which case you actually can't prove anything at all... ever. For instance, the entire world (yourself included) could be figments of my imagination. Or maybe we're both characters in a book, and just don't know it.

              For the strictest definition of "prove", indeed we cannot. As Decartes so eloquently stated, the only thing I can be sure of is my own mind. (After all, if my mind didn't exist in some form, then I wouldn't be able to even contemplate not-existing.) But just because I am sure of my own mind's existence, does not mean that I can definitively extend that to other people.

              "Truth" is commonly accepted to be something that is so likely that to withhold provisional belief would be irrational. Sure everything (with a single exception) cannot be proven definitively, but at some point things are so likely true that not believing in them just makes you crazy.

              So, proving this whole issue and claiming the prize money would involve demonstrating that believing in practical quantum computers would be unreasonable. And that is perfectly reasonably possible.

              But one has to realize the ambiguity of the word "prove" here. There is absolute proof of certainty (for instance most mathematical proofs), while just about everything else lies in a range of "yeah, probably." Newton's Laws of Motion were proven correct time and time again, until we eventually started noticing very small errors, and even yet today, while we know that Newton's Laws of Motion aren't the most accurate model, we still know that it's often "good enough".

        • Re: (Score:3, Insightful)

          by sycodon ( 149926 )

          Proving that there are no lions in your fridge is a badly formed question.

          The valid question, and scientifically provable question, is does your fridge currently contain a lion?

          The difference is subtle but important. "does your fridge currently contain a lion?" is a positive statement that can be verified through observation and to which the answer is a positive assertion that is valid within the context of the question, "there is not currently a lion in my fridge."

          • Nonsense. This is the sort of stupidity that gets people into trouble with so-called logic. The same stupidity that insists that if time travel were possible, you can't go back in time and shoot your grandparents because it would "create a paradox", not realizing that the universe doesn't "care" about paradoxes - 'it is what it is."
            • I don't follow you. Assuming time-travel were possible, then, what would happen if I went back and shot my grandparents? Or rather, what I really want to know is, what's wrong with the logical process that leads me into the assumption that it would somehow be impossible to do that?
          • There have NEVER been lions in my fridge and there never will be.

            • by jamesh ( 87723 )

              I broke into your house and put a lion in there yesterday. Check again. Or maybe it's wandered off... you should probably look under your bed too.

        • Also, it is definitely possible to prove a negative. I can prove that there are no lions in my refrigerator, no elephants hiding behind my couch, and no dead zombie typing this comment, to most people's satisfaction, for starters.

          One can not prove a negative but one can disprove a negative. To prove a hypothesis one must reduce the hypothesis to something that is already proven or traverse the set of all possible outcomes and prove the the hypothesis hold for all possible outcomes. It only takes one counter example to disprove a hypothesis but it is much harder to prove a hypothesis.

          The reason the cited hypotheses are provable is that the set of possibilities is finite and easily traversed. The issue with proving that quantum comput

      • This is not true in mathematics and physics. Lots of things have been proved to be impossible. One can prove, without leaving room for doubt, that the halting problem is undecidable, that no arithmetic theory can be consistent and complete, that the universe cannot allow FTL propagation while obeying both causality and relativity, etc.

        • Ah but prove causality. A lot of physics starts from what we consider to be reasonable assumptions for how the universe works and than goes from there. That was the whole screwiness with quantum theory it removed a clear predictive chain of causality from the universe. You have things that are much more likely but you essentially have no certainty.

          FTL can have causality it is just our mindset that would make it difficult for us to understand. For example if you know the concepts of light cones, where everyt

        • Re: (Score:2, Insightful)

          by grumbel ( 592662 )

          One can prove, without leaving room for doubt, ...

          All you can ever really do is gaining confidence in your hypothesis by repeated observation and experiments. Even in math it will be impossible to ever reach absolute certainty without leaving room for doubt, as you can never be fully sure that the proof you did is actually correct, as it could always contain a mistake. Having other people look over the work and repeat it will of course shrink the doubt to a negligible tiny fraction that allows you to assert for practical purposes that something is true.

      • Ever try proving something that is not going to happen?

        If you're using a quantum computer, it could go either way.

      • Quantum computing is math. In math it is possible to prove that some things are not possible, given sufficient constraints.

        But the problem as stated is not well enough bounded to admit the possibility of a proof. It needs to be restated precisely.

        * with constraints on the hardware that define what is and isn't a quantum computer
        * with a definition of what constitutes "useful work". A handheld calculator can do useful work, if useful work is defined as carrying out a few simple mathematical operations at use

      • by PRMan ( 959735 )
        Time travel involving changing of the past is impossible. Why? Because we would see evidence of it already, as human nature is to abuse everything.
        • The Novikov consistency principle asserts that if an event exists that would give rise to a paradox, or to any "change" to the past whatsoever, then the probability of that event is zero.

      • by bartoku ( 922448 )
        I am not convinced. I demand you prove it is impossible to prove something is negative. Sorry I can only offer you $10 if you succeed.
  • by Hadlock ( 143607 ) on Saturday February 04, 2012 @11:43AM (#38927545) Homepage Journal

    Err, uh,
     
    Didn't D-Wave sell a commercial Quantum computer to Locheed Martin [hpcwire.com] in 2010? Almost a year to the day?
     
    Someone explain to me the difference between this quantum computer and the one they're trying to prove doesn't exist, please.

    • by Ken_g6 ( 775014 ) on Saturday February 04, 2012 @11:57AM (#38927695)

      D-Wave uses quantum annealing [wikipedia.org]. This works for minimization problems, although it's unclear whether it's better than "simulated annealing". This does not work for problems like factoring integers, which "real" quantum computers can do.

    • From what my friend who is into Quantum computers tells me that was almost certainly a scam.

      And even without knowing the specifics of quantum computers enough to have any opinion I know that one of the leading quantum computing places in the world, Waterloo Canada does not have a QC that is even close to being usable. It is just like a few quantum bits with a few rooms full of machinery that operates these bits and is both slow and has way to small a number of bits to really be useful.

      • by paiute ( 550198 )

        It is just like a few quantum bits with a few rooms full of machinery that operates these bits and is both slow and has way to small a number of bits to really be useful.

        I don't know Jack - sorry, I don't know Werner - about quantum computing, but you did just describe the state of regular computing circa 1946 or thereabouts.

        • I don't know Jack - sorry, I don't know Werner - about quantum computing, but you did just describe the state of regular computing circa 1946 or thereabouts.

          The difference is that the way forward was clear in 1946. Scaling up was primarily a problem of cooling and maintenance. In other words, engineering problems, not theoretical ones.

          The area of quantum computing today is nowhere near on par with where we were with classical computing in 1946.

          • by harperska ( 1376103 ) on Saturday February 04, 2012 @01:02PM (#38928313)

            When the status quo was a room full of vacuum tubes, I doubt that the way forward (solid state transistors) was as clear as you suggest. Hindsight is 20/20 and all that. There is a vast world of difference between making smaller, faster, better vacuum tubes, and making a transistor. So I think GP's suggestion that we are in the vacuum tube era of quantum computing is reasonable, and we are waiting on the equivalent of a quantum transistor to make quantum computing feasible.

            • by pscottdv ( 676889 ) on Saturday February 04, 2012 @01:57PM (#38928659)

              People were already working on solid-state transistors in 1946. The main difficulty was growing pure enough crystals.

              Even without solid state transistors, computers would have continued to get more powerful and require less maintenance per tube as vacuum tubes improved (nothing like what was possible with solid-state transistors, of course). Remember, vacuum tubes themselves were only about 35 years old at that time--lots of improvement in size, power and reliabililty was possible, but work on them stopped when it became clear that transistors were so much better.

              In the case of quantum computers, there are lots of ideas floating around, but no one actually has any clear idea of what will be needed to maintain quantum coherence across a large number of bits. In fact, it is not yet clear that it is possible.

              The D-Wave computer uses quantum annealing which does not require coherence across a large number of bits, but which is also a LOT less useful than one that does.

    • a new BS meter for posting that link, which features the following gem among many others:

      HPCwire: Can you prove that quantum computing is actually taking place?
      Rose: This was the question we set out to prove with the research published in the recent edition of Nature. The answer was a conclusive "yes."


      And this is the clincher:

      HPCwire: What's next?
      Rose: This is a very significant time in the history of D-Wave. We've sold the world's first commercial quantum computer to a large global security co
    • The physics of oscillating crystals, such as those used in microphones and phonograph needles as well as radio transmitters, indicates that quantum computing could never not exist. Matched oscillating crystals have been in use for thousands of years and the mathematical model is proven by hundreds of different laboratory and home appliances; eg. an infrared spectrophotometric detector. The emission and absorption frequencies predicted by the mathematical model of the particle [wikipedia.org] in a box (the basis for calculating electron dispersion around the nucleus and the fundamental beginning for subatomic calculations).

      Particle in a box model translates into equations known as the Hamiltonian and, in combination with Eigenvalues calculated from the variables used in particle in a box modeling, generates the Schroedinger equation. Quantum computing could never be nonexistent because the mathematics of matched oscillating subatomic particles already has been proven millions of times over.

      The marathon runner was not reporting a successful war campaign. The marathon runner was part of a system proving that those crystals do indeed oscillate, matched, from across the universe (at least 26.2 miles), in real time. Begin counting, begin running, when you arrive, repeat what they said back to them and report your current number. They will determine if your number matches theirs and if you repeat the exact words they said.

      One aspect of the inside joke is that, when the marathon runner arrived and made his report, the response from the priests was,"That's _NOT_ what we said!" and they promptly hit him over the head with a baseball bat in frustration over the not completely failed experiment. "Don't tell anyone that he made it."

    • by drolli ( 522659 )

      Disclaimer: i have worked for a group competing with dwave.

      What dWave has, and they claim not much more, is a system which is stable enough to use thermal noise (their unproven claim: with a small addition by quantum tunnelling) to find the ground state of a Hamiltonian to construct. This solves some tasks, but by far not all.

      What the rest of the QC community wants is a computer which can generate and manipulate entangled state superpositions, enabling to execute arbitrary operations on exponentially scalin

  • by msobkow ( 48369 ) on Saturday February 04, 2012 @11:44AM (#38927557) Homepage Journal

    Now there's a challenge!

    Prove that something which already exists CAN'T exist!

    Methinks their money might be safe on this one... :P :P :P

  • by Anonymous Coward on Saturday February 04, 2012 @11:45AM (#38927577)

    I will prove Quantum Computers both possible AND impossible at the SAME TIME!

  • by funwithBSD ( 245349 ) on Saturday February 04, 2012 @11:46AM (#38927593)

    So I guess the proof would be that they do exist, but only if you don't observe one.

    • by Anonymous Coward on Saturday February 04, 2012 @12:22PM (#38927941)

      'You can't prove a negative'

      If that were true, it would be unprovable. But, anyway, it's not true. Some of the most important (and proven) results in 20th century mathematics were negative: Goedel's proof that arithmetic is INcomplete, Church's proof that polyadic first-order logic is UNdecidable, Tarski's proof that truth is UNdefinable, Cohen's proof that the continuum hypothesis is UNprovable in ZFC, etc.

    • This whole thing strikes me as if a Christian would put up $ for someone to prove to him that God doesn't exist with said Christian as both judge and also having no real incentive to part with the $.

  • So if we make a quantum computer that can log in to facebook, it clearly is not doing useful work. Would we then win?
  • Yesyes...maybe Lockheed bought a quantum computer. It's real? I don't see why not. I can imagine you can program existing hardware to simulate the quantum effect. Does it mean that you get a quantum computer - no...but it simulates it, so in effect...you have one, expensive - not sure how useful, but it'll prove some working theory.

    It's like a double douche - here's one, the other proves the existence of the first one. It's like perpetual energy theory, there will always be believers, and if you make it com

  • .. we've gone from the objective exists | ~exists question to the subjective one of doing "any useful work".

    Even my brother-in-law can do useful work if you stretch the definition far enough.

  • Sorry, what? (Score:5, Insightful)

    by Nemyst ( 1383049 ) on Saturday February 04, 2012 @12:09PM (#38927805) Homepage

    A similar question could've been asked years ago, back when transistors didn't exist: 'I'm now offering a US$100,000 award for a demonstration, convincing to me, that scalable personal computing is impossible in the physical world.'

    Using only technology available then, the answer would've to scale down tubes to the minimal size and go "well this computer's too weak to do anything useful, ergo it's impossible to have a personal computer that isn't just a toy computer." Then transistors happened.

    These kinds of things are stupid, because you're asking for a demonstration to an engineering problem, when engineering is always capped by scientific research. You could have a perfectly "convincing" proof today and tomorrow a new discovery crumbles it all to the ground.

    Unless a theoretical and fundamental proof can be made that quantum computing is impossible, there's no reason to say that it is, and I have serious doubts such a proof can be made considering what has been accomplished thus far. Current limitations are engineering issues, but nothing fundamental is stopping a useful and practical quantum computer from existing.

    • Unless a theoretical and fundamental proof can be made that quantum computing is impossible, there's no reason to say that it is, and I have serious doubts such a proof can be made considering what has been accomplished thus far. Current limitations are engineering issues, but nothing fundamental is stopping a useful and practical quantum computer from existing.

      I think the whole area of what causes quantum behavior to disappear as systems scale up to macroscopic size is not well understood at all. A fundamental proof that large-scale quantum computing is not possible would be monumental in improving our understanding this area.

      • Re:Sorry, what? (Score:4, Interesting)

        by Nemyst ( 1383049 ) on Saturday February 04, 2012 @02:47PM (#38929039) Homepage

        I'm not sure what you mean by this. Quantum behavior disappears at macroscopic sizes simply because all lengths involved are microscopic. Take a hallmark of quantum mechanics as a simple example: the Heisenberg uncertainty principle. It has been shown that the standard deviation of the position times that of the momentum MUST equal or exceed Planck's reduced constant divided by two. Considering the latter is in the order of 10^(-34), it's no surprise that macroscopic measurements are not affected by this limit at all, but nanoscopic ones most definitely are. In the same way, quantum tunneling is also an effect which could theoretically happen at macroscopic sizes, but with a probability so low it's effectively impossible. There's no hard limit, it's just a spectrum which rapidly becomes negligible as size increases.

        As I said, the biggest problem is an engineering one: how do you scale up the number of qubits to an appreciable amount while keeping errors below an acceptable threshold? How do you operate on said qubits without measuring them so as to preserve the wavefunction? Some cases have answers, but this is still overall an open question, unlike classical computing where the first question's been answered by transistors and the second question has no bearing.

    • Re:Sorry, what? (Score:5, Insightful)

      by Beryllium Sphere(tm) ( 193358 ) on Saturday February 04, 2012 @01:49PM (#38928613) Journal

      In _Profiles of the Future_, Arthur Clarke collected a long series of well-thought-out, quantitative, proofs of the practical impossibility of aviation and space flight. The people he quoted were willing to agree that future breakthroughs such as antigravity might allow aviation to work, but that it was an engineering impossibility.

      • by Nemyst ( 1383049 )

        Thank you! I wanted to compare this to flight, but I didn't have sources or references at hand.

    • Re:Sorry, what? (Score:4, Informative)

      by quantaman ( 517394 ) on Saturday February 04, 2012 @02:18PM (#38928845)

      A similar question could have been asked of perpetual motion machines, and in that case there would have been a payout, which I think is partially his point

      The impetus for this prize was a post on Dick Lipton’s blog, entitled “Perpetual Motion of the 21st Century?” (See also this followup post.) [...] Anyway, in the comments section of the post, I pointed out that a refutation of scalable QC would require, not merely poking this or that hole in the Fault-Tolerance Theorem, but the construction of a dramatically-new, classically-efficiently-simulable picture of physical reality: something I don’t expect but would welcome as the scientific thrill of my life.

      I think he's saying that while a general quantum computer might be a very long way off, the underlying theory that allows such a thing to exist is on very solid ground (which is why he's putting up the money). Of course this prize might still cost him since if the news of the prize goes viral he's going to spend the next decade getting spammed by kooks.

    • Re:Sorry, what? (Score:5, Informative)

      by LargeMythicalReptile ( 531143 ) on Saturday February 04, 2012 @02:45PM (#38929023)

      There's some needed context.

      Aaronson himself works on quantum complexity theory. Much of his work deals with quantum computers (at a conceptual level--what is and isn't possible). Yet there are some people who reject the idea the quantum computers can scale to "useful" sizes--including some very smart people like Leonid Levin [bu.edu] (of Cook-Levin Theorem fame)--and some of them send him email, questions, comments on his blog, etc. saying so. These people are essentially asserting that Aaronson's career is rooted in things that can't exist. Thus, Aaronson essentially said "prove it."

      It's true that proving such a statement would be very difficult, and you raise some good points as to why. But the context is that Aaronson gets mail and questions all the time from people who simply assert that scalable QC is impossible, and he's challenging them to be more formal about it.

      He also mentions, in fairness, that if he does have to pay out, he'd consider it an honor, because it would be a great scientific advance.

    • by jamesh ( 87723 )

      Except that wasn't really the question being asked. The challenge was to offer a proof to Scott Aaronson that will convince _him_ that quantum computers will never work. It doesn't have to be correct, just convincing.

      Unless the guy has no ego at all this is still impossible though, just not for the reasons you think. It might have been easier if he hadn't put up the $100k...

  • Isn't the human brain a quantum computer? Isn't that proof enough that it doesn't work?
  • ...and no, it 'in't 'cos I'm a black man. This is a CS guy looking for potential problems in QC to solve before a mature solution can be even considered ready for promotion from drawing board to prototyping - 'cos once you go physical shit gets expensive.

  • 1. Human imagination imagines beyond what is possible.
    2. I cannot imagine a quantum computer.
    3. Therefore, quantum computing is further beyond what is possible than my imagination.
    4. By (1), quantum computing is beyond the possible.


    At least it's valid. If you give me half the money, I can work out rest of the kinks.
  • ... if I can prove they both are possible and impossible?
  • Maybe it's just me, but I had a hard time accepting the credibility of TFA when it misused "effects"/"affects".

  • The idea is nice but it seems like you're trying to get something for nothing which generally doesn't tend to work out in the real world. This prize is probably a good idea to take a look at things from the other end rather than just trying to scale up small-scale experiments (and continually failing if it's genuinely not possible).

    I'd love to be wrong in this case but it seems possible it's something that's in the realm of perpetual motion, FTL travel and anti-gravity to my mind.

  • Um, you can't disprove a negative... so, anyone that is offering $100 grand to... is a fool.

    -AI

  • I examined all of the possibilities simultaneously and I have the answer.

  • by azgard ( 461476 ) on Saturday February 04, 2012 @03:26PM (#38929315)

    I am a layperson, though I studied quantum computers a bit at the university, and (years ago) I came to conclusion that quantum computers do not scale as well as normal computers. That's what will make them impractical.

    In QC, unlike in normal computers, every qubit needs to be interlinked with all other qubits, otherwise the superposition won't work. In normal computers, once you can create a computer with X bits, creating a computer with X*2 bits is pretty easy, just build X twice (and add an address line). With quantum computers, creating a computer with even X+1 qubits from computer of X qubits can be hard, because you need to entangle the extra bit with all others. So the QC will scale only logarithmically to normal computer, and that will make it impractical (respectively, any advantage will be nullified by this problem).

    At least that's what I think; I would like to hear a debunking argument.

    • by ImprovOmega ( 744717 ) on Saturday February 04, 2012 @04:58PM (#38929909)
      It's not logarithmic, it's sqrt(). For a given number of bits (n) adding 1 extra bit requires n additional entanglements. Thus for n-qubits you must have n(n-1)/2 = (n^2 - n) / 2 entanglements. Doubling that increases the difficulty quadratically instead of linearly, but it's not the exponential growth in difficulty that you're implying.

Dennis Ritchie is twice as bright as Steve Jobs, and only half wrong. -- Jim Gettys

Working...