Shtetl-Optimized

The above is a question that’s interested me for as long as I can remember, though I avoided blogging about it until now.  See, unlike many libertarian economist Ayn-Rand types, I don’t actually like asking social or political questions the very asking of which marks you as eccentric and Aspergerish.  I’d rather apply myself to proving lower bounds, popularizing quantum mechanics, or other tasks that are (somewhat) more respected by the society I depend on for my dinner.  And I’d rather pick battles, like evolution or climate change, where truth and justice have well-connected allies on their side and a non-negligible chance of winning.  For years, I’ve been studying the delicate art of keeping my mouth shut when what I have to say will be deeply unpopular—and despite lapses, I’ve actually made a great deal of progress since (let’s say) the age of 14.

There are times, though, when a question strikes such an emotional chord with me that I break down and ask it in spite of everything.  Such a case was provoked by this story in the New York Times a few weeks ago (registration required), about a 17-year-old girl who was jailed for creating a MySpace page.

At worst, Hillary Transue thought she might get a stern lecture when she appeared before a judge for building a spoof MySpace page mocking the assistant principal at her high school in Wilkes-Barre, Pa. She was a stellar student who had never been in trouble, and the page stated clearly at the bottom that it was just a joke.

Instead, the judge sentenced her to three months at a juvenile detention center on a charge of harassment.

She was handcuffed and taken away as her stunned parents stood by.

“I felt like I had been thrown into some surreal sort of nightmare,” said Hillary, 17, who was sentenced in 2007. “All I wanted to know was how this could be fair and why the judge would do such a thing.”

The answers became a bit clearer on Thursday as the judge, Mark A. Ciavarella Jr., and a colleague, Michael T. Conahan, appeared in federal court in Scranton, Pa., to plead guilty to wire fraud and income tax fraud for taking more than $2.6 million in kickbacks to send teenagers to two privately run youth detention centers run by PA Child Care and a sister company, Western PA Child Care.

The article expresses disapproval about the corruption of the judge and the severity of the sentence, but seems completely unfazed by the idea of an American citizen standing before a judge to answer for a satirical website.  And this is actually understandable given the context.  While children’s rights law is a notoriously murky area, it seems fair to say that children’s “individual rights” (free speech, due process, etc.) are generally thin to nonexistent, certainly in the US and probably elsewhere too.  So for example, if Ms. Transue had been punished by her school rather than a court for setting up her website, it probably wouldn’t even have been news.

The law strikes me as inconsistent in its attitude toward minors: first it denies them individual rights, on the ground that they’re not yet capable of exercising moral judgment.  But then it punishes them harshly for all sorts of offenses (in many cases more harshly than adults), thereby presupposing the moral responsibility they’re not yet supposed to have.

Now, if I had political capital to spend, I would not want to spend it on children’s rights, just as I wouldn’t want to spend it on legalizing marijuana.  In both cases, I’m guessing that lions will embrace vegetarianism and the polynomial hierarchy will collapse to the 23^rd level before American law changes significantly.  But I’ve also noticed an interesting difference between the two issues.  In the case of marijuana, almost every brainful person I’ve met (whether “liberal” or “conservative”) has agreed that the current American laws are an absurdity; that all the power is on one side of the issue while all the evidence and arguments are on the other side; and that eventually, one imagines this will all be as obvious to everyone as it’s obvious today (say) that contraceptives should be legal.  It’s just a question of time, of the regrettable generations-long delay between the inarguable and the acted-upon.

By contrast, when it comes to granting legal rights to children, people whose intelligence I respect seem compelled to give really bad arguments for the status quo—arguments that (so to speak) a 12-year-old could demolish.   (I know of only two famous intellectuals who’ve publicly advocated changing things: the educator John Holt and the quantum computing pioneer David Deutsch.  Anyone know of others?)

For simplicity, let’s restrict attention to the question of whether suffrage should be extended to a large class of people under 18: either by lowering the voting age (say, to 12 or 14), or better yet (in my view), by giving any citizen the vote once he or she reaches a certain age or passes a test of basic civics knowledge analogous to a driver’s-ed or citizenship test.  (Just like with the plurality voting system, showing that the current rule is terrible is the easy part; figuring out the best among many possible better rules to replace it is the harder and more interesting problem.)

