On Deutsches, Shors, and Vaziranis

My friend Robin Hanson kvetches that scientific contrarians don’t get no respect: even if they ultimately turn out to be right, it’s the more cautious, Johnny-come-lately “conservative radicals” who get the lion’s share of the credit. (Like many of Robin’s posts, this one is written in a purely descriptive mode that nevertheless leaves no doubt where his sympathies lie.) And so, as a firmly-entrenched pillar of the hidebound scientific establishment, I thought I’d tell you our side of the story.

In the US, there are companies whose business it is to patent (or buy patents for) every obvious idea they can think of, then sit around and do nothing with those ideas, wait for some other company to build a successful business around one of them, and sue that company for patent infringement. (The textbook example is NTP’s lawsuit against Research In Motion.)

In science, one occasionally sees the intellectual equivalent of these patent-holding companies: people who publish one flaky idea after another with no data or calculations to back them up; and then if, after years of painstaking research, one of their speculations turns out to be right (or even 10% right), scream “they stole my idea!”

But in my experience — and happily for all concerned — the truth usually lies between this extreme and the opposite extreme described in Robin’s post. To illustrate, let’s consider the example of Robin’s that I know best: that of David Deutsch and quantum computing.

Unlike the patent-holding firms, David Deutsch really was a scientific pioneer, thinking deeply about quantum physics and the Church-Turing Thesis back when basically no one else was. His philosophical insights led him to define the quantum Turing machine model, prove its universality, and realize it might have implications for complexity theory. But his one concrete example of a quantum algorithm — how shall I say? — sucked. In particular, he gave an algorithm to compute the XOR of two bits (and know one has done so) using one quantum query and with success probability 1/2. (Later it was realized that success probability 1 is achievable, but that’s still only a factor-2 speedup compared to classical computers.) If this was all you’d seen of quantum computing, you would rightly file it away with dozens of other promising ideas that hadn’t led anywhere.

Unless, that is, you were Ethan Bernstein and Umesh Vazirani. These “conservative radicals” from Berkeley decided to put quantum computing under the microscope of theoretical computer science. The result of their labor — besides a bounteous harvest of complexity theorems like BPP ⊆ BQP ⊆ P#P — was the first example of a black-box problem for which quantum computers gave a superpolynomial speedup over classical randomized ones. Shortly afterward, another conservative, Dan Simon, set out to prove that the speedup of quantum computing was illusory — and ended up with strong evidence (now called Simon’s algorithm) for exactly the opposite conclusion. A year later, yet another conservative — an expert on combinatorics and discrete geometry by the name of Peter Shor — took a close look at Simon’s algorithm, and realized that if you changed the underlying group from (Z2)n to the cyclic group ZN, then you could efficiently compute the period of a black-box function, and thereby factor integers, and thereby break the RSA cryptosystem, and thereby change the world.

A Hansonian might downplay these later achievements — arguing that, were it not for Shor, some other “mainstream mathematician” (a strange description of him!) would’ve sooner or later discovered the factoring algorithm. But it’s equally true that, were it not for Deutsch, some other “renegade physicist” would have come up with quantum Turing machines (and indeed Feynman and Benioff were close). My own judgment is that Deutsch and Shor both made creative scientific contributions of the highest order, and are both deservedly celebrated for them. Indeed, if anyone gets short-shrifted in the usual popular accounts, I think it’s the people in between — like Bernstein, Vazirani, and Simon.

So yes, let’s remember the first person who struck gold, but also the first to realize it wasn’t fools’ gold and the first to figure out how to mine it. Science is a big place; there’s plenty of room for Deutsches, Shors, and even a Vazirani or two.

