Whether or not God plays dice, I do

Another Update (Feb. 7): I have a new piece up at IEEE Spectrum, explaining why I made this bet.  Thanks to Rachel Courtland for soliciting the piece and for her suggestions improving it.

Update: My $100,000 offer for disproving scalable quantum computing has been Slashdotted.  Reading through the comments was amusing as always.  The top comment suggested that winning my prize was trivial: “Just point a gun at his head and ask him ‘Convinced?’”  (For the record: no, I wouldn’t be, even as I handed over my money.  And if you want to be a street thug, why limit yourself to victims who happen to have made public bets about quantum computing?)  Many people assumed I was a QC skeptic, and was offering the prize because I hoped to spur research aimed at disproving QC.  (Which is actually an interesting misreading: I wonder how much “pro-paranormal” research has been spurred by James Randi’s million-dollar prize?)  Other people said the bet was irrelevant since D-Wave has already built scalable QCs.  (Oh, how I wish I could put the D-Wave boosters and the QC deniers in the same room, and let them duke it out with each other while leaving me alone for a while!)  One person argued that it would be easy to prove the impossibility of scalable QCs, just like it would’ve been easy to prove the impossibility of scalable classical computers in 1946: the only problem is that both proofs would then be invalidated by advances in technology.  (I think he understands the word “proof” differently than I do.)  Then, buried deep in the comments, with a score of 2 out of 5, was one person who understood precisely:

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.

OK, two people:

    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 (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 … 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.

For better or worse, 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.  This award has no time limit other than my death, and is entirely at my discretion (though if you want to convince me, a good approach would be to convince most of the physics community first).  I might, also at my discretion, decide to split the award among several people or groups, or give a smaller award for a discovery that dramatically weakens the possibility of scalable QC while still leaving it open.  I don’t promise to read every claimed refutation of QC that’s emailed to me.  Indeed, you needn’t even bother to send me your refutation directly: just convince most of the physics community, and believe me, I’ll hear about it!  The prize amount will not be adjusted for inflation.

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.)  The post consists of a debate between well-known quantum-computing skeptic Gil Kalai and well-known quantum-computing researcher Aram Harrow (Shtetl-Optimized commenters both), about the assumptions behind the Quantum Fault-Tolerance Theorem.  So far, the debate covers well-trodden ground, but I understand that it will continue for a while longer.  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.  Gil more-or-less dared me to put a large cash prize behind my words—as I’m now, apparently, known for doing!—and I accepted his dare.

To clarify: no, I don’t expect ever to have to pay the prize, but that’s not, by itself, a sufficient reason for offering it.  After all, I also don’t expect Newt to win the Republican primary, but I’m not ready to put $100,000 on the line for that belief.  The real reason to offer this prize is that, if I did have to pay, at least doing so would be an honor: for I’d then (presumably) simply be adding a little to the well-deserved Nobel Prize coffers of one of the greatest revolutionaries in the history of physics.

Over on Lipton’s blog, my offer was criticized for being “like offering $100,000 to anyone who can prove that Bigfoot doesn’t exist.”  To me, though, that completely misses the point.  As I wrote there, whether Bigfoot exists is a question about the contingent history of evolution on Earth.  By contrast, whether scalable quantum computing is possible is a question about the laws of physics.  It’s perfectly conceivable that future developments in physics would conflict with scalable quantum computing, in the same way that relativity conflicts with faster-than-light communication, and the Second Law of Thermodynamics conflicts with perpetuum mobiles.  It’s for such a development in physics that I’m offering this prize.

Update: If anyone wants to offer a counterpart prize for a demonstration that scalable quantum computing is possible, I’ll be happy for that—as I’m sure, will many experimental QC groups around the world.  I’m certainly not offering such a prize.