I’ll also restrict attention to the US, even though most of the discussion applies more broadly.  Finally, I’ll use the word “children” to mean “children and teenagers”; I like it more than legal terms like “minors” or “people under 18.”

As John Stuart Mill pointed out in The Subjection of Women, it’s not clear how you make an affirmative case against a form of discrimination: pretty much all you can do is stand around, wait for people to suggest pro-discrimination arguments, and then answer them.

People say: should toddlers have the vote?  Should embryos?  You have to draw a line somewhere!  But the real question is: granting that one has to draw a line, granting that any line will be arbitrary and unfair, can’t one at least make it vastly, manifestly less unfair than the current line?  To give two examples: if you can be imprisoned for a crime, shouldn’t you be able to vote?  If you can demonstrate knowledge of American politics and history well beyond that of the average voter, shouldn’t you be able to vote?  (In 1971, the 26^th Amendment lowered the voting age from 21 to 18, on the ground that anyone who can be drafted into the military should be able to vote.  It seems to me that one can take that same logic much further.)

People say: if you want to grant the vote to sufficiently knowledgeable children, then shouldn’t you also take it away from sufficiently ignorant adults?  Well, it’s going to be quite a while before the glorious age of the intellectual meritocracy, when all shall submit willingly to Plato’s philosopher-kings.  And before that happens, we’ll have probably all upgraded ourselves to post-Einsteinian superintelligences anyway, by downloading the requisite applet from the iBrain store—so the question of what to do with the ignoramuses will be moot.  Until that day, I’m content to imagine something that’s merely politically impossible (like giving the vote to anyone over 18 and to all knowledgeable minors), rather than 2 to the politically impossible power.
(Notice also that slippery-slope arguments get invoked every time any new step away from medieval morality is on the table: if we legalize gay marriage, then don’t we also need to legalize polygamy, etc. etc.  Again, the fact that any rule we can think of is imperfect, doesn’t imply that some rules we can think of wouldn’t be much better than the current ones.)

People say: if you’re going to grant votes to some children and not others on the basis of a test, isn’t that elitist?  But why isn’t the driver’s-ed test or the citizenship test given to immigrants similarly elitist?

People say: even supposing they can pass some test, doesn’t everyone know that children are too immature and unwise to be entrusted with awesome burden of democracy?  Ah, and who are the mature, wise elders, those paragons of Enlightenment rationality, who twice elected George W. Bush?  If minors could vote, wouldn’t Bush have almost certainly lost both times—thereby averting (or at least mitigating) the global disaster from which we’re now struggling to recover?  Or was that a fluke: a case of the young disproportionately getting the right answer by accident, while the older and wiser made one of their rare mistakes?  Or am I being ‘reductive’ and ‘simplistic’?  Does our belief in the political immaturity of the young belong to that special category of truths, the ones too profound to be confronted by data or experience?

People say: but children only care about the present; they lack foresight.  But isn’t it children pressuring their parents to worry about climate change and the Amazon rainforest, more often than the other way around?  And isn’t that just what you’d expect, if children formed a self-interested bloc much like any other; if they grasped (some clearly, others less so) that they’d eventually run the planet, and if they consequently cared more rather than less about the distant future? So if—like me and many others—you see excessive short-term focus as the central tragedy of politics, then shouldn’t you be chomping at the bit to let more young people vote?

People say: but children will just vote however their parents tell them to.  But to whatever extent this is true, doesn’t it undercut the previous fears, of immature brats voting in Mickey Mouse for president?  And if millions of wives in conservative parts of the country still vote however their husbands tell them to, is that an argument for denying those wives the vote?  And don’t most people of every age simply vote their demographics?

People say: but only a tiny minority of precocious, high-IQ children could possibly care about voting—and while you might have a point in their case, you ignore the 99% of children who only care about the latest Hannah Montana accessory.  But if less than 1% of Americans want to run for Congress, or file a Freedom of Information Act request, or do computer security research that’s outlawed by the DMCA, does that make those rights unimportant?  At the risk of the usual charge—elitism—doesn’t the tiny minority that cares about such things tend to have a disproportionate impact on everyone else?

Also, suppose that in Victorian England, only a tiny percentage of women cared about politics rather than the latest in corsets and garden mazes: should that have carried much weight as an argument against women’s suffrage?  What if the denial of rights to a whole class of people is a reason why many in that class focus on trivialities, rather than the other way around?