17 Responses to “On Deutsches, Shors, and Vaziranis”

  1. Dave Bacon Says:

    Or three?

  2. Robin Hanson Says:

    I wasn’t claiming that contrarians get no credit, nor was I claiming that conservatives should get no credit. Yes, both have a role to play. The question is whether the relative credit they get is appropriate to the value they provide and risks they take.

  3. Tyler DiPietro Says:

    I’d have to take a strong exception to Hanson’s thesis. The problem isn’t that scientific contrarians are assigned too little importance, I’d say that they are assigned far too much.

    Just about every crank and crackpot out there, for instance, wears the mantle of Galileo or the Wright Brothers, or even Louis Pasteur or Antonie Lavoisier. And it’s a clever ploy, as the general public is largely enamored of the story of the scientific iconoclast going up against a rigid orthodoxy and prevailing in the end. It usually gets looked over that these cases are few and far between in proportion to the number of cranks who routinely compare themselves to such figures.

    I think it’s rooted in the broader “great man” fallacy of history, whereby a handful of exceptional individuals move and shake the landscape. Science in the real world bears little resemblance to this idea.

  4. anonymous Says:

    “I think it’s rooted in the broader “great man” fallacy of history, whereby a handful of exceptional individuals move and shake the landscape. Science in the real world bears little resemblance to this idea.”

    There are notable exceptions. Newton, for example.

  5. Greg Kuperberg Says:

    Just about every crank and crackpot out there, for instance, wears the mantle of Galileo or the Wright Brothers, or even Louis Pasteur or Antonie Lavoisier.

    The Wright brothers are a funny example, although in the end an apt one. They built the first convincing airplane, because they discovered the key idea of three-axis flight control, and because their engines and airfoils were more efficient than what came before. But this was not the first airplane, and they took full advantage of prior expertise. They also never built a useful airplane, because there were other key ideas that were beyond them. Instead, they convinced themselves that they were THE inventors of heavier-than-air flight. They bottled up American aviation with lawsuits. France surged ahead of America in aviation partly because of the Wright Brothers’ obsession with priority.

    Along the way, the Wright Brothers skewed American history books in their favor.

  6. Tyler DiPietro Says:

    anonymous,

    I agree that Newton was certainly exceptional, but I would also argue that even his historical reputation is a bit overblown. He’s generally credited with inventing the differential and integral calculus, yet his theory is generally regarded as inferior to that of Leibniz. He also failed to apply his laws of motion to planetary orbits, leaving work to be completed by Laplace.

    Greg,

    Yes, the Wright Brother’s debacle is certainly more complicated than the general perception would have it. But at the Wrights had some useful ideas. The be perfectly honest, most contrarian ideas don’t even get that far. Examples of contrarianism in recent memory include Linus Pauling’s claims that cancer could be cured by Vitamin C, or Lynn Margulis jumping on the bandwagon of those who deny that HIV causes AIDS.

    There is one thing I agree with: science is biased against contrarians and generally conservative. But I think this is a good thing. There are far more loony contrarian ideas out there than there are useful ones.

  7. Greg Kuperberg Says:

    But the Wrights had some useful ideas.

    They had brilliant ideas, not just useful ones. But single-handed invention is another matter.

    Although single-handed invention is rare in history, there are some interesting examples. (In mathematics and CS too, as well as in engineering.) Bartolomeo Cristofori invented the piano all by himself, based only on long-available examples such as harpsichords. I read somewhere that he was so far ahead of his time that his design was substantially un-invented by expedient imitation. It took most of a century for some of his good (but expensive) ideas to come into vogue.

  8. Bram Cohen Says:

    I find Robin’s essay completely unconvincing, mostly because of his examples. Of his seven claimed examples of people who haven’t gotten a fair shake because they’re contrarians, three of them – Ted Nelson, Eric Drexler, and Doug Lenat, are, to put it politely, extremely overhyped.

  9. Robin Hanson Says:

    In science, one occasionally sees … people who publish one flaky idea after another with no data or calculations to back them up.

    What sort of resources do these people thereby get? Do they win grants, tenure, or awards? What is the evidence that they are over-rewarded?

  10. Greg Kuperberg Says:

    Do they win grants, tenure, or awards?

    They certainly get to keep tenure, and sometimes they do get grants. That’s part of the merit of the tenure system, that once you’ve had some proven success, you can speculate as much as you want. In fact, because of the bedrock of tenure, academia is at least more accommodating of contrarians than the rest of society. To be sure, we still fall short of reasonable intellectual norms sometimes, but you’re criticizing the part of society where things are the best.

    For that matter, your question here drifts away from the title of your essay, which is “Even when contrarians win, they lose”. I’m totally with Scott on this one; it’s just not true. Your argument for it overlooks a key effect, which is that Mr. Standard has to face a lot more competition than Mr. Contrarian. Academia is full of people whose research is perfectly respectable and standard, even difficult; but who don’t get grants, or don’t get tenure, or don’t get a job at all just because they’re in second place. There is a palpable indirect incentive to succeed in a wild and crazy way.

  11. Sumwan Says:

    I don’t know whether Narkevic should be considered standard or contrarian but this looks like a nice story :
    http://blog.wired.com/wiredscience/2007/09/student-finds-m.html

  12. Peter Shor Says:

    Hi Scott,

    You’ve left Richard Jozsa and Giles Brassard, who both played key roles, out of the story completely. Why does Umesh get to be a conservative radical while I get labeled a conservative? And finally, maybe a lesson to be drawn from this history is that some of these contrarians get labeled weirdos because they really are weirdos. Anybody who has visited David Deutsch will have to admit that he is somewhat eccentric. Maybe people who ignore scientific orthodoxy are likely to flaunt social conventions as well.

  13. Scott Says:

    Thanks, Peter! Yes, Richard and Gilles both played key roles and I shouldn’t have omitted them. I have visited David Deutsch and I do admit he’s somewhat eccentric. And the labels “conservative” and “conservative radical” were of course meant ironically; as such they’re pretty much interchangeable.

    –Scott (just arrived yesterday in Riga, and about to tour the Latvian countryside with Andris Ambainis and his niece)

  14. Peter Shor Says:

    Have fun!

  15. mitchell porter Says:

    My blood is boiling after just seeing a week-old story reporting the surprising news that “Parallel universes exist – study”. And Deutsch is one of the major culprits, so pardon the digression while I vent.
    http://www.channel4.com/news/articles/science_technology/parallel+universes+exist++study/838052

    Unsurprisingly, the proximate source of the story is New Scientist, the magazine that reports comparable “breakthroughs” just about every month, it seems…
    http://groups.google.com/group/alt.kq.p/browse_frm/thread/9631b2e37ba5e7a2/fb3202c9c5b71228#fb3202c9c5b71228
    an article which was in turn occasioned by “Many Worlds at 50″, a conference at Perimeter Institute…
    http://www.perimeterinstitute.ca/manyworlds/
    at which one of Deutsch’s group gave a talk.
    http://www.mail-archive.com/everything-list@eskimo.com/msg13810.html

    My objection is not to the postulation of “many worlds”, it is to the incredible sloppiness with which the concept is developed, which makes the dogmatism of certain proponents even more ridiculous. A good starting point might be Deutsch’s opening remarks in his book “The Fabric of Reality”, where he claims that the outcomes of double-slit experiments can be explained by the doings of “shadow photons” in the universes next door. Well, that’s an interesting claim! Can you show me the equation which describes how the photons in this universe are affected by the photons in the other universes? Why, that’s just the Schrodinger equation. Well, in that case, can you show me how to read the Schrodinger equation as a statement about the interactions of photons in neighboring universes? But of course he can’t. Instead, we are to take up the wavefunction of the universe, chop it up into parts that look sort of classical, and believe that those are the “worlds”. And we get to ignore any messy left-overs like nonzero offdiagonal terms because they’re small, and besides, “world” is just a heuristic concept anyway… As I said, and as you can see, the carelessness, the doublethink, the substitution of rhetoric for rigor, has driven me up the wall.

    For slightly more technical complaints from myself, see…
    http://www.sl4.org/archive/0305/6607.html
    http://www.mail-archive.com/everything-list@eskimo.com/msg00009.html

    And Adrian Kent (one of the Perimeter event’s organizers) seems to have made comparable criticisms.
    http://front.math.ucdavis.edu/9703.4489
    http://arxiv.org/abs/0708.3710

  16. Brian Wang Says:

    >In science, one occasionally sees the intellectual equivalent
    >of these patent-holding companies: people who publish
    > one flaky idea after another with no data or calculations to
    >back them up; and then if, after years of painstaking
    >research, one of their speculations turns out to be right
    > (or even 10% right), scream “they stole my idea!”

    The case that I most familiar with is Eric Drexler and nanotechnology. He did work that had calculations to back it up. He and the people he worked with founded the Foresight organization which held regular scientific conferences which from 1980 to 1998, they were the ones who were advancing the work of both wet and dry nanotechnology. DNA nanotechnology, protein nanotechnology, mechanosynthesis were all explored at a significant level.

    When Nanotechnology was funded in a major way, those who took advantage of the interest generated by Drexler not only hijacked control of all of the funding but also some of them chose to ostricize and smear Drexler as part of a strategy to eliminate all controversy and ensure continued funding.

    This is described in detail here
    http://www.wired.com/wired/archive/12.10/drexler.html

    In this case any part of nanotechnology that starts achieving any real world success is usually allowed to crossover to the “conservative, mainstream side”. Any part that is competitive with what the funding in-crowd wants to continue to have funded is downplayed as much as possible. This downplaying process is easier for things like mechanosynthesis which requires some improved tools in order to start achieving significant goals. Although there has been some theoretical and experimental success.

    http://www.molecularassembler.com/Nanofactory/Publications.htm

    http://www.molecularassembler.com/Nanofactory/AnnBibDMS.htm

    So the problem is not so much “they stole the idea”. It is that work is done on some of the ideas and advance it and then deny that it was part of the prior large amount of conceptual work and indicate that Drexler and Drexler related work only represents something which is impossible.

    They work in a portion of the same space, take the popularity of the nanotechnology label ( the popularization of the vision is clearly related to Drexler’s popular books, the congressional hearings in 1992 that laid the foundation for later funding were inspired by the vision articulated and popularized by Drexler. see the wired article) in order to get funding and then prevent even 5% of the budget from going to work to prove or disprove the high potential area of mechanosynthesis.

    “we take the label that you popularized and hijack the funding and then we work to prevent you and people who worked with you from receiving any funding to explore what we view as a competing idea.”

    The problem I see is when the current and historically funded mainstream has to prevent any upstart, competitive concept from getting a toehold. To prevent a toehold, money for an initial validative study has to be blocked. The trashing of a radical may be a by-product of this process.

    Mainstream and funding hog Tokomak fusion has to block any other fusion concepts from getting any significant funding. So that they can stick to their 80 year multi-billion per year development effort. 40 years in the past and another 40 or so years projected.

    Mainstream chemical rockets and the traditional NASA space efforts (space shuttle, International space station, new Moon and Mars programs) are all about political pork and continuation of past jobs. It is only incidentally about achieving results in space. There are better ideas and plans, which are ignored and unfunded because they do not create or maintain enough jobs on the ground. Meanwhile, those who criticize space development point to the lack of achievements as an indication that space development and colonization is impossible, when the real case is that a political pork machine that is labeled a space program has not delivered results in space.

    So I think that 80% of funds should go to conservative concepts and plans but that there needs to be more accountability for achieving results and 20% on allowing outlying ideas and plans to compete and prove their worth.

  17. Brian Wang Says:

    In my view there is less of an issue in quantum computing, because there is not a lot of non-private money in play. There is also no “dominant only way to do things” which is sucking up all of the funding oxygen. A reasonable level playing field for ideas and approaches to compete on their own merits is sufficient.

    Just having some people argunig over credit is irrelevant to whether a good idea is being developed. My main concern is that the process allow and encourage the best ideas to be developed.