171 Responses to “Whether or not God plays dice, I do”

  1. Nex Says:

    Nice. I would love for such prices to be much more common. I would love it even more to have enough $$ to be able to offer them myself :P

    Anyway can you clarify one point, you say that proof would require “the construction of a dramatically-new, classically-efficiently-simulable picture of physical reality.” Why efficiently-simulable? What about classical but non-local and as a consequence not efficiently-simulable pictures of reality?

  2. fgrosshans Says:

    Just for curiosity : would a proof that BPP=BQP be considered a proof that quantum computing is possible (be cause we can build a machine which computes any quantum algorithm) or impossible (because a quantum computer can do no better than a classical computer) ?

  3. Carl Says:

    You should try to see if you can get Mitt Romney on the other side of the bet. He’s good for it, apparently.

  4. Scott Says:

    Nex #1: Good point! If scalable QC (as currently understood) turns out to be impossible, but the same discovery that shows such an impossibility, also shows that the Extended Church-Turing Thesis is false for some “different” reason, then I’ll consider myself off the hook for the full $100K prize, but might award a smaller prize at my discretion.

  5. Scott Says:

    fgrosshans #2: Alright, alright. :-) If the physical assumptions underlying the quantum computation model turn out to be fine, but BPP=BQP, then I’ll also award a smaller prize, maybe $5,000-$10,000 depending on the details.

  6. Scott Says:

    Carl #3: Good idea! Mitt is, indeed, a high-roller woefully out of touch with the common man … just like me. ;-)

  7. rrtucci Says:

    Your prize could be called the S Prize (S=Scott). I think you should also try to convince the X prize foundation to award several million dollars for an experimental demonstration that scalable quantum computing is possible. You could help them draft the guidelines.
    Wow, $100K is a lot of bread.

  8. rrtucci Says:

    Gil and Alicki, those gambling facilitators, could help the X prize foundation draft the guidelines too.

  9. Scott Says:

    rrtucci:

    $100k is a lot of bread.

    Yeah, I’d say at least 50,000 loaves. :-)

  10. wolfgang Says:

    >> The prize amount will not be adjusted for inflation.

    So either you are very sure about scalable quantum computers or you trust Ben will do QE3, QE4 … 8-)

  11. MIchael Nielsen Says:

    1. Can you give an example of what you’d consider convincing evidence that scalable quantum computing is impossible in the physical world? It’s not clear from the post.

    2. It’s possible that quantum mechanics is false, yet quantum computing is still possible. I believe this is the case in some of the nonlinear variants of QM which people have proposed, under reasonable assumptions about noise. The idea is simply to error-correct away the deviations from quantum mechanics. In some sense we can error-correct the non-quantum reality to a quantum simulation.

    3. An amusing way to increase the prize: buy a $100k premium from an insurance company against the event scalable QC is found to be impossible. They will, one presumes, be willing to offer a much larger payout. The only downside is that you’d have to pay the premium :-) (I believe the X-prize people paid a premium of 2 million to get their 10 million prize.)

  12. rrtucci Says:

    $100K for one of the biggest scientific and technological discoveries of the century

    = 1 micro Facebook.

    1 bacteria \approx 1 micron

  13. Jiav Says:

    Don’t even try Michael! If you were the one to prove that, you’d be at risk to face a series of reimbursement claim :-)

  14. Scott Says:

    Michael #11:

    1. Well, the “prototypical” example would be a new mathematical framework for physics, forced on us by novel experiments, that replaced quantum mechanics (agreeing with QM in its current range of validity), and that led “back” to BPP as the natural class of efficiently-solvable problems, in the same sense that quantum mechanics leads to BQP. Other possibilities should be judged by their similarity to that prototype.

    Anyway, the vagueness in the post was deliberate! Conditioned on scalable QC being impossible, I genuinely have no idea which of our current ideas would fail, and I suspect it would be some assumption that’s so ingrained, neither QC proponents nor QC skeptics realize at the moment that they’re making it. Hence the central role in my offer of “discretion”—I think an impossibility argument for QC is less like a P=NP proof than like pornography (can’t define it, but know it when you see it…)

    2. Yes, good point! If it turned out that there was some fundamental decoherence mechanism, like GRW or Penrose’s gravitational collapse, I’d be tremendously excited (obviously), but I wouldn’t immediately be on the hook for this award. For, as you say, it’s entirely possible that one could still do scalable QC, treating the new fundamental mechanism as just one more source of decoherence to be error-corrected.

  15. Roger Says:

    You say, “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.” Then you say, “If scalable QC (as currently understood) turns out to be impossible, but … also …, then I’ll consider myself off the hook for the full $100K prize”. In other words, you have reneged on your offer already.

  16. Scott Says:

    Roger #15: That’s some selective quotation worthy of Fox News. The situation I was talking about is one where QC gets replaced by something that QC opponents would no doubt find equally crazy and unacceptable.

    In such a case, it would depend on how different the something else was. If it had absolutely nothing to do to QC, then I’d consider myself on the hook for the full $100,000 prize. On the other hand, to whatever extent the other thing was like or similar to quantum computing, I’d adjust the prize amount at my discretion.

    Look, in cases like Vinay Deolalikar’s claimed P≠NP proof (about which, might I remind you, I was right, despite being a “liberal academic” :-) ), I could give extremely sharp conditions for when I would pay. In cases involving physics rather than math, it’s not possible to be equally sharp, because we don’t have the imagination to foresee all the possible ways Nature could violate our expectations. So I do the best I can.

    Incidentally, since you seem pretty confident over on Lipton’s blog, how much are you offering for a demonstration that scalable QC is possible? Any interest in taking the other side of this? If you were, I’d be much more interested in haggling over boundary cases.

  17. plm Says:

    That is alot of fine prints.

    How many qubits, processed at what frequency, is considered scalable -for our human society?

    Anyway, I find this a really really great question.

  18. rrtucci Says:

    Nice news report by a “Mike James”

    http://www.i-programmer.info/news/112-theory/3723-100000-prize-for-proving-quantum-computers-are-impossible.html

  19. Jim Graber Says:

    I postulate that there might be a fundamental limit on the size of a Schrodinger cat, not just a FAPP limit.
    My understanding is that this is contrary to what Schrodinger, Einstein, Zeilinger and “all” quantum physicists believe,
    and hence would represent a fundamental change in QM, just as would a fundamental limit to the size of a quantum computer.
    It is not clear to me that the Schrodinger Cat Limit (SCL) implies or is implied by the Quantum Computer Limit (QCL), but I think they might be related.
    Comments?

  20. Mike James Says:

    rrtucci -
    Thanks for the “nice news report” :-)
    I hope it creates some extra interesting in the whole idea.

  21. Scott Says:

    Jim #19: Your postulate isn’t as uncommon as you think! So for example, Roger Penrose has conjectured that the fundamental limit on Schrödinger cat size gets imposed by general relativity. Notably, his and related “gravitational-collapse” proposals actually make predictions that experimentalists—including some I just visited at the University of Vienna—are hoping they’ll be able to test over the next decade. Then there’s the GRW (Ghirari-Rimini-Weber) collapse proposal, which also involves a fundamental decoherence process that would impose a limit on Schrödinger cat size. (However, I and many others consider GRW extremely ad hoc, since it doesn’t even try to explain where the decoherence process comes from, and it involves parameters that have to be fine-tuned to avoid conflicting with current experiments.)

    Interestingly, though, as I said above, neither GRW nor a Penrose-like gravitational collapse necessarily conflicts with scalable QC! A quantum computer might treat the fundamental collapses, supposing they existed, as “just one more source of decoherence” to be dealt with via error-correction.

    Conversely, one could imagine some novel principle of physics that would rule out quantum computers (maybe because they violate some “universal complexity limit”!), but that wouldn’t have any problem with arbitrarily-large Schrödinger cats. In other words, the two possible ways quantum mechanics could fail seem incomparable to me.

  22. Roger Says:

    If scalable quantum computers are possible, then it ought to be possible to build one that can factor N-bit integers for some value of N larger than what is possible for conventional (Turing) computers. My bet is that quantum computers never outpace ccnventional computers in this way.

  23. Henning Dekant Says:

    Most academic attempts at generating a marketing stunt are pretty sad affairs, but this is really a good! I hope some more reporting will latch on it.

  24. rrtucci Says:

    Story hits the jackpot (or shitpot, depending in your point of view)

    http://news.slashdot.org/story/12/02/04/140207/100000-prize-prove-quantum-computers-impossible?utm_source=rss1.0mainlinkanon&utm_medium=feed

  25. Would you like to earn 100000$ ? « adifferentconnection Says:

    [...] Aaronson, a well-known MIT computer scientist, has offered 100000$ to the person that convinces him (and in the same time the entire physics community) that scaleable [...]

  26. Mike O'Donnell Says:

    This won’t get me the prize, but I conjecture that the physical laws governing quantum coherence will prevent scalable quantum computing from achieving an exponential improvement in computing time. Furthermore, a characterization of coherence in terms of computational complexity will become a useful physical principle. I don’t envision any proof of this conjecture other than experimental evidence.

  27. Scott Says:

    Mike #26: I appreciate your honesty in differentiating conjectures from knowledge! :-)

    To me, it would be an unsatisfying situation indeed—one of the most unsatisfying in the history of physics—if

    (a) your conjecture was right, yet

    (b) experiments never led us to any theoretical principle that would explain your conjecture, just a morass of uninterpretable data.

  28. asdf Says:

    What do you do if there’s a scaling limit similar to how Moore’s Law is supposed to eventually run out of steam? That is, it becomes practical to build a quantum computer that can run Shor’s algorithm on billion-bit RSA numbers, but getting much beyond a billion bits runs into physical limits that current (2012) theory hasn’t clearly predicted? Does that mean QC is scalable, or non-scalable?

  29. Scott Says:

    asdf: Interesting question! Given that even classical computers can’t scale beyond the maximum entropy of the observable universe (roughly 10122 bits), it would clearly be unfair to define “scalable” quantum computers in a way that required literally-unbounded scaling. So as a rough-and-ready criterion, I’ll say that “scalability” has been achieved if (say) Shor’s algorithm can be implemented with a few thousand qubits—or, more generally, if QCs can be made large enough that they’re clearly, decisively, uncontroversially superior to classical computers for some problems.

  30. $100,000 Prize: Prove Quantum Computers Impossible | Akmproject Says:

    [...] 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 [...]

  31. rrtucci Says:

    asdf: Besides, Scott will be dead by then.

  32. asdf Says:

    “…more generally, if QCs can be made large enough that they’re clearly, decisively, uncontroversially superior to classical computers for some problems.”

    But that might be temporary— P!=QBP today is an unsolved conjecture. Maybe while it’s still unsolved, experimenters build large QC’s which become the only known way to factor billion-bit RSA numbers (but not bigger, per above, e.g. due to some fundamentally unavoidable decoherence issue). Lots of such QC’s are then built for various purposes. Then one day, someone proves P=QBP, concocting a devious algorithm that lets classical computers simulate quantum computers in P-time. That means classical computers can now solve even bigger problems than quantum computers…

    By the way I have to wonder how Dana reacted to your committing $100K like that. You have responsibilities now ;-).

  33. Assorted links — Marginal Revolution Says:

    [...] 5. Is scalable quantum computing possible? [...]

  34. rrtucci Says:

    adsf: A corny but effective movie scene:
    I am Spartacus. No, I am Spartacus. No, I am Spartacus…

  35. Scott Says:

    asdf #32: Another good point! Well, I already said that for a proof of P=BQP that didn’t challenge the physical assumptions behind quantum computing, I’d pay $5,000-$10,000, so in your scenario that’s what I’d ultimately be on the hook for. Remember that with this bet, the burden isn’t on me to prove something scales; it’s on skeptics to prove it doesn’t!

    As for Dana, she agrees that there’s no compelling reason to doubt the scalability of quantum computing, so she’s fine with it (as she was with the Deolalikar bet), but she also requests that I not make any more such bets. ;-)

  36. Slipper.Mystery Says:

    I bet Dana $100. that Scott will make more such bets.

  37. Joshua Zelinsky Says:

    There’s also a possibility that P=BQP but that BQP allows very high degree polynomial speedup. In that case, quantum computers might be doable and very useful even though P=BQP. In fact, I don’t see a priori why one might not have P=BQP but having arbitrary high degree polynomial speed ups on problems in P.

  38. blk Says:

    @Joshua: If P=BQP, you get polynomial quantum speedup of some degree if and only if BQP can be simulated in P with polynomial slowdown of that same degree.

  39. Matthew Fuller Says:

    Were superlenses with a negative refractive index provably impossible at some time point in the 20th century?

    I have a small bet with my sister (who is a chemist) that by 2054 we would solve the protein folding problem. She said it was impossible to solve because we would *never* be able to image the proteins, and x-ray crystallography had too many limitations.

    Looking forward to your comments. The phenomena of negative refractive index in metamaterials was truly new? So like no one could anticipate it until that magic eureka moment? How often does that happen, if true?

  40. John Sidles Says:

    Matthew, your chemist sister perhaps has in mind RIchard Henderson’s much-cited survey “The potential and limitations of neutrons, electrons and X-rays for atomic resolution microscopy of unstained biological molecules” (Quarterly Reviews of Biophysics, 1995, 418 citations).

    Needless to say, in limiting the analysis to “neutrons, electrons and X-rays”, the conclusions of Henderson’s survey are explicitly circumscribed rather than broadly applicable.

  41. Matthew Fuller Says:

    Thanks Dr. Sidles.

    She was quoting her professor who may have actually gotten the idea from that very paper. I’ve asked her what she thought about the bet today and she still feels the same, knowing nothing about the problem since that time. She wound up dropping out her phd program and getting married. Given the drop-out rate for grad programs I think I can make a pretty strong case if I wanted to do cognitive science research, which is my field.

    There are a lot of problems where a firm disproof would be very valuable and they don’t just include physics.

  42. Richard Says:

    We have a very good example of a QC in operation right now…your own brain. The human brain is operating at the Quantum level and the trapped electrons in the microtubuels, are collapsing the incoming wave functions, internaly. The internal projection is seen as reality outside of the skull. Nothing exists outside of the brain except a shower of energy.

  43. Scott Says:

    Richard: Even Roger Penrose expresses lots of uncertainty about whether or not quantum effects in microtubules have anything to do with consciousness; your blithe confidence in that idea seems completely unwarranted. However, even supposing he and Hameroff were right, the human brain still wouldn’t be a quantum computer in the specific sense we’re talking about here: namely, a machine able to use superposition and interference to (e.g.) factor huge numbers and simulate arbitrary quantum systems. (Can you do those things? I can’t! :-) )

  44. Michelle Marie Says:

    Scott, I’m a little confused, you stated above: “Many people assumed I was a QC skeptic, and was offering the prize because I hoped tospur research aimed at disproving QC (Which is actually an interesting misreading)”. http://www.scottaaronson.com/blog/?p=902 which contradicts your statement below taken from the article _The Limits of Quantum_ you wrote in 2008″

    “Quantum computing can be seen as the most stringent test to which quantum mechanics itself has ever been subjected. In my opinion, the most exciting possible outcome of quantum computing research would be to discover a fundamental reason why quantum computers are not possible. Such a failure would overturn our current picture of the physical world, whereas success would merely confirm it.

    Such limitations ensure that computer scientists will continue to have their work cut out for them in designing new quantum algorithms. Like Achilles without his heel or Superman without kryptonite, a computer without any limitations would get boring pretty quick.” via:http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

    How could you claim the assumption as a misreading? You clearly indicated that you hoped QC would be disproven so that compter scientists will continue to have their work cut out for them. Can you please clerify?

  45. Scott Says:

    Michelle: The key is that what I hope will happen—i.e., what would be the most exciting thing to me intellectually—is the complete opposite of what I expect will happen! I hope we’ll get the opportunity to modify quantum mechanics in the regime tested by quantum computing, but I expect we won’t.

    Anyway, you’re not alone: it seems many, many people have mistakenly thought I was a QC skeptic, probably because they’re congenital optimists who assume that what a person hopes and what they expect are the same thing! :-)

    Incidentally, though, the last paragraph of my “Limits of Quantum Computers” essay had nothing to do with this issue. That paragraph was talking about limitations of quantum computers and the cleverness needed to design algorithms for them, even assuming that scalable quantum computers can be built and that they behave exactly as predicted by standard quantum mechanics.

  46. Michelle Marie Says:

    Scott, Not to argue what might be considered minutiae, but since you brought it up I should point out (in the defense of others) the word hope is synonymous to the word expect.

    Hope:
    1: to desire with expectation of obtainment
    2: to expect with confidence : TRUST
    http://www.merriam-webster.com/dictionary/hope

    So it’s not completely wrong to believe the words hope and expect to be one and the same. But I understand what you’re getting at, I don’t use the words in the same context either. Thank you for clarifying : )

  47. Scott Says:

    OK then, instead of the word “hope,” you can substitute “wish” :-)

  48. Quantum Computing Challenge of the Day - TDW Geeks Says:

    [...] MIT’s Scott Aaronson, whose area of expertise is theoretical quantum computing, has issued a $100,000 challenge to skeptics who don’t believe quantum computers are [...]

  49. Raoul Ohio Says:

    Michelle Marie:

    It is well known and obvious that dictionaries cannot be definitive; consider the “circular definition” issue.

    At any rate, if that is in fact the Merriam-Webster definition of “hope”, it is particularly lame. The work “hope” has a well understood meaning in English, and it has little or nothing to do with “expectation of actually happening”.

    For example, around February 6 (with pitchers and catchers about to report to camp) close to 100% of baseball fans HOPE their favorite team wins the World Series in 2012. A much smaller percent EXPECT this to happen.

  50. MIT Scientist Offers $100000 to Anyone Who Can Prove Quantum Computing Is … Says:

    [...] [Scott Aaronson via SlashDot] [...]

  51. Igor Says:

    http://en.wikipedia.org/wiki/Russell%27s_teapot

    *philosophic burden of proof lies upon a person making scientifically unfalsifiable claims rather than shifting the burden of proof to others*

  52. Joe Fitzsimons Says:

    Michele, I believe that second definition is to do with a separate usage of hope: “We hold out little hope of …”, “The is now hope that…”, rather than the usage in “I hope I’ll win the lottery”, “I hope there really are superluminal neutrinos”, etc.

  53. Scott Says:

    Igor #51: Why don’t you go reread the part of the post about Bigfoot. If quantum computers are impossible, then just like faster-than-light communication and perpetual-motion machines, they can be ruled out by a better understanding of physics. That puts them in a completely different category than Bigfoot or Russell’s teapot.

  54. Igor Says:

    Scott #53: I hope you understand that if you put them in two different categories (just because it’s convenient for you here and now as much as it’s convenient to not mention HUGE holes in the theory), doesn’t mean they really are in different ones. Bigfoot/Creationism/Whatever also can be ruled out by better understanding of biology/evolution/whatever.

    I myself believe in QC possibility, but I don’t like how you put it – instead of producing a viable result/proof you are asking community to prove you are wrong.

  55. Scott Says:

    Igor, I’ve spent the past 12 years trying to advance quantum computing research. Most relevantly, experimental groups in Bristol and in Brisbane are now working to implement BosonSampling, a proof-of-principle for optical quantum computing proposed last year by myself and Alex Arkhipov. I understand how it might look to people like the entirety of my intellectual output consists of blog posts, but I really do have a day job! :-)

    In the meantime, though, if you go read Lipton’s blog, you’ll find commenters who, incredibly, think QC is impossible because of some trivial problem that all the world’s physicists, computer scientists, and mathematicians somehow overlooked for the last 20 years … or think the belief that quantum mechanics will be vindicated yet again is no different from the belief in fairies or Santa Claus. The very existence of such ignoramuses in this world makes it harder for me to sleep at night. Those people, and anyone who sympathizes with them, are the ones my bet was aimed at.

  56. Igor Says:

    Scott #55: Why don’t just send them to go check out D-Wave One or something.

  57. Scott Says:

    Igor #56: Because I have no idea whether the D-Wave One actually exploits quantum coherence to get a speedup over classical simulated annealing.

    (Though as I said in the post, I do sometimes fantasize about putting the D-Wave folks and the anti-QC folks in the same room, so they can sort things out between themselves while leaving me alone!)

  58. rrtucci Says:

    “Most relevantly, experimental groups in Bristol and in Brisbane are now working to implement BosonSampling, a proof-of-principle for optical quantum computing proposed last year by myself and Alex Arkhipov.”

    How long before we see a paper from them? When is the baby due, if you know? How far advanced are they?

  59. rrtucci Says:

    How many photons are they aiming for?

  60. rrtucci Says:

    Are they the only ones in the race? It seems like a natural problem for Japanese expertise.

  61. $100,000 To Whoever Proves Quantum Computing is Impossible | Science, Singularity & Spirituality Says:

    [...] [Scott Aaronson via SlashDot] ← Half of Fortune 500s, US Govt. Still Infected With DNSChanger Trojan [...]

  62. Scott Says:

    rrtucci: No, I don’t know when the “baby” is due. I was lucky enough to tour the lab in Bristol last week; they’re currently working on doing BosonSampling with 4 photons and 16 modes. I don’t know what the group in Brisbane is planning right now; it’s been a while since I’ve talked to them.

  63. MIT Scientist Offers $100,000 to Anyone Who Can Prove Quantum Computing Is Impossible | Geek Mecca Says:

    [...] [Scott Aaronson around SlashDot] [...]

  64. Luca Says:

    Hi, i was thinking about physics and complexity theory! What if finding the right final physics theory is hard (NP)? Is this a completely meaningless question?

  65. Scott Says:

    Luca #64: Yeah, it’s pretty meaningless! :-) The concept of NP-completeness applies only to the asymptotic limit (i.e., as the input size goes to infinity), but presumably there’s only one set of physical laws to be discovered.

  66. MIT Scientist Offers $100k Prize To Anyone Able To Prove Quantum Computing Is Useless | Lose Your Fear Says:

    [...] Aaronson’s blog has all the details, and he’s been very responsive to answering questions from commenters. Or, if you want to brush up about recent happenings on the QC front, feel free to check out our articles about the “World’s First Programmable Quantum Photonic Chip,” entangling ions with microwaves, or breaking the laws of single-particle physics with ultrapure gallium arsenide semiconductor crystals. Oh, and thanks to Popular Science for pointing the contest out! [...]

  67. coffeemug Says:

    Regarding this and the recently posted piece at IEEE Spectrum: I think the point is as follows. The TV show Mythbusters doesn’t actually bust any myths. It shows some clever guys giving it three or four tries and then, if those all fail, they declare the myth to be “busted.” It’s a fun TV show, but we all know that this isn’t the scientific method; and especially if they attempted to bust a ‘theoretical myth’, 3 counterexamples does not demonstrate that there cannot be a positive example.

    Well, scalable quantum computing is to many folks one of the most important ‘myths’ we’re still working on in quantum physics. And the vocal minority behind Scott’s wager are trying to declare it to be “busted” in a Mythbusters-esque we-tried-a-few-ideas-and-they-didn’t-work-so-let’s-give-up sort of way (not all of course; some are pursuing legitimate theoretical approaches and I’m sure Scott would agree that it’s good we have people thinking about that, but that none of those people have claimed any convincing result that truly ‘busts’ the myth).

    So, if you think scalable quantum computing is a myth and you want to ‘bust’ it, Scott wants you to direct your attention to non-Mythbusters ways of doing it. No controversy. That’s all.

  68. Slipper.Mystery Says:

    > I have a new piece up at IEEE Spectrum, explaining why I made this bet.

    This piece has a significant problem, chastising a group of unknown size and composition without the temerity to specify even who exactly you’re talking about. I expected to learn from it finally what the fuss was all about, but instead there’s only vague innuendo along the lines:

    > for decades, a small but vocal minority of computer scientists and physicists has held that building a scalable quantum computer is impossible

    > A few of the skeptics seem rather angry, and express the view that quantum computing researchers are some sort of powerful cabal bent on suppressing dissent.

    > Not surprisingly, most quantum computing skeptics — among the ones who offer physical arguments at all! …

    > Most of the skeptics say …

    > Like a wily defense attorney, the skeptics don’t even try …

    No overt refs but at least the first had an actual link to RJLipton’s blog where one learns of “the debate sparked by Gil’s paper” [arXiv:1106.0485]. At last the villainous group has a member, Gil Kalai, who then explains that an allegedly famous Robert “Alicki is perhaps the only physicist engaged in long-term research skeptical towards quantum computers and error-correction”, and gives refs to his articles arXiv:quant-ph/0306103, arXiv:quant-ph/0306103, arXiv:quant-ph/0702050, arXiv:0812.0999.

    That’s it? … your mystery anti-QM cabal, your “decades” of “angry” and “small but vocal minority”, consists of a whole two people?!? and a handful of articles, the majority unpublished? If so, you’ve given them infinitely more promotion and credibility than they deserve.

    There must be more to it, your IEEE Spectrum piece could have provided a few refs as informative background, but didn’t — perhaps you could provide that here?

  69. Quantum Computing Bounty | wavewatching Says:

    [...] the even bigger surprise: This academic really knows how to create one heck of a marketing stunt.  His blog was already flooded after slashdot reported on this and more media is now jumping on the bandwagon. [...]

  70. plm Says:

    Luca #64 and Scott #65:
    Actually I find (some form of) this a great question. It may turn out that experimental results will never quite match theoretical predictions and we may always search for more refined theories. In any case I see at least 2 related questions:

    1. Given a finite set of experimental results (just formulas in classical logic, say working in ZF) how hard is it to write (few, short) axioms which imply them? (This may already be researched in proof complexity.)

    2. What physical limitations on (the complexity and predictivity of) theories of physics exist? Presumably there would be several useful limits, of various kinds. And perhaps we could prove things like “different QM interpretations can never be definitely ruled out”, but there could still be an optimal one (short and psychologically appealing in various senses -I think psychology should be involved, we are talking of human researchers).

  71. Scott Says:

    Slipper.Mystery #68: Besides Gil and Robert Alicki, other notable QC skeptics include Leonid Levin (of Cook-Levin Theorem fame), Oded Goldreich, Gerard ‘t Hooft (the Nobel physicist), Stephen Wolfram, and Ed Fredkin (well, he actually believes P=BQP). Besides them, my experience has been that there’s also a significantly larger group of physicists, chemists, and computer scientists who agree with the anti-QC sentiments but haven’t articulated them in print (there were even a few who angrily accosted me after department colloquia to accuse me of peddling lies!) If you read the comment threads on Gil’s blog, you’ll see lots of contributions from two more skeptics, both of whom played large roles in “pushing me over the edge” to make this bet: Roger Schlafly (author of a book called “How Einstein Ruined Physics”) and Craig Feinstein (author of numerous wrong P≠NP proofs).

  72. PhotonAce Says:

    If someone demonstrates the contrary (i.e., actually build a quantum computer) and save you the $100K, would you be willing to buy her/him a nice dinner? That might be another way to settle this debate…

  73. Scott Says:

    PhotonAce: Absolutely! Dinner’s on me (pending logistics), at any restaurant of the experimenter’s choice. Now, an obvious difficulty is that building a scalable QC is likely to be the result of the combined efforts of hundreds or thousands of people, and I can’t eat fancy restaurant dinners with all of them without destroying my arteries. But if scalable QC becomes a reality, then I will, at my discretion, offer dinners to those individuals who seem to have made the most decisive contributions.

    Alas, while the actual building of scalable QCs might sway some skeptics, others (such as Oded Goldreich) have said explicitly that it would make no difference whatsoever to them. In such a case, Oded told me that he would still be 100% certain of the classical Extended Church-Turing Thesis; it’s just that the constant factors would’ve turned out to be bizarre. ;-)

  74. Slipper.Mystery Says:

    Let’s see, that’s now a whole nine people (plus the “few who angrily accosted me after department colloquia to accuse me of peddling lies” — no doubt the case, but probably unrelated to the question of scalable quantum computing)

    So let’s consider where these people are coming from: Kalai, Levin, Goldreich are math/computer science, no particular expertise in quantum physics. Ed Fredkin has a fascinating background, but which also doesn’t include quantum physics.

    Of the three with a physics background, ‘t Hooft is the best known, but it’s difficult to find any statement from him regarding the impossibility of quantum error correction. He has some interesting ideas about the interplay between quantum mechanics and gravity (going way back, which led him to the idea of holography), but appears to be skeptical about string theory rather than quantum computing. If Wolfram is skeptical about quantum computing, it’s only in the sense that he believes it unnecessary since in his view the entire quantum mechanical world can be simulated with cellular automata (perhaps sharing Fredkin’s confusion). That leaves only Alicki, certainly serious and playing a useful role, as Kalai’s “perhaps the only physicist engaged in long-term research skeptical towards …”
    (typo in above comment, 2nd of the four refs should have been quant-ph/0506201).

    Of the two who pushed you “over the edge”: Roger Schlafly is a failed mathematician with no expertise in quantum mechanics or computer science (and it would certainly be unfair to hold his conservative nutcase parentage against him), and Craig Feinstein is an amateur nobody yet to produce a single correct result of any form.

    At least now we understand the proper context of this debate, somewhere between misconstruing blog trolls as representative of the scientific community, and jousting with pygmies.

    But the artifice of the wager notwithstanding, it is indeed useful to have clearly articulated the difference between difficulties of principle, and difficulties in practice. In that sense, it is little different from past comments you’ve made re quantum computing testing the validity of our understanding of many body quantum mechanics (linearity, superposition, …). If at your colloquia to “physicists, chemists, …”, you polled the audience at the outset re their beliefs in this specific aspect of quantum mechanics, and then again at the end, you might feel less accosted.

  75. Scott Says:

    Slipper.Mystery #74: Well, I’m not going to argue too strongly with you. :-D

    Look, if I get criticized about equally by people who think I don’t take QC skepticism seriously enough, and people like you who think I take it too seriously, then I guess I’m doing something right.

    You’re right that this is little different from stuff I’ve said countless times before. The only new aspect is what you call the “artifice of the wager” (i.e., highlighting my views with money that I expect never to have to pay). And I think the results of the experiment are now in: while my wager succeeded in garnering some attention, it’s had no effect whatsoever that I know about in swaying any skeptics. Oh well…

  76. Jiav Says:

    Slipper.Mystery, I’m sorry but you’re just boring. Could you please shut up and go play elsewhere? Thanks in advance for your help.

  77. rrtucci Says:

    Slipper.Mystery. I think the bet/prize has made a lot of people take an important problem more seriously, and think more about quantum mechanics and quantum computers. Not bad!

  78. Científico ofrece recompensa a quien demuestre que la computación cuántica es imposible Says:

    [...] “Si la computación cuántica escalable es posible es un cuestionamiento sobre las leyes de la física. Es perfectamente concebible que el desarrollo futuro de la física entre en conflicto con la computación cuántica escalable, de la misma manera en que la relatividad entra en conflicto con la comunicación más rápida que la luz, y la Segunda Ley de la Termodinámica entra en conflicto con el movimiento perpetuo”, dijo Aaronson en su blog. [...]

  79. Tim Converse Says:

    I enjoyed this post, and I have no criticism to make about the $100K offer, which I think is a fun idea.

    But I was struck by this in your update:

    “(Oh, how I wish I could put the D-Wave boosters and the QC deniers in the same room, and let them duke it out with each other while leaving me alone for a while!)”

    Uhh, if you *genuinely* would like to be left alone on this issue, maybe posting $100K prize offers about it is not the best way to achieve your goal.

  80. Raoul Ohio Says:

    Scott has been accused of having a lack of “temerity”. According the top hit on Google (MW dictionary) temerity means “unreasonable or foolhardy contempt of danger or opposition : rashness, recklessness.”.

    Makes me yearn for the good old days of “Cowboy TCS”.

  81. coffeemug Says:

    Slipper.Mystery #74: 9 people, among which there are at least two very famous physicists, is not a small enough group to brush off. You’re acting like 9 is unequivocally a small number… but that entirely depends on the context.

  82. Scott Says:

    Tim Converse #79: The reason I feel the need to respond to this stuff on my blog is that the “silent majority” doesn’t respond to it, even when the majority agrees with me. This creates a bizarre situation where it looks like I represent some sort of embattled fringe, both when I’m debating the D-Wave boosters and when I’m debating the QC deniers … despite the obvious fact that both of them can’t be right! Hence my fantasy of the “D-Wave team” and the “anti-QC team” duking it out with each other for a while (i.e., the Green Goblin battling Doctor Octopus, so Spiderman can rest).

  83. Scott Says:

    Raoul Ohio #80: I stand accused of a lack of temerity?

  84. Vadim Says:

    I’m afraid so, Scott, post #68.

  85. thank you based scott Says:

    http://www.physorg.com/news/2012-02-quantum-physicist-100k-proof-scaled-up.html

    Thank you Scott, this article gave me good positive energy while reading the news at work.

    You said that a while ago on the blog that you were thinking about logical depth. This paper is interesting: http://arxiv.org/abs/0810.5663

    Thanks for letting me spam the blog.

  86. Slipper.Mystery Says:

    scott#72: > Hence my fantasy of the “D-Wave team” and the “anti-QC team” duking it out with each other for a while

    Indeed, the entirety of your fantasy universe consists solely of the handful of fringe elements on either side of that issue. But happily on 1 Mar 2012 at the American Physical March meeting you have the opportunity to meet roughly 10^4 actual quantum physicists in neither of those camps, but who simply use QM on a daily basis, and take for granted the principles of linearity and superposition (though most will be at parallel sessions during your talk, try the hallways afterwards). Go ahead and ask if any have heard of Kalai or Alicki, or Schlafly or Feinstein, or for a reality check go ahead and weigh the many tens of thousands of articles these working scientists produce per year against the handful produced by both your fantasy teams over their decades of uncited angry production.

    coffeemug#81: > 9 people, among which there are at least two very famous physicists

    Reading more carefully beyond the first sentence, you will find no famous physicists claimed to deny the possibility of quantum error correction. (And gut responses from uninformed mathematicians and computer scientists are less compelling.)

    #76: Regrettably, my crayon-to-ascii converter does not always produce content-free one-line messages adapted to elementary school backgrounds.

  87. Tracy Hall Says:

    Scott: “I don’t promise to read every claimed refutation of QC that’s emailed to me.”

    I would suggest going further: promise publicly and prominently that you will never acknowledge having read any refutation unless it is personally recommended to you by a minimum of two of your own doctoral students (current or former) who have read it and are convinced of its validity. The injunction to “convince most of the physics community” is certainly the right idea, but that may not provide a specific enough target to deflect the attention of the dedicated, energetic, and prolific, um, non-traditional thinkers whose aspirations and imaginations you are bound to have sparked.

  88. coffeemug Says:

    Slipper.Mystery #85 : We can agree to disagree. I don’t think that the title of ‘computer scientist’ precludes someone from being a world-class expert on quantum physics, especially not in this area since we’re dealing with quantum computing. To be a research level computer scientist in that field any more, you must be at least as good as many research level physicists working in and around the fault tolerance theorem.

    If you want to dispute that Leonid Levin’s stance, for example, shouldn’t be treated seriously just because his job title is ‘computer scientist’, well, you’re welcome to do so, but you’re not going to have very many people agreeing with you. That’s a needlessly narrow view of dissenting opinions.

  89. Scott Says:

    Tracy Hall #87:

      I would suggest going further: promise publicly and prominently that you will never acknowledge having read any refutation unless it is personally recommended to you by a minimum of two of your own doctoral students…

    What kind of thing is that to inflict on my poor doctoral students? :-)

    Still, your point is well-taken, and I hereby strengthen my statements as follows:

    I’m under no obligation whatsoever to read, or to acknowledge having read, the alleged refutations of quantum mechanics (and claims on the $100,000 prize) that have already started arriving in my inbox and my comment moderation queue.

    A prerequisite to convincing me that scalable QC is impossible is to convince a large part of the physics community, including the part that specializes in quantum information.

  90. Scott Says:

    coffeemug #88: You’re absolutely right that having the job title “computer scientist” in no way, shape, or form precludes serious engagement with the physical issues around the fault-tolerance theorem. In Levin’s specific case, on the other hand… ;-)

  91. Scott Says:

    Slipper.Mystery #86: Once again, your tone puzzles me since it seems we’re in almost-total substantive agreement.

    Despite what it must look like out in Readerland, I actually spend most of my time teaching and doing research (just like all those other folks who will be there with me at the APS March meeting) … not debating QC skeptics and D-Wave boosters on the blogosphere!

    On the other hand, given the wildly disproportionate attention that extreme claims tend to receive, don’t you think it’s a useful public service for scientists to spend at least some of their time responding to them? Sure, you might not want to do it yourself, but why complain if someone else like me does?

    Or maybe the idea is that the extreme memes would die without the oxygen of attention provided by this blog? Empirically, that seems completely false (besides attributing way more influence to this blog than it has!) Had this blog never existed, journalists would still be running regular D-Wave stories, and a large minority (majority?) of computer scientists and members of the nerd public would still have the vague, unarticulated sense that somehow quantum computing must be like perpetual motion.

  92. Links 9 Feb « Front to Back Books Says:

    [...] offering 100K USD for proof of infeasibility of scalable quantum computing (Aaronson’s blog), here and  also picked up by IEEE. This is like Gary Cooper in High Noon, only [...]

  93. Slipper.Mystery Says:

    Scott#91: > Once again, your tone puzzles

    Ascii “tone” can be difficult to parse … there’s no problem with the wager (“useful to articulate the difference between difficulties of principle, and difficulties in practice”), and it can even clarify the issue for the general public (cue/queue the choir — that we may be in the situation Babbage was in, not yet having the proper technological realization; that it’s not a question of violating 2nd law of thermo or special relativity, … and Re D-Wave, as you well know, even if they succeed to establish quantum coherence in their systems, there’s the issue of whether adiabatic quantum Hamiltonians will ever be suitable for the interesting problems, i.e., whether the band gaps are exponentially small so that the adiabatic method necessarily takes exponentially long anyway).

    The criticism #68 of the IEEE Spectrum piece was that it gave no direct references or names, not clarifying just how small or unrepresentative was the “vocal minority”. Now that the landscape is clarified, I accept this as a rhetorical device furthering the above pedagogic interests. It would have been less effective (though still humorous) to specify that the group in question consists of a single mathematical physics outlier, others less schooled in QM, and persons of uncertain provenance who accost you after talks.

  94. Prof. Byron Brainard Says:

    “Many people assumed I was a QC skeptic, and was offering the prize because I hoped to spur research aimed at disproving QC.”

    Guilty – I thought this only because several “news” articles I read really seemed to promote that this was what MIT was doing. I was unaware of your blog until I read a REAL science article in http://www.physorg.com/ that gave the appropriate details.

    Keep up what you are doing, quantum computing is a fascinating field and something I have thought about for a very long time. When I first started learning about computers in the late 70′s I always asked myself, “Why limit ourselves to just one OR zero” I wish I were intelligent enough to be more of a contributor in this field. Perhaps some day I will be. (by the way, if you can thing of a way to “crowdsource” some of the research I would be more than happy to participate)

  95. Drew Henry Says:

    First of all I’m an artist, and not quite suited for this question when it comes to a sheer analytical fashion in the academic sense. However, I do have a creative mind, so here’s my shot at it. Plus, I’m a computer geek, so why the Hell not… FIrst of all, we currently don’t have the storage needed for quantum computing. The largest drive we have, at the moment, I believe is 3TB. Nowhere near enough to run a quantum OS, let alone quantum compilers and programs. To have a quantum PC run as smooth and as seamless as the current tech we have today would go far beyond our lifetimes. Meaning to have a quantum PC sitting next to me as my workstation does today, or to have a quantum netbook, laptop, or smartphone will never happen in our lifetime. Not to run as “seamlessly” as we have it today with our current tech. Then throw into the mix particles given off by our sun, which already screws-up current PCs when there’s a solar flare. How stable do you think a quantum PC would be given that situation? It would have to have some serious housing to deflect such cosmic intrusions. Once again… Wont “seamlessly” be done in our lifetime. Speaking of which, then you have the basic infrastructure of the computer as we know it, today. An analogy; The government is highly against solar power as a renewable energy resource. NOT because it isn’t “valid” or “better”, but simply because we’d have to change the entire infrastructure of the oil industry to accomodate such a drastic change/shift. Same with this~ We’d have to “re-invent” all of our current motherboards, circuitry, and materials to do this. Once again I say, wont be done “seamlessly” in our lifetime. Perhaps not even in our children’s lifetime. Once again, the key word here is “seamless”. Getting back to compilers and programming, another analogy for you; Video game programmers now have access to 6 or more cores on a cpu, but they aren’t using all of those threads because the cost of “development” doesn’t allow for it. If they tried, video games would cost upwards of $200 a piece. Not practical at all. So just “how long” do you think it would take to write COMPLETELY NEW OS systems, compilers, drivers, and applications/programs for such a system? EVERYTHING would have to be re-written/re-done. The first Intel chip came out in the late 70′s. “dual core” didn’t happen until 2003. Look at the time span for that alone… almost 30 years. Microsoft didn’t even get Windows right until Win 7 (in my opinion), and that came out about 3 years ago. So here’s my conclusion to your proposal. Scalable quantum computing IS “physically impossible” in our lifetimes. Especially if you want such a system to run as “seamlessly” as the systems we have today (and as compact). You said that your bet goes “until you’re dead”. Well, by the time you die, we still wont be there. Your reality will be over, and the pursuit will still be sought after. So in your reality/life time, scalable quantum computing will have been “physically impossible”. Especially if you want it to run as well as the PCs we have today, and as compact. Given all of these factors, my concluding statement is… Where’s my money? ~Drew Henry

  96. Gil Says:

    Hi all, the purpose of my investigation is not to prove that universal quantum computers are impossible, but rather to offer principles that if true (or when true) then quantum error correction is impossible. I find this subject academically fascinating which is why I study it. Indeed, I come from the mathematics/computer science side of the story and this has disadvantages and advantages. In any case, Aram and I (along with our hosts and several participants) discuss several specific issues and especially some conjectures that I have raised which touch on important questions regarding quantum error correction.

    As far as I know, Robert Alicki and me are the only people involved in a long term research of this kind. (And our approaches are quite different.) There is a big difference between a skeptical approach which dismiss the whole issue as uninteresting, and an academic study of this fascinating question. So personally, I would like to think about myself in this context as on board the quantum computation research and not as “(vocal??) QC skeptics”. It is indeed true that when I am pushed to the wall I say that I tend to think that QC are implausible, but being more right or more wrong on this single bit issue is not what my work is about.

    I think Scott’s prior beliefs and mine on this issue are different. Scott compared the QC project to bringing a man to March and I think it is perhaps closer to a trip around the world aimed to reach India. (Yes, yes I know you can also reach India…) It is an uncharted scientific territory which is what make it so interesting.

  97. Scott Says:

    Drew #95: “Your” money is in my bank account, retirement fund, etc. :-), and it’ll stay there until someone offers a reason why quantum computing is impossible in principle—meaning, not in my lifetime, not in the next hundred years, but forever.

    Technological/social plausibility arguments very much like yours could’ve been (and were!) given against Charles Babbage’s crazy idea of universal classical computers in the 1830s. And those “arguments” were valid—until they weren’t! By contrast, the arguments against perpetual-motion machines, which were also given in the 19th century, remain just as valid today as they were back then—because those arguments were based on laws of physics, rather than technological circumstance. In some sense, helping people understand the difference between the two types of argument was the entire purpose of this bet!

  98. Drew Henry Says:

    Scott~ As I already stated in the beginning, I truly am NOT suited for the challenge. And for the record, I agree 100% with what you’ve said. But none-the-less… I am right. He says his bet goes until he’s dead. We wont have the tech by then. And there’s also the possibility of us giving-up on it in exchange for some other technological advancement that could offer a more cost effective/practical option. All I know is this; When this man is on his deathbed (and when I’m on mine)… We’ll see who was right. ;)

  99. Scott Says:

    Drew: But I’m not betting that practical QCs will be built, only that no one will discover a physical reason why they can’t be. If I’m on my deathbed and neither of those two things has happened, then I will have been right, not wrong on the specific question I was addressing.

    Having said that, I’m not nearly as pessimistic as you are, and would give at least 50% odds for some sort of practical QC (though possibly not universal QC) in my lifetime. Obviously, those aren’t good enough odds for me to stake $100k on!

  100. Gil Says:

    (Putting a man on March is hard now, but in few weeks this can change…)

  101. Vomitorium » Blog Archive » 100.000 USD für den Beweis… - Die Welt. Wirtschaft. Technologie. Medien. Gossip. Bullshit. Says:

    [...] Whether or not God plays dice, I do. …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… [...]

  102. Drew Henry Says:

    Scott~ Oh, so YOU are the fella posing this inquiry? I thought you were just another fella on here. Well, I don’t mean to come off as pessimistic. I’m being more of a realist; I LOVE technology. If QCs happen… More power to it. I’m a digital artist and would love to game/scream Photoshop on one of those bad boys! But let ME ask YOU this~ What are the limitations thus far? I mean… WHY can’t one be built aside from cost-of-research? Right now we are very technologically advanced. We have CPUs being built on a 23nm process now. Years ago IBM made an “IBM” logo using gold molecules (remember that?). So what’s the actual “problem”?

  103. Drew Henry Says:

    Also… Out of curiosity… What are your thoughts on DNA computing? I read an article in a PC magazine stating that some company (I think IBM) has designed a prototype chip that mimics how the synapses in the human brain works. 1 “synaptic transistor” has “branches”, where-as today’s transistors do not… Opening a world of possibilities of advanced computing. And a major up-side to that… Much like the human brain (which is analog as opposed to digital)… Is that if part of the chip screws-up, another part of it can take on the task at hand. Much like if someone suffers brain damage, another part of the brain can “learn” how to do the same task. Do you think DNA/Synaptic computing would assist in QCs on some level? Do you think these type of computers would be cheaper/easier to develop? Your thoughts, sir…?

  104. Drew Henry Says:

    I was just reading an article from a Google search where you state that the problem is “decoherence”, where active quanta feel the need to interact with those that are not, and that this is the problem that must be overcome. I also read that there have been small QCs already created that are capable of doing “useless tasks”. If you want a practical QC built that functions as a full-fledged PC, perhaps the decoherence problem lies in a technique we are already doing, today; “Multicore Processing”. So in other words, why can’t we take those small UN-scaled QCs, and cluster them to create one “scalable” QC? Seems like an easy fix, to me. Once again… Your thoughts??

  105. Drew Henry Says:

    Now that I’ve given my input on how it MIGHT be done, I’ll go ahead and give some solid scientific principles (at least as much as I know) as to why it CAN’T be done. The only thing that comes to mind is the whole “spooky effect” thing. Didn’t Einstein isolate quanta in some sort of fashion using lead containment cutting off all “communication” between 2 quanta? YET… When this was done… Didn’t those 2 quanta still communicate, regardless of the physical separation? Am I right on this (it’s been a very long time since I’ve heard this). If this is true, then THAT is what would make a true QC impossible to build. So there… There is my “real” scientific answer. And again… Your thoughts???

  106. Drew Henry Says:

    I AM right! I just read an article on this! So, the ONLY way to make it so that a QC can be built is to overcome the “Spooky Effect”. And in order to do that, one would have to figure-out “how” to get said particles/quanta from communicating with each other. Which is apparently extremely hard to do given the fact that this effect can happen from miles and miles away. Then there’s also the question of, if we could achieve this “block of communication”… Then what? Would the quata disappear and cease to exist (i.e. “die?”). Would this cause some sort of violent reaction comparable to a nuclear reaction? And what about possible radiation effects? Is that an issue? Could it be? Given the “Spooky Effect”, I don’t think it is possible to create a Scalable QC. It hink the notion of a DNA/Synaptic computer is a far better (and easier) bet.

  107. Drew Henry Says:

    Now my “creative/artistic” side is gonna kick in! Yay! I think the reason the “Spooky Effect”/Decoherence issue can NOT be overcome… Are you ready for this… Is because I’m of the opinion that quanta aren’t merely just “things”, but ENTITIES. I don’t know a lot about this stuff, but I do know this~ Weird unexplained shit happens in physics. Especially quantum physics, such as the problem posed here. And I’m of the opinion that the only way to “explain” these things is that there’s “more to it”. What if quanta ARE “entities”? Some kind of life-form that we… As humans… Just don’t see that way? If that’s the case, it can’t be done. Not unless somehow, some way, we (as humans) discover a way to create our own “artificial quanta” that are merely “slaves” that do what we tell them to do. I believe quantum particles are entities that we do not fully understand. And I will have that as my basis as to “why” it can’t be done… Ever. :D Not bad for a Mass Art fella, huh? Lol !

  108. Drew Henry Says:

    Basically, quantum particles make-up stuff. They make-up molecules, and those molecules make material, and that material makes… Well… “Stuff”; Skin, blood, hair, enamel. Plastic, metal, silicone, etc. Living and non-living. I know I’m skating around the idea of “God” here, but I’m not. What I’m saying here is this; Quantum particles have a specific job/place in the universe. And well… “computing” isn’t it. At least not in the way we think. You can’t “control” nature… Not 100%. And that’s the “problem”. At least in this case. Humans don’t control what quantum particles do… The universe does. If we DID find a way to have quantum particles “bend to our every whim”, we’d have replecators that made food (Star Trek), we could teleport, and so on and so-forth. We weren’t meant to have that kind of control. Quantum Computing is out of the reach of humans. It’s a “God thing”. $100,000.00 please :D

  109. Drew Henry Says:

    “The human mind is not capable of grasping the Universe. We are like a little child entering a huge library. The walls are covered to the ceilings with books in many different tongues. The child knows that someone must have written these books. It does not know who or how. It does not understand the languages in which they are written. But the child notes a definite plan in the arrangement of the books—-a mysterious order which it does not comprehend, but only dimly suspects.”
    ~Albert Einstein

  110. Drew Henry Says:

    I have thoroughly enjoyed this, Scott… $100,000.00 or not. Me entering this blog has shown a classic example of the artistic mind vs. the scientific mind. “God” (or whatever you wish to call it) can not be proven scientifically. And in an attempt in defending myself in sounding “archaic”, simple fact is… There are things in this world that can NOT be explained… Ever. Just as there are “powers” that can NOT be “harnessed”… Ever. There are things as humans we ARE meant to know/understand/control and there are things that we simply can NOT. And by the way, according to Einstein… “God” does NOT play dice with the universe. Just sayin’ ;)

  111. Scott Says:

    Drew: I fail to understand why your argument (i.e., “but mortal Man wasn’t MEANT to build quantum computers! It’s PLAYING GOD!!!“), if correct, wouldn’t also rule out classical computers, genetic engineering, nuclear weapons, quantum cryptography, Bose-Einstein condensates, the Large Hadron Collider, and thousands of other things that we already have today.

    Also, factoring integers and solving Pell’s equation in polynomial time is an unusual notion of “playing God”! I’d think God would be able to solve NP-complete problems in polynomial time at the least. But according to current conjectures, that would already put Him well beyond what a quantum computer can do (see my Scientific American article for more).

  112. Drew Henry Says:

    I’m not saying we CAN’T “play God”. What I’m saying is that we shouldn’t always try to do-so. In doing-so, “we” (as humans) have had some great things happen, sure. But we have also had catastrophe after catastrophe because of it, as well. Also, to put my notion in a more poetic/artistic sense; What if “quantum computing” truly is something that the universe itself was only meant to achieve/do? As humans, the computers we have today are amazing, if you think about it. That right there is a “miracle” that we have created. And we could still go plenty far with “binary computation”. The angle I’m coming from is this; Quantum computation is probably a language meant for the universe ONLY. Quantum computation is probably how the universe was created, and is how it continues to create. As I’ve already stated~ Quantum particles are the basis of all material… Living and non-living. And “how” they arrange themselves to create “whatever” is a quantum computation that we probably aren’t meant to understand. Regardless, I have a high admiration for your tenacity in this relentless pursuit. But Einstein himself once said that he wished he never created the atom bomb. Food for thought.

  113. Drew Henry Says:

    I tried saving/opening your PDF document, but it’s locked and has asked me for a password. Can you UN-lock it, or give me the password?

  114. Raoul Ohio Says:

    Drew Henry:

    Where kind of coffee do you drink? I want to get some! Maybe I will be able to read Knuth V4 tonight!

  115. Drew Henry Says:

    LOL!! Nothing special. Just kinda caffeine sensistive. Guess I lucked-out genetically XD

  116. Drew Henry Says:

    Source: Science Daily…
    “A quantum computer can only function if the information exists for long enough to be processed. The so-called coherence of the qubit ensures that the quantum information remains intact. The researchers have now discovered that the coherence spontaneously disappears over the course of time and with this the stored information as well. This could pose a considerable problem for the development of a quantum computer.

    A quantum computer makes use of the fact that a quantum mechanical system -an electron, an atom or even a larger system such as a superconducting quantum bit – can simultaneously exist in two states. Normally one of the two states disappears as soon as the system comes into contact with the outside world.”

    “Much to their surprise they discovered that the coherence tends to spontaneously disappear, even without external influences. The degredation process is linked to the occurrence of quantum mechanical spontaneous symmetry breaking. In classical physics an equivalent example of this process is spontaneous crystallisation in a solution. At a certain position a crystal is spontaneously formed, as a result of which the fluid structure is broken.”

    Like I said, IF scalable QCs are possible, we’re going to have to somehow create artificial quantum particles that don’t behave like this. If that’s possible. The irony of this? It would take one of today’s PCs to design it! LOL!!

  117. Drew Henry Says:

    I’m voting for DNA/Synaptic computers! Give this a read!
    http://www.bbc.co.uk/news/technology-14574747

  118. Drew Henry Says:

    Another interesting read; “Stacked” 3D cpus!
    http://news.bbc.co.uk/2/hi/technology/6548365.stm

  119. Drew Henry Says:

    National Geographic News: “Israeli scientists have devised a computer that can perform 330 trillion operations per second, more than 100,000 times the speed of the fastest PC. The secret: It runs on DNA.”
    Scalable QCs are already looking obsolete! And this was in 2003… LOL!!
    Give ‘er a read…
    http://news.nationalgeographic.com/news/2003/02/0224_030224_DNAcomputer.html

  120. Drew Henry Says:

    Honestly, I don’t think Scalable QCs will ever make it. Not to sound pessimistic, but… We are already developing cheaper/more practical alternatives. My concluding statement (just to be a smart-ass), “Scalable QCs will never make it in a full fledged fashion. Did you want my account number for that deposit? If-so, send me a private email.”. Lmfao!

  121. Drew Henry Says:

    Oh wait! You wanted a concrete scientific REASON as to “why” Scalable QCs “can’t” be built. Well, for the Nobel Prize (of $100,000.00), here’s my “scientific” answer… HUMAN NATURE! We’re too lazy to do it! ROTFLMFAO!!

  122. Luca Says:

    From a technological and practical point of view, what the logorroic Drew says (no pun intended) is probably correct. DNA computers (or something similar) will be among us, powering our daily web surfing, email checking, twitting and
    facebooking. And finally we will be able to store our 10^10 .jpg images. Smaller is ok. Smallest is probably still too hard.

    Scott, you clearly stated, with your bet, what do you strongly believe. But i want to ask you: in your view, what do you think could be possible barriers to QC (even if with really tiny possibility to be real barriers)? I am referring to both theoretical and practical barriers…

  123. Drew Henry Says:

    If you’ve enjoyed my “logorroic” comments, and are curious about “Drew the artist, from Mass Art”… Check-out my stuff! http://www.AvatarINK.deviantART.com ! And Scott~ If you feel like helping me out with a small donation (as us artists are always poor), I’ll take anything ya give me! At least I added “color” to your blog! Cheers! ~Drew ;)

  124. Raoul Ohio Says:

    #123: Yo! That is the opening line I need for a novel:

    “A ponderous series of QC sketches, drew the artist from Mass Art.”

  125. Drew Henry Says:

    LOL!! Nice :P

  126. asdf Says:

    Scott, tell me something (sort of related to this bet) if you don’t mind. Do you think it’s physically possible to generate an actual random sequence (i.e. Martin-Löf random, a more precise version of Kolmogorov randomness), either by flipping coins, or through some quantum experiment? If yes, does that mean physical experiments can reach into the uncomputable and not just the superpolynomial? It would immediately eliminate the possibility of being able to simulate QM with classical computers. Thanks.

  127. PS Says:

    “If you will it, it is no dream.” -Theodor Herzl

    (Although I agree with this, don’t make bets your booty can’t cover!) –> http://spectrum.ieee.org/tech-talk/semiconductors/processors/why-im-wagering-100000-on-quantum-computing

  128. Scott Says:

    asdf #126: Yes, I think it’s possible to generate Kolmogorov-random numbers using QM. (Indeed, if the quantum measurement outcomes weren’t random, then in the Bell experiment, they would have to be correlated in a way that violates relativity—an observation that isn’t nearly as well-known as it should be!)

    But I would never put that forward as a reason QM is hard to simulate classically. Why not? Well, firstly, if QCs couldn’t do anything more than ordinary computers equipped with random-number generators (as indeed seemed like it might be the case, when all people knew about was the Deutsch-Jozsa algorithm), then there wouldn’t be any reason to get excited about QCs or try to build them. Randomized algorithms have been pervasive in computer science since the 1970s; what makes quantum algorithms interesting is precisely how they aren’t just like randomized algorithms.

    And second, “generate a bunch of random numbers” isn’t a “normal” example of a computational problem (much like “roast a chicken,” another thing that your laptop probably can’t do (though it might generate enough heat to melt chocolate)). If you instead ask, what did you want to use the random numbers for?—and the answer is, run such-and-such a randomized primality algorithm, or estimate such-and-such a probability using Monte-Carlo simulation—then chances are excellent that there’s also a deterministic algorithm that could’ve given you the same answer. Indeed, the prevailing conjecture in computer science today is that P=BPP: i.e., that it’s possible to construct good enough pseudorandom generators to derandomize any randomized algorithm with only a polynomial overhead in running time.

  129. “Whether or not God plays dice, I do” « FerriMagnet Says:

    [...] “Whether or not God plays dice, I do”: [...]

  130. jonas Says:

    There used to be a cash prize for demonstrating scalable quantum computing to be possible: the RSA factoring challenge. Sadly, RSA has retracted the prize.

    Of course, if someone did demonstrate scalable quantum computing, they could probably steal a lot of money by breaking currently used cryptography methods that depend on factorization.

  131. janis Says:

    In comment #14 you said:
    “1. Well, the “prototypical” example would be a new mathematical framework for physics, forced on us by novel experiments, that replaced quantum mechanics (agreeing with QM in its current range of validity), and that led “back” to BPP as the natural class of efficiently-solvable problems, in the same sense that quantum mechanics leads to BQP. Other possibilities should be judged by their similarity to that prototype.”

    I am not sure what are BPP and BQP but let me ask this.
    Say experiment is performed that tests fair sampling assumption for photon detection and let’s say it demonstrates that fair sampling assumption does not hold. That would in turn demonstrate that Bell theorem is not applicable to all currently performed photon experiments undercutting theoretical basis for non-classical nature of photon entanglement.

    Would you consider that a disproof of scalable quantum computing?

  132. Scott Says:

    janis: I’m not sure what the “fair sampling assumption for photon detection” is, or how its failure would undermine the experiments violating the Bell inequality (which, in any case, have been performed with other physical systems besides photons—e.g., superconducting qubits—in every single case agreeing exactly with the predictions of QM). In any case, no, that wouldn’t by itself be a disproof of scalable QM, just of certain specific Bell experiments. The burden would still be on you to convince the physics community of an alternative picture of reality according to which scalable QC is impossible.

  133. Shtetl-Optimized » Blog Archive » My visit to D-Wave: Beyond the roast-beef sandwich Says:

    [...] scalable quantum computation.  For, if nothing else, such a success would prove to the world that my $100,000 is safe, and decisively refute the QC skeptics who, right now, are getting even further under my skin than [...]

  134. Matthew Says:

    You can’t prove a negative. I win money?

  135. Quantum computation vs Copenhagen Interpretation | Are You Shura? Says:

    [...] debates on possibility of quantum computer provoked a specific prize. Between all, Scott Aaronson wrote: [...] whether scalable quantum computing is possible is a [...]

  136. Uncle Al Says:

    A scaled quantum computer will decay by dissipation while it is being configured, running, and being read. Whether that is a fundamental or technological limit on problem size is debatable. Somebody must discover or synthesize a real world usable, deeply state-stable vs. temperature q-bit.

    Grant-funded research will protractedly magnificently fail unless an insubordinate git works weekends off PERT chart and budget. Homeland Severity, ATF, OSHA, and Personnel will quash him. Discovery disciplines management rewarded for enforcing process.

    the Second Law of Thermodynamics conflicts with perpetuum mobiles.

    Counterdemonstration: Hard vacuum envelope containing two closely spaced but not touching in-register parallel conductive plates having micro-spiked inner surfaces. They are connected with a wire containing a dissipative load. One plate has a high vacuum work function material inner surface (e.g., osmium at 5.93 eV). The other plate has a low vacuum work function material inner surface (e.g., n-doped diamond at 0.1 eV). If the temperature is above 0 kelvin, cold cathode emission runs the closed system forever. The plates never come into thermal equilibrium.

    http://en.wikipedia.org/wiki/Work_function#Electron_Work_Functions_of_Elements
    http://www3.ntu.edu.sg/home/ecqsun/rtf/SSC-WF.pdf

    A quantum computer is about loopholes. Politicized science is a business plan – there are no loopholes.

  137. We were promised quantum computers | Backtogeek's Technology Journey Says:

    [...] Institute of Technology, is one believer in the scaled-up quantum computer. He recently offered a $100,000 prize for a convincing proof that such a device could not be [...]

  138. Teresa Mendes Says:

    Dear Scott Aaronson,

    You have often expressed in this blog, your interest in being informed of arguments against the viability of Quantum Computation. Accordingly, in the following couple of paragraphs I present you mine.

    Quantum Computation is Computation based on Quantum phenomena (rather than on Classical, say Mechanic or Electromagnetic, phenomena), Quantum phenomena being those phenomena described and probabilistically predicted by Quantum Theory.

    Quantum phenomena can be classified into two categories:
    Those which are compatible with local-realism and one which is not, known as Entanglement.

    Computation based on local-realistic compatible quantum phenomena would be just a form of analog computation, which is perfectly viable but is at most equivalent to classical computation (Turing machine) and suffers from non-scalability due to signal-to-noise ratio degradation with growing computation size (a well known old problem of analog computation, that has led to its near abandonment and the present prevalence of digital computation). This non-scalability problem of analog computation seems now to be in the process of rediscovery in this context, under the name of ‘decoherence’.

    Such Quantum Computation, though perfectly viable, is totally uninteresting, since it offers no benefits over Classical Computation and plenty of drawbacks when compared to ordinary digital computation.

    Quantum Computation would, thus, only become interesting if it were based on that Entanglement phenomenon predicted by Quantum Theory, for only then might it go beyond the limits of local-realism and, hence, of Classical Computation.

    Entanglement is consequently the indispensable resource for relevant Quantum Computation and the viability of such Quantum Computation rests on whether this predicted phenomenon does indeed exist in the real world.

    It happens that a terrible mistake has been made in the interpretation of experimental Bell tests (experiments which aim to demonstrate Entanglement): The inequalities used to interpret the experiments’ results did not adequately take into account the non-idealities present in the real experimental setups, and hence, the wrong inequalities were used and the wrong conclusion, that Entanglement had been observed, was drawn.

    In fact, when the correct inequalities are used to interpret them, all experimental results to this date are found compatible with local-realism and, hence, no evidence presently exists that Entanglement is a real phenomenon.

    Should you wish further details, please refer to my article ‘Bell inequalities under non-ideal conditions’ recently published in Annales de la Fondation Louis de Broglie (http://aflb.ensmp.fr/AFLB-371/aflb371m746.pdf).

    This does not, of course, disprove the possibility of Entanglement or of relevant Quantum Computation. It simply means that we have no supporting evidence for claiming it to be possible.

    Given that experimental evidence of Entanglement has now been actively sought for 40 years, its absence makes this phenomenon, and hence relevant Quantum Computation, not impossible, but quite unlikely nevertheless.

    I look forward to your comments, if any.

    Best regards,
    JE

    (Posted by Teresa Mendes on behalf of the author.)

  139. Scott Says:

    Teresa Mendes: I’ll leave detailed comments on that paper to the experts in experimental Bell tests. I’ll say, though, that I found the paper extremely unsatisfactory for its lack of discussion of the “big picture.” In particular,

    (1) The author never really comes out and says which tests would convince him that entanglement is there. If you start with a prior probability of zero for entanglement being a real phenomenon, it’s not hard to reconcile that belief with any Bell test by inventing sufficiently elaborate loopholes. As I understand it, the loopholes that people talked about in the 70s and 80s have since been closed—but the skeptics responded by simply switching to other loopholes without batting an eye. Why do I suspect that, if the loopholes discussed in this paper are all closed in a single experiment in the next decade (which I’d guess is more likely than not), the author will still claim that, because some new loophole hasn’t been closed, there’s still “zero evidence for entanglement”?

    (2) The broader point is that quantum mechanics is a wildly-successful framework that, if it’s wrong at all, has to be replaced by something radically different. Yes, it’s important that physicists continue to perform better and better experimental tests of whatever aspects of QM they can, looking for deviations between theory and experiment. But ultimately, I’d say the burden lies with the people who deny some aspect of QM—whether it’s quantum computing, or something even more basic like 2-particle entanglement—to suggest an alternative picture of reality that recovers QM’s century of experimental successes, but in which the aspect in question doesn’t appear. Indeed, that was precisely the point of my bet: that I’m tired of the “defense attorneys” who think they win if they can raise a single point that the prosecution can’t immediately answer, and who don’t acknowledge any need to offer their own alternative picture of the world.

  140. Teresa Mendes Says:

    Dear Scott Aaronson,

    Thank you for your comments.

    The aim of the article is the logical deduction of Bell inequalities applicable to non-ideal EPRB experiments. I acknowledge that you would have preferred that I wrote a different article, discussing what you call the “big picture” but that was not my intention.

    It is not true, however, your statement, (1), that I do not clearly define the criteria for unquestionable observation of Entanglement. These criteria are indeed the core of the article and are presented both in algebraic form (inequalities (41)-(47) as well as the inequalities in pages 22 and 25) and graphically (in Appendices A and B).

    Take, for instance, Figure 3. Inequality (45) is the red line and Quantum Theory is the blue line. If you or anyone else is able to establish a solid experimental point in the triangular region, on the right-hand side of the Figure, which lies above the red line and below the blue line, then Entanglement would have, unquestionably, been observed.

    The problem is that all experimental points, to this date, lie close to the blue line but to the left of the intersection of the two curves, in the region where Quantum Theory and local-realism are compatible, and hence all experimental evidence is within the domain of potential explanation by a local-realistic theory.

    This brings us to your (2) comment. As you have often mentioned it is much easier to recognize a problem than to solve it.

    The development of a new theory of quantum phenomena is not going to be easy and for the scientific community to commit to this endeavour a clear need for it must first be established.

    It is towards the establishment of this need that the article aims to contribute.

    My claim is simply that it is a very serious problem that Quantum Theory predicts a phenomenon which, though hard we have tried to observe it, has not been observed.

    The seriousness of this problem has been downplayed throughout the last 40 years but the problem has not gone away.

    You may, of course, chose to remain in denial of the importance of this problem, but that is not going to solve it and by failing to address this problem in due time we may all end up paying a heavy price.

    Kind regards,
    JE

    (Posted by Teresa Mendes on behalf of the author.)
    ===============================
    Dear Scott,

    After the “scientific” reply by JE, above, and because I’m a non-expert in the field, let me ask you a question of my own:

    In your post you said: “As I understand it, the loopholes that people talked about in the 70s and 80s have since been closed but the skeptics responded by simply switching to other loopholes without batting an eye.”

    Been closed? What other loopholes? As far as I understand it, there have always been just 2 loopholes: one regarding detection efficiency and the other locality. Just one or the other of these has been “closed” in separate experiments. Never have both been closed in the same experiment.

    Don’t you think that there is a risk of misleading investors and politicians into believing that when they are investing in Quantum Computing they are building in solid ground whereas it may well not be the case? Don’t you think that more of this collective effort should be redirected to consolidating the foundations of the field before it is sold as the next
    miraculous technology?

  141. Aram Says:

    This business with loopholes in EPR tests reminds me of gaps in the fossil record, and the alleged problem this causes for the theory of evolution by natural selection. In fact, we have many overlapping pieces of evidence for evolution: DNA evidence, direct observation of evolution, radio-isotope dating, functional relations between species, etc. that would make an overwhelming picture even without a single fossil ever existing.

    Similarly, there is no good explanation of atoms, black-body radiation, the photoelectric effect, the Hong-Ou-Mandel dip, NMR, semiconductors, or a gazillion other things that does not either (a) use quantum mechanics, or (b) make up some special rule for that particular situation in a way that is either logically inconsistent, or contradicts other known experimental results. This is true even without ever thinking about Bell’s theorem. The fact that it’s hard to make single-photon detectors with low dark counts does nothing to undermine the theory, no more than the fact that bacteria don’t leave fossils is not a refutation of the theory of evolution.

    This reminds me of when I once met a new-age sort of person who asked me whether I did “conventional physics” or “quantum physics”. I tried to be as polite as possible, but couldn’t help but point that today essentially ALL physics research is in quantum physics. (And my understanding is that almost all modern biology conceptually relies on the theory of evolution in some way.)

    So yes, it’d be cool to have a loophole-free test of Bell’s theorem. But let’s not confuse this with some validation of quantum mechanics, which is already a well-tested and highly-successful theory.

  142. Scott Says:

    Teresa Mendes #140: Regarding quantum computing, there’s a funny irony here. In the paper, Especial discusses Bell inequality violations that have been observed over microscopic distances, and basically says, sure they might close the other loopholes, but they don’t count because the distances are too small. But entanglement over microscopic distances is all that would be needed to factor enormous numbers using Shor’s algorithm! In other words, even if you believed that QM fails in some yet-to-be-specified way when you try to create entanglement over huge distances, you’d still need some other modification of QM if you wanted to kill quantum computing!

    As for the justification for experimental work in quantum computing: well, as I’ve said again and again, I see only two possible outcomes if such work were pushed to its logical conclusion. The first is that we build a scalable QC. The second is that we learn something profoundly new about physics, which overturns nearly a century of understanding of quantum mechanics in order to explain why scalable QC is not possible. I regard the second possibility as even more exciting than the first (but also much less likely).

  143. Teresa Mendes Says:

    Scott:
    Regarding the Bell tests performed with two qubits at microscopic distances I do assert they are inconclusive but not because of the small distances involved. Those tests are inconclusive because they suffer from measurement crosstalk (the measurement process on one qubit directly influences the state of the other and hence its measurement outcome as was
    indeed experimentally confirmed and measured). If one measurement process directly influences the other measurement process that’s “cheating” and there is then no mystery in the bilateral correlations.

    The irony here is that the best experimental value obtained to date, achieved by Ansmann, is, as I show in the article, in exact agreement with the limit imposed by local-realism for the amount of measurement crosstalk present in the setup. Do you think this is just a coincidence?

    Kind regards,
    JE

  144. Scott Says:

    JE: I don’t know enough to comment on the Ansmann experiment. However, if you’re asking me or others to ditch quantum mechanics, then at the very least, you’ll need to take a broader perspective and address a much wider range of experiments! (Cf. Aram Harrow’s analogy above, to people who think that, if they cast enough doubt on one part of the fossil record, then they’ve destroyed the case for evolution.)

    I’m curious, for example, to know your opinion about the Zeilinger group’s double-slit experiments with buckyballs. Can you explain the results of those experiments, in a way that doesn’t involve entanglement among the position degrees of freedom of the hundreds of particles inside the buckyball?

  145. Teresa Mendes Says:

    Aram (#141):

    As you say: quantum mechanics is a well-tested and highly-successful theory. And you can cite a gazilon examples in multiple areas in which the predictions of quantum mechanics are consistent with experimental results, but these are all compatible with local-realism. Can you really name one,that actually demonstrates non-locality in action?

    All experiments that claim to make use of entangled particles need to confirm entanglement using a violation of some Bell inequality. However, the inequalities they violate are only valid for ideal setups. As soon as you take their non-idealities into account you realize that none of them has actually violated any Bell inequality. How can then one claim to have observed entangled particles?

    The problem, for me, is that students, right from under-graduate level, be it in Physics, Chemistry or now in Computer Science, are told that they have to believe in entanglement because all problems have already been closed, since the 80s. And that is just not true.

    Don’t you see a problem here?

  146. Klas Says:

    So, how is the Canary Islands experiment doing in this context Teresa/JE?
    http://arxiv.org/abs/0811.3129

  147. Teresa Mendes Says:

    (Posted by Teresa Mendes on behalf of J. Especial)

    Scott: I do advocate the replacement of current quantum theory by a local-realistic theory of quantum phenomena as a fundamental theory of Physics in the same sense that we may say that relativistic mechanics has replaced Newtonian mechanics in that role.

    However, just as Newtonian mechanics remains quite useful today as a simpler framework for, for instance, designing mechanical machines in which no part moves at close to the speed of light, so I expect quantum theory to remain a useful computational shortcut to obtain approximate solutions of the new theory in the domain where quantum theory does not conflict with local-realism (which is all quantum phenomena but entanglement).

    This means that I believe that the limits imposed by local-realism are to quantum theory what the speed of light is to Newtonian mechanics. Both theories work beautifully well below those limits but, as we approach them, they begin to fail and ultimately the limits prevail.

    Hopefully this will have made clear to you why I focus on Entanglement and Bell tests: Its where I expect current quantum theory to significantly deviate from experimental evidence, as indeed has been the case, and, ultimately, break down.

    This also means that I have no problem with any two-slit experiment, be it performed with whatever the particle of your choice. The observed phenomena do not in any way conflict with local-realism (i.e. they do not suggest any super-luminal spooky action hypothesis; plain sub-luminal interactions ought to suffice). True, we don’t yet have a local-realistic model of what goes on at the slits when the particle arrives, but the description current quantum theory provides for the experiment also seems to me totally unrealistic.

    Consequently, in my opinion, two-slit experiments remain an open problem and I warmly welcome Zeilinger’s work, for it may well provide surprising results which could prove invaluable to the conception of the new theory.

    Kind regards,
    JE

  148. Teresa Mendes Says:

    (Posted by Teresa Mendes on behalf of J. Especial)

    Klas [#146] : The Canary Islands experiment you refer has been inconclusive, due to insufficient detection efficiency on both arms of the experiment, as also have been all photon-pair based EPRB experiments to this date.

    This means that the observed result is compatible both with quantum theory and with local-realism and consequently does not discriminate between these nor constitutes evidence either for or against Entanglement.

    Let me walk you through to this conclusion.

    La Palma arm: Pg. 7: “… attenuation of Alice’s quantum channel of 20 dB”. This implies a detection efficiency, eta_A, of 10^-2 on this arm.

    Tenerife arm: Pg. 7: “… the attenuation … in Tenerife was measured to be 35 dB”. This implies a detection efficiency, eta_B, of 10^-3.5 = 3.16 x 10^-4 on this arm.

    Applicable Bell inequality for the conjunction of the hypotheses of local-realism and fair-sampling detection (pg. 22 of my .article referenced in Comment#138 above): 2 eta_A eta_B – 4 <= S_N <= 4 – 2 eta_A eta_B

    Since the eta_A eta_B product is of order 10^-6 the upper bound of this inequality is quite close to 4.

    The experimental value of S_N was (pg. 5): S_N^exp = 2.37 +- 0.02, value which fails to violate the upper bound of the applicable Bell inequality by more than 81 standard deviations.

    Kind regards,
    J. Especial

  149. Joy Christian Says:

    Scott,
    You owe me 100,000 US Dollars plus five years of interest. In 2007, right under your nose (when you and I were both visiting Perimeter Institute), I demonstrated, convincing to me, that scalable quantum computing is impossible in the physical world. If you need a reminder of my argument, it has been detailed in my book for your convenience:
    http://www.brownwalker.com/book.php?method=ISBN&book=1599425645
    Joy

  150. Scott Says:

    Joy: ROTFL!!

    Assuming your comment is not a (self?) parody: maybe you should reread the post? You know, the part where I explain that the disproof has to convince me, not merely the would-be disprover? In your case, the situation is much worse: not only are your aggressively-wrong ideas about quantum mechanics unconvincing to me, they’re unconvincing to pretty much everyone on earth besides you, and for excellent reason.

  151. Joy Christian Says:

    Thanks, Scott.
    Can you please tell me what my ideas about quantum mechanics are?
    Also, it would be good to know what method you used (apart from Chinese whispers you are so fond of) to determine what “everyone on earth besides [me]” thinks of my ideas.
    The point of the parody was that there is absolutely nothing that would convince you to part with your 100,000. You know that, and everyone else knows that (here I use the same method as you did to determine what everyone else knows). The whole thing is just a smug scam to look smarter than the rest of us without having to do the hard work. Good luck with that.
    Joy

  152. Scott Says:
      there is absolutely nothing that would convince you to part with your 100,000.

    That’s complete garbage. As I’ve said over and over, what would be necessary and sufficient would be to convince the majority of the physics community. Do you hope and expect to do that? If so, then you can expect my $100,000; if not, then not. If a scientific revolution has taken place only inside the revolutionary’s head, then let the monetary rewards be likewise confined to his head.

    As for your “ideas”: well, I do know that (in paper after paper after paper—one would’ve sufficed if you made any sense), you’ve claimed a “disproof of Bell’s Theorem”, based on trivial algebraic errors combined with personal redefinitions of words such as “local.” Now, the wonderful property of mathematical theorems is that I don’t really need to know much more than that, any more than if you had built your worldview on a “disproof” of Gödel’s or Cantor’s theorems, etc., as countless others have done and will continue to do.

  153. Joy Christian Says:

    Scott,
    I do not want to pick a fight with you, but you did make some derogatory remarks about me in the past without knowing the first thing about me or my work. What you say above again proves that you haven’t read a single paper of mine and do not know the first thing about my framework. Worse still, you do not seem to know what the so-called Bell’s theorem was all about (I, on the other hand, do know what it was all about, because I learned it partly from Bell himself). All you know about my work is hearsay. You are repeating the words of some people who have repeated the words of some other people without having read a single paper of mine themselves. If this is how you want to do science, then fine. It is up to you. I myself prefer to have no opinion on a paper I haven’t read.
    But let us forget about my work. It is not for you. Instead, let me make a counter offer to you. I will give you 200,000 US dollars the day someone produces an actual, working, quantum computer in a laboratory recognizable by me. If I am still alive, I will send you 200,000 US Dollars, multiplied by an appropriate inflation factor. Go build a quantum computer.

  154. Teresa Mendes Says:

    (Posted by Teresa Mendes on behalf of Teresa Mendes)

    Scott: In the introduction you say: “It’s perfectly conceivable that future developments in physics would conflict with scalable quantum computing, in the same way that relativity conflicts with faster-than-light communication, and the Second Law of Thermodynamics conflicts with perpetuum mobiles. It’s for such a development in physics that I’m offering this prize.”

    Does your meaning for “quantum computing”, as used above, require computation beyond the limits of classical computation and, hence, require entanglement, or just computation within the classical limits but using quantum phenomena other than the semiconductor based phenomena already widely used presently and, thus, not require entanglement?

  155. Scott Says:

    Teresa: It requires computation “beyond the limits of classical computation,” which in turn would indeed almost certainly require entanglement.

  156. Teresa Mendes Says:

    Scott: Thank you for clarifying your position.

    Relativity (i.e. local Lorentz symmetry of the space-time manifold) and the Second Law of Thermodynamics are instances of fundamental principles of Physics.

    Do you agree that the only evidence we have that these principles are valid is that no event has ever been observed in which they are violated?

  157. Scott Says:

    Teresa:

      Do you agree that the only evidence we have that these principles are valid is that no event has ever been observed in which they are violated?

    No, I disagree with that statement in the strongest possible terms. Should we say the only evidence we have for the nonexistence of 10-mile-high, punk-rocking unicorns made out of peanut butter is that no one has ever observed one? No, because such an argument would apply equally well to an Earth-like extrasolar planet, or a new variety of giant squid, or a dark matter candidate produced at LHC, or any number of other things that no one has ever seen, but that perfectly plausibly exist. The real reason to doubt my giant peanut-butter unicorn is the amount of violence its existence would do to our most successful explanatory frameworks for understanding the world (in this case, basic principles of both physics and biology). It’s exactly the same reason why I’d need overwhelming evidence before I could take seriously faster-than-light communication, perpetual-motion machines, or complicated local-hidden-variable conspiracies that somehow managed to agree with quantum mechanics on all experiments to date.

  158. Teresa Mendes Says:

    Scott: In your opinion then, if another theory were to agree with quantum mechanics on all experiments to date, it would be just a conspiracy?
    Not even a plausible alternative until further experimental evidence might discriminate between the two?

  159. Scott Says:

    Teresa, if such a theory were ever proposed, I could try to evaluate it — but right now we have no such theory so there isn’t much to discuss. The only ways I’ve seen for trying for trying to avoid quantum mechanics have been ugly, ad hoc, and completely different from one type of experiments to another.

    This is all very well-trodden ground, so I don’t see much point in continuing unless you want to take things in a new direction…

  160. Shtetl-Optimized » Blog Archive » Bell’s-inequality-denialist Joy Christian offers me $200K if scalable quantum computers are built Says:

    [...] what I was perfectly content to do, until Monday, when Joy left the following comment on my “Whether or not God plays dice, I do” [...]

  161. Teresa Mendes Says:

    Scott
    You are right: I think we could keep talking because I do want to take things in a new direction.
    But can we do it in a more private forum?
    You have my email.
    Hoping to hear from you soon.
    Teresa Mendes

  162. Teresa Mendes Says:

    Closed? I had one more question for you …

  163. Teresa Mendes Says:

    So … my new question for you is here:
    http://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/#comment-20131

  164. Shtetl-Optimized » Blog Archive » Why Many-Worlds is not like Copernicanism Says:

    [...] you might remember, I wagered $100,000 that scalable quantum computing will indeed turn out to be compatible with the laws of physics. [...]

  165. The CIA invests in Canadian company’s quantum computer | Sync™ Blog Says:

    [...] scientist and an Associate Professor of Electrical Engineering and Computer Science at MIT and has offered a $100,000 reward to anybody who can prove that scalable quantum computing is impossible. Others, however, are less [...]

  166. Shtetl-Optimized » Blog Archive » Happy New Year! My response to M. I. Dyakonov Says:

    [...] a general principle that would explain why scalable quantum computing is not possible.  (Thus, my $100K prize presumably isn’t relevant to him.)  He even ridicules discussion of such a principle (see [...]

  167. Quantum Computing Hype Cycle and a Bet of my Own | Wavewatching Says:

    [...] Aaronson as a mutually acceptable arbiter.  Scott is blissfully unaware of this, but as he is also the betting kind (the really big ones), I hope he'd be so kind as to help us sort this out if need be. After all, I [...]

  168. My Quantum Debate with Aram Harrow: Timeline, Non-technical Highlights, and Flashbacks I | Combinatorics and more Says:

    [...] Aaronson: (over his blog)) For better or worse, I’m now offering a US$100,000 award for a demonstration, convincing to [...]

  169. Saving phase: Injectivity and stability for phase retrieval | Short, Fat Matrices Says:

    [...] this pales in comparison to the wagers of Scott Aaronson, who inspired the following [...]

  170. Jenae Distel Says:

    I think this is among the most vital info for me. And i’m glad reading your article. But wanna remark on few general things, The web site style is great, the articles is really great : D. Good job, cheers

  171. John Decker Says:

    This is a great article. I love finding new tech blogs like this. It is amazing what new programs are coming out for computers. I think these new technological solutions are going to very effective in many industries.However, I also thing it is important to make sure computer devices are always protected for all organizations. I know a lot of companies these days uses a Server Rack for storage of all important computers.

Leave a Reply