People say: but it’s obvious that children shouldn’t vote, because they’re not economically self-sufficient.  Again, wouldn’t it save time to pass these arguments through the “Victorian England / women’s suffrage” filter before making them, rather than after?

People say: ah, but there’s no comparison between the two cases, since unlike Victorian women, children will be able to vote once they’re old enough.  Right, and what about the children who die before they’re 18?  Even ignoring those cases, is it obvious that it’s okay to deny people their fundamental rights, provided that those people, in turn, will someday get to deny fundamental rights to others?

People say: at any rate, denying the vote to children doesn’t seem to have any particularly bad consequences.  I wish I agreed; the reasons why I don’t are really a topic for another post.  Briefly, though, I think our culture’s insistence on treating children as children even after those children are ready to be treated as adults is

1. weird from the standpoint of anthropology and evolutionary psychology,
2. an excellent prescription for turning out adults who still think the way children are supposed to,
3. a useful tool for cracking down on unwanted precocity of all kinds, and
4. a terrific way to make up for the unfortunate encroachments these past few centuries of justice, civilized behavior, and protections for the nerdy and weak, by keeping human beings in such a savage environment for the first years of their lives that by the time they’re let out, the new Enlightenment nonsense has difficulty gaining a foothold.

(For more on similar themes, see Paul Graham’s justly-celebrated essay Why Nerds Are Unpopular, or my Return to the Beehive.)  The denial of suffrage is just a small part of the story—nowhere near the most important part—but it works as an example.

Finally people say: that’s just the way things are.  This argument—also useful for justifying chattel slavery if you happen to live in 1845—is, at last, a sound one. I agree with it and accept it.  Because of this argument, I’ll now admit that this entire post has been nothing more than an intellectual exercise, a way for me to procrastinate from answering email.  I don’t actually believe any of what I wrote—nor, for that matter, do I believe anything.  Still, purely out of academic curiosity, I’d be interested to know: are there any other arguments for the legal status of Hillary Transue, besides its being the way things are?

Follow

Most Respected Profeser Sir Dr. Scot Andersen: I wish to join your esteemed research group. I have taken two courses in Signal Processing at the Technical College of Freedonia; thus, it is clear that I would be a perfect fit for your laboratory at MIT. Please respond immediately with a specific date for the commencement of my studies.

Scott, did you hear the news yet?? There's a link on Slashdot about how to solve NP-complete problems in linear time using Peanut M&M's! There's also an interview with Dr. Doofus McRoofus in New Scientist, where he says quantum computing proves the reality of time travel! Plus, a mathematician at the University of Trivialshire has apparently announced a new number system where you can take not only square roots, but also the square roots of square roots! What do you think about all these developments? Please blog your reaction ASAP!

Dr. Aaronson, while your writings are of some interest, you have nevertheless a great deal to learn from my more refined insight and sagacity. In particular, your references to the so-called "theory of evolution" are surprisingly naïve and simplistic. You seem wholly unaware of the profound conundrum of how a system with a low degree of order can obtain progressively higher degrees of order, in direct contradistinction to the Second Law of Thermodynamics... [17 pages omitted] Please let me know when you will be available to enter into a sustained dialogue about the flawed presuppositions underlying empirical positivism.

Hello, I am interested in leaning about computer science !! Please give me some links to get started.

Brief responses here. Back in the day, I prided myself on answering emails individually, and vowed I’d never become the sort of academic who puts an FAQ on his home page and tells people to read it before emailing him. And I kept that vow — three whole months into starting a faculty job.

Follow

Needing a token of my years in Waterloo, I figured it was finally time to trade in my Pleistocene Nokia phone for a BlackBerry. So I used some of my startup funds to buy a BlackBerry 8830 World Edition from Verizon. What particularly excited me about this model was that it was advertised as having a built-in GPS receiver — meaning (or so I thought) that I’d be able to pull up Google Maps wherever I was, and never get lost again.

Well, today the phone arrived, and I found out that Verizon has disabled the GPS (see here, here, and here). The reason, apparently, is that at some unknown time in the future, it plans to sell an inferior navigation service for $10/month, and doesn’t want people getting for free what it will later rip them off for.

I’ve been having fun imagining the conversation between Mike Lazaridis (the founder of Research in Motion, the Waterloo-based company that makes BlackBerries) and Verizon:

Lazaridis: It’s an abomination! As long as I draw breath, I’ll never agree to your crippling my invention!

Verizon CEO (breathing heavily): Young Lazaridis, come over to the Dark Side.

Lazaridis (pause): Actually, how much are you offering? I’ve been needing cash, ever since blowing all those millions on the Perimeter Institute and the Institute for Quantum Computing…

Some will say I’m a sucker, buyer beware, etc. The more sympathetic will call me a victim of false advertising — indeed, of the exact sort of corporate behavior that my best friend Alex Halderman and his adviser Ed Felten have battled for years with some spectacular successes.

Recently I attended a talk by the legendary free-software activist Richard Stallman, who thundered like an Old Testament prophet about human beings’ inalienable right to understand, modify, and share the technology they own. At the time I agreed with Stallman intellectually but found him a bit obsessive. Now I have my own dog in this fight.

I’ve always known that American cell phone companies are evil: they have shitty, unreliable networks, enormous advertising budgets, and miniscule R&D budgets. But Verizon has taken things to a level even I wouldn’t have predicted.

We’re not living in anything close to the efficient market dreamed of by my economist friends like Robin Hanson. The invisible hand has palsy and four missing fingers. And the proof is that, when a company like Verizon pulls a Monty Burns, there’s almost no risk it runs — almost nothing it fears. Indeed, about the only risk it does run is that some of its customers might have blogs — and that some of the savvier readers of those blogs might figure out how to hack the crippled phones and share that information with the world…

Follow

Today’s topic is one I was hoping I could avoid, since I know that my stance will alienate many of my own supporters. But after I read the comments on this post by Bill Gasarch, and reflected on all the men, women, and children who were dispossessed of their land while the world did nothing, I realized I could no longer remain silent.

Most of you will know what I’m talking about, but for those who don’t: I urge the readers of this blog to join me in severing all academic ties with the settler state of New Zealand, until that state makes complete restitution for its historic crimes against the Maori people. That means no more giving seminars at the University of Auckland. No more reading papers with “ac.nz” in the author’s email address. Indeed, no more involvement with any physics or climate research in Antarctica, the flights to which leave from Christchurch.

Some will say my proposed boycott smacks of anti-Kiwi prejudice. But in reality, some of my best friends are Kiwis. Furthermore, I hope and expect that those Kiwis who care about justice will embrace my proposal, for the chance it affords their rogue state to confront the lies and denial upon which it was founded.

Others will ask: if we’re going to boycott Kiwi scientists over the dispossession of the Maori, then why not boycott Australian scientists over the aboriginals, Chinese scientists over the Tibetans, or American scientists over the Native Americans, Iraqis, Vietnamese, or Guatemalans? I trust, however, that sensible people will recognize this question for the Kiwi diversionary tactic that it is. For what could Australia, China, or the US possibly have to do with New Zealand? Until the Kiwis acknowledge that the issue is them and only them, there is no hope for progress.

Even in a world rife with violence and despair, I can think of no single issue with a greater claim upon our conscience. And that is why I ask again: who will join me in severing all academic ties with New Zealand?

Follow

If you reject an overwhelming consensus on some issue in the hard sciences — whether it’s evolution, general relativity, climate change, or anything else — this blog is an excellent place to share your concerns with the world. Indeed, you’re even welcome to derail discussion of completely unrelated topics by posting lengthy rants against the academic orthodoxy — the longer and angrier the better! However, if you wish to do this, I respectfully ask that you obey the following procedure:

1. Publish a paper in a peer-reviewed journal setting out the reasons for your radical departure from accepted science.
2. Reference the paper in your rant.

If you attempt to skip to the “rant” part without going through this procedure, your comments may be deleted without warning. Repeat offenders will be permanently banned from the blog. Life is short. I make no apologies.

Scott Aaronson
Rebel for the Scientific Consensus

Update (4/11): I am, of course, under no illusions whatsoever that my requirement of having published a relevant peer-reviewed paper will eliminate all tinfoil-hat rants from the comments section. My hope, rather, is that it will make those rants that I do receive more interesting and original.

Follow

Look, I promise this will be the last D-Wave post in a while. But there have been two developments that, as Planet Earth’s primary D-Wave skepticism clearinghouse, I feel a duty to report.

First, Jason Pontin’s article in the Sunday New York Times has appeared. It’s not perfect, but to get in a description of quantum computing that was even somewhat accurate required a long, word-by-word and phrase-by-phrase battle with the editors of the business section.

Second, Umesh Vazirani sent me a document summarizing the skeptical case against D-Wave, which anyone coming to this blog from the Tech Review or New York Times might find helpful. (Hey, as long as you’re here, stick around for a bit!) I’ve posted Umesh’s criticisms below.

Finally, Happy Easter from all of us here in the shtetl!

Reasons To Be Skeptical About D-Wave’s Claims

by Guest Blogger Umesh Vazirani

1. An Unconvincing Demo: D-wave’s demo consisted of a computer in a box that could solve simple problems. We have no way of knowing whether the computer in the box was an ordinary classical computer or a quantum computer. For the problem the computer solves — finding ground states for 16 bit Ising problems — a classical computer would work just as quickly. This demo is the only public evidence D-wave has presented in support of its claims.

2. A Physics Breakthrough?: Achieving 16 coherent superconducting quantum bits would be quite a breakthrough. Physicists working on superconducting qubits have not been able to achieve more than two coherent quantum bits in the lab. In the absence of evidence from D-Wave that their 16 qubits are coherent, scientists are understandably skeptical. If D-Wave’s qubits are not coherent, as many scientists suspect, their computer would be classical, not quantum. This would still be consistent with the results of the demo, since the decohering qubits would act like classical random bits, and the adiabatic computer would act like a classical computer implementing simulated annealing, which would be quite fast for a small 16 bit Ising problem. It is possible to test the quantum states of D-Wave’s computer for coherence, but Geordie Rose’s statements suggest that no such tests have been made.

3. Claims of Big Algorithmic Breakthrough Without Evidence: 16-bit quantum computers are useless from a practical standpoint because they can only solve very small problems that could just as easily be solved using a classical computer. Thus, D-Wave’s demo, even if it really was a quantum computer, will only be practically useful if the technology will scale to the larger problems that cannot be solved with a classical computer. Unless D-Wave has made a major algorithmic breakthrough as well as a major practical one, however, D-Wave’s computer, even if implemented with thousands of qubits, will not provide a speedup over classical computers. D-Wave does not implement a general purpose quantum computer, only one that can implement adiabatic optimization. They wish to use it to solve the Ising model, which is thought to be beyond the reach of classical computers, but there is no known efficient algorithm for solving the Ising model using this adiabatic approach. It is possible to achieve a quadratic speedup for unstructured search problems using adiabatic optimization, but that result requires an ability to tune the rate of the adiabatic process — something which appears to researchers to be extremely hard if not impossible for the Ising problem. Geordie Rose’s public statements suggest that he doesn’t understand this issue, which makes computer scientists skeptical that any breakthrough has been made.

To summarize: For D-Wave to achieve a practically useful quantum computer using their technology, they would have to have made a breakthrough in physics, as well as a breakthrough in the design of their algorithm. Scientists are skeptical both because D-Wave has failed to provide any supporting evidence, and also because their public statements suggest a lack of understanding of the issues involved.

You might ask why researchers are putting so much energy into debunking the D-Wave hype. One reason is that QC researchers feel a responsibility to the public to not overhype quantum computers. Quantum computing is an exciting field that has caught the imagination of the public. This is a good thing. But if the quantum computing effort starts to mingle fact with fiction, then the entire effort loses its credibility.

Another reason is that D-Wave’s unsupported claims are undermining the efforts of the researchers who are working very hard on these problems. It’s as if there was a new biotech company claiming to be at the brink of a revolutionary cure for cancer. If it is true, it is great, but if it’s not, then it undermines the efforts of the legitimate cancer researchers.

Follow

Last night Jason Pontin, the Editor-in-Chief of MIT’s Technology Review, published a hard-hitting article about D-Wave, the Vancouver startup that claims to have built “the world’s first commercial quantum computer.” A condensed (and, alas, considerably mangled and dumbed-down) version of his article will appear in Sunday’s New York Times.

Jason wrote to me a couple weeks ago and said that, while he knew that most journalists had gotten the D-Wave story wrong, he was determined to get it right, and wanted my help in understanding the computer-science issues. He didn’t have to ask me twice.

Since I come across as pretty harsh on D-Wave in the article, I think it’s worth recalling how we got to this point. When the D-Wave story broke, my first reaction was to give them some benefit of the doubt (as you can see from the mild tone of my “Orion Anti-Hype FAQ”). So what changed? Well, four things:

1. I asked Geordie Rose (the founder of D-Wave and sometime commenter on this blog) twice for actual information about the speedup D-Wave claimed to be seeing over classical algorithms, and he never provided any.
2. Instead of answering my and others’ technical questions, D-Wave decided to attack academic science itself. Here’s what Herb Martin, the CEO of D-Wave, told an interviewer from ITworld: “Businesses aren’t too fascinated about the details of quantum mechanics, but academics have their own axes to grind. I can assure you that our VCs look at us a lot closer than the government looks at the academics who win research grants.” The track record of companies that engage in this sort of behavior is not good.
3. I read article after article claiming that quantum computers can solve NP-complete problems in polynomial time. I reflected on the fact that a single one of these articles will probably reach more people than every quantum complexity paper ever written.
4. It became clear, both from published interviews and from talking to Jason, that D-Wave was doing essentially nothing to correct journalists’ misconceptions about what sorts of problems are believed to be efficiently solvable by quantum computers.

Update (4/6): Geordie Rose has responded to me. A few responses to his response:

• I apologize for getting the CEO’s name wrong. I’d originally written Herb Martin, but then noticed that the ITworld article referred to him as “Ed Martin” and therefore changed it. This seems like another case where D-Wave has to work harder to correct journalists’ misconceptions!

• In a discussion with Geordie on my blog, following my Orion Anti-Hype FAQ, I asked:
  

  You say you’re seeing a speedup in your experiments — but (1) how big of a speedup, and (2) do you mean compared to the best-known classical algorithms (like simulated annealing), or compared to brute-force search?

  Then, in another discussion with Geordie following my Speaking truth to parallelism post, I asked him again:

  I’m certainly glad that you’re not claiming an exponential speedup. But at least based on the evidence I know about, whether you’re seeing a quadratic speedup — or indeed any asymptotic speedup — is very much open to question. Hence the question I asked you earlier: have you compared the empirical scaling for your adiabatic algorithm to the empirical scaling for the best classical algorithms like simulated annealing? If so, what were the results?

• Geordie now says that “the only way scaling can be extracted is empirically, and we can’t build big enough systems (yet) to answer scaling questions.” Thanks; that’s actually extremely helpful to me. I must have gotten a wrong impression from some of D-Wave’s previous statements. For example, here’s from D-Wave’s recently-released “Introduction to Orion” document (which now seems to be available for “premium subscribers” only):
  

  Q: Are D-Wave processors quantum computers?
  A: Yes. We have determined that quantum effects are being harnessed to accelerate computation in our processors.

  And here’s from a comment on Dave Bacon’s blog (blog comments seem to be D-Wave’s preferred venue for announcing scientific results):

  While the jury is still not in, our studies of these systems seem to indicate that AQCs, in the presence of thermal and spin bath environments, can still provide O(sqrt(N)) scaling even though the central QC system is definitely NOT a “system that’s globally phase coherent over the entire calculation”.

• The core of Geordie’s response is the following paragraph:
  

  This is worth emphasizing, because I thought it was obvious, but it turns out alot of people don’t get this. Most of the poorly thought out comments related to what we’re trying to do have come from theoretical computer scientists, who assume that the things they hold dear are likewise treasured by everyone else. Because they worship efficiency, they have assumed that’s the objective of our projects, when I have repeatedly said it’s not.

  When I read this to Umesh Vazirani over the phone, he sardonically replied, “it will be interesting to find out what’s left of this field after you’ve removed the notion of efficiency…”

Follow

Here’s a letter that Umesh Vazirani (my adviser at Berkeley) sent to The Economist, and which he kindly permitted me to share. I’m guessing they’ll print this one instead of mine, which is fine by me.

Sir,

Your article “Orion’s belter” regarding D-Wave’s demonstration of a “practical quantum computer”, sets a new standard for sloppy science journalism. Most egregious is your assertion that quantum computers can solve NP-complete problems in “one shot” by exploring exponentially many solutions at once. This mistaken view was put to rest in the infancy of quantum computation over a decade ago when it was established that the axioms of quantum physics severely restrict the type of information accessible during a measurement. For unstructured search problems like the NP-complete problems this means that there is no exponential speed up but rather at most a quadratic speed up.

Your assertions about D-Wave are equally specious. A 16 qubit quantum computer has smaller processing power than a cell phone and hardly represents a practical breakthrough. Any claims about D-Wave’s accomplishments must therefore rest on their ability to increase the number of qubits by a couple of orders of magnitude while maintaining the fragile quantum states of the qubits. Unfortunately D-Wave, by their own admission, have not tested whether the qubits in their current implementation are in a coherent quantum state. So it is quite a stretch to assert that they have a working quantum computer let alone one that potentially scales. An even bleaker picture emerges when one more closely examines their algorithmic approach. Their claimed speedup over classical algorithms appears to be based on a misunderstanding of a paper my colleagues van Dam, Mosca and I wrote on “The power of adiabatic quantum computing”. That speed up unfortunately does not hold in the setting at hand, and therefore D-Wave’s “quantum computer” even if it turns out to be a true quantum computer, and even if it can be scaled to thousands of qubits, would likely not be more powerful than a cell phone.

Yours sincerely,
Umesh Vazirani
Roger A. Strauch Professor of Computer Science
Director, Berkeley Quantum Computing Center

Update (2/18): There’s now a Nature news article about D-Wave (hat tip to the Pontiff). Like pretty much every other article, this one makes no attempt to address the fundamental howlers about the ability of quantum computers to solve NP-complete problems — but at least it quotes me saying that “almost every popular article written on this has grotesquely over-hyped it.”

Follow

Today The Economist put out this paragon of hard-hitting D-Wave journalism. At first I merely got angry — but then I asked myself what Winston Churchill, Carl Sagan, or Chip ‘n Dale’s Rescue Rangers would do. So let’s see if The Economist prints the following.

SIR —

In a remarkably uncritical article about D-Wave’s announcement of the “world’s first practical quantum computer” (Feb. 15), you gush that “[i]n principle, by putting a set of entangled qubits into a suitably tuned magnetic field, the optimal solution to a given NP-complete problem can be found in one shot.” This is simply incorrect. Today it is accepted that quantum computers could not solve NP-complete problems in a reasonable amount of time. Indeed, the view of quantum computers as able to “try all possible solutions in parallel,” and then instantly choose the correct one, is fundamentally mistaken. Since measurement outcomes in quantum mechanics are random, one can only achieve a computational speedup by carefully exploiting the phenomenon known as quantum interference. And while it is known how to use interference to achieve dramatic speedups for a few problems — such as factorising large integers, and thereby breaking certain cryptographic codes — those problems are much more specialised than the NP-complete problems.

Over the past few days, many news outlets have shown a depressing willingness to reprint D-Wave’s marketing hype, without even attempting to learn why most quantum computing researchers are sceptical. I expected better from The Economist.

Scott Aaronson
Institute for Quantum Computing
University of Waterloo

I thought ‘factorising,’ ‘specialised,’ and ‘sceptical’ were a nice touch.

A Final Thought (2/16): As depressing as it is to see a lazy magazine writer, with a single harebrained sentence, cancel out your entire life’s work twenty times over, some good may yet come from this travesty. Where before I was reticent in the war against ignorant misunderstandings of quantum computing, now I have been radicalized — much as 9/11 radicalized Richard Dawkins in his war against religion. We, the quantum complexity theorists, are far from helpless in this fight. We, too, can launch a public relations campaign. We can speak truth to parallelism. So doofuses of the world: next time you excrete the words “NP-complete,” “solve,” and “instantaneous” anywhere near one another, brace yourselves for a Bennett-Bernstein-Brassard-Blitzirani the likes of which the multiverse has never seen.

Update (2/16): If you read the comments, Geordie Rose responds to me, and I respond to his response. Also see the comments on my earlier D-Wave post for more entertaining and ongoing debate.

Follow

Some of you might have read about how flight attendants at AirTran kicked a 3-year-old screaming brat and her parents off a plane, after the brat had already delayed takeoff for 15 minutes by refusing to get in her seat, and the parents had demonstrated their total unwillingness to control her. The parents went to the media expecting sympathy; instead, AirTran was immediately deluged with messages of support and people vowing to fly them from then on. Unfortunately, the airline then squandered a PR bonanza by apologizing profusely to the parents and refunding their tickets. In my opinion, there was no need to kick anyone off the plane: the child and parents should’ve been promptly moved to the luggage compartment, then whipped and beaten upon arrival.

Follow