Scott Aaronson's Blog, page 56

NSA: Possibly breaking US laws, but still bound by laws of computational complexity

Last week, I got an email from a journalist with the following inquiry.  The recent Snowden revelations, which made public for the first time the US government’s “black budget,” contained the following enigmatic line from the Director of National Intelligence: “We are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.”  So, the journalist wanted to know, what could these “groundbreaking” capabilities be?  And in particular, was it possible that the NSA was buying quantum computers from D-Wave, and using them to run Shor’s algorithm to break the RSA cryptosystem?

I replied that, yes, that’s “possible,” but only in the same sense that it’s “possible” that the NSA is using the Easter Bunny for the same purpose.  (For one thing, D-Wave themselves have said repeatedly that they have no interest in Shor’s algorithm or factoring.  Admittedly, I guess that’s what D-Wave would say, were they making deals with NSA on the sly!  But it’s also what the Easter Bunny would say.)  More generally, I said that if the open scientific world’s understanding is anywhere close to correct, then quantum computing might someday become a practical threat to cryptographic security, but it isn’t one yet.

That, of course, raised the extremely interesting question of what “groundbreaking capabilities” the Director of National Intelligence was referring to.  I said my personal guess was that, with ~99% probability, he meant various implementation vulnerabilities and side-channel attacks—the sort of thing that we know has compromised deployed cryptosystems many times in the past, but where it’s very easy to believe that the NSA is ahead of the open world.  With ~1% probability, I guessed, the NSA made some sort of big improvement in classical algorithms for factoring, discrete log, or other number-theoretic problems.  (I would’ve guessed even less than 1% probability for the latter, before the recent breakthrough by Joux solving discrete log in fields of small characteristic in quasipolynomial time.)

Then, on Thursday, a big New York Times article appeared, based on 50,000 or so documents that Snowden leaked to the Guardian and that still aren’t public.  (See also an important Guardian piece by security expert Bruce Schneier, and accompanying Q&A.)  While a lot remains vague, there might be more public information right now about current NSA cryptanalytic capabilities than there’s ever been.

So, how did my uninformed, armchair guesses fare?  It’s only halfway into the NYT article that we start getting some hints:

The files show that the agency is still stymied by some encryption, as Mr. Snowden suggested in a question-and-answer session on The Guardian’s Web site in June.

“Properly implemented strong crypto systems are one of the few things that you can rely on,” he said, though cautioning that the N.S.A. often bypasses the encryption altogether by targeting the computers at one end or the other and grabbing text before it is encrypted or after it is decrypted…

Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency’s success depends on working with Internet companies — by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware…

Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members.

Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

So, in pointing to implementation vulnerabilities as the most likely possibility for an NSA “breakthrough,” I might have actually erred a bit too far on the side of technological interestingness.  It seems that a large part of what the NSA has been doing has simply been strong-arming Internet companies and standards bodies into giving it backdoors.  To put it bluntly: sure, if it wants to, the NSA can probably read your email.  But that isn’t mathematical cryptography’s fault—any more than it would be mathematical crypto’s fault if goons broke into your house and carted away your laptop.  On the contrary, properly-implemented, backdoor-less strong crypto is something that apparently scares the NSA enough that they go to some lengths to keep it from being widely used.

I should add that, regardless of how NSA collects all the private information it does—by “beating crypto in a fair fight” (!) or, more likely, by exploiting backdoors that it itself installed—the mere fact that it collects so much is of course unsettling enough from a civil-liberties perspective.  So I’m glad that the Snowden revelations have sparked a public debate in the US about how much surveillance we as a society want (i.e., “the balance between preventing 9/11 and preventing Orwell”), what safeguards are in place to prevent abuses, and whether those safeguards actually work.  Such a public debate is essential if we’re serious about calling ourselves a democracy.

At the same time, to me, perhaps the most shocking feature of the Snowden revelations is just how unshocking they’ve been.  So far, I haven’t seen anything that shows the extent of NSA’s surveillance to be greater than what I would’ve considered plausible a priori.  Indeed, the following could serve as a one-sentence summary of what we’ve learned from Snowden:

Yes, the NSA is, in fact, doing the questionable things that anyone not living in a cave had long assumed they were doing—that assumption being so ingrained in nerd culture that countless jokes are based around it.

(Come to think of it, people living in caves might have been even more certain that the NSA was doing those things.  Maybe that’s why they moved to caves.)

So, rather than dwelling on civil liberties, national security, yadda yadda yadda, let me move on to discuss the implications of the Snowden revelations for something that really matters: a 6-year-old storm in theoretical computer science’s academic teacup.  As many readers of this blog might know, Neal Koblitz—a respected mathematician and pioneer of elliptic curve cryptography, who has some ties to the NSA—published a series of scathing articles, in the Notices of the American Mathematical Society and elsewhere, attacking the theoretical computer science approach to cryptography.  Koblitz’s criticisms were varied and entertainingly-expressed: the computer scientists are too sloppy, deadline-driven, self-promoting, and corporate-influenced; overly trusting of so-called “security proofs” (a term they shouldn’t even use, given how many errors and exaggerated claims they make); absurdly overreliant on asymptotic analysis; “bodacious” in introducing dubious new hardness assumptions that they then declare to be “standard”; and woefully out of touch with cryptographic realities.  Koblitz seemed to suggest that, rather than demanding the security reductions so beloved by theoretical computer scientists, people would do better to rest the security of their cryptosystems on two alternative pillars: first, standards set by organizations like the NSA with actual real-world experience; and second, the judgments of mathematicians with … taste and experience, who can just see what’s likely to be vulnerable and what isn’t.

Back in 2007, my mathematician friend Greg Kuperberg pointed out the irony to me: here we had a mathematician, lambasting computer scientists for trying to do for cryptography what mathematics itself has sought to do for everything since Euclid!  That is, when you see an unruly mess of insights, related to each other in some tangled way, systematize and organize it.  Turn the tangle into a hierarchical tree (or dag).  Isolate the minimal assumptions (one-way functions?  decisional Diffie-Hellman?) on which each conclusion can be based, and spell out all the logical steps needed to get from here to there—even if the steps seem obvious or boring.  Any time anyone has tried to do that, it’s been easy for the natives of the unruly wilderness to laugh at the systematizing newcomers: the latter often know the terrain less well, and take ten times as long to reach conclusions that are ten times less interesting.  And yet, in case after case, the clarity and rigor of the systematizing approach has eventually won out.  So it seems weird for a mathematician, of all people, to bet against the systematizing approach when applied to cryptography.

The reason I’m dredging up this old dispute now, is that I think the recent NSA revelations might put it in a slightly new light.  In his article—whose main purpose is to offer practical advice on how to safeguard one’s communications against eavesdropping by NSA or others—Bruce Schneier offers the following tip:

Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can.

Here Schneier is pointing out a specific issue with ECC, which would be solved if we could “merely” ensure that NSA or other interested parties weren’t providing input into which elliptic curves to use.  But I think there’s also a broader issue: that, in cryptography, it’s unwise to trust any standard because of the prestige, real-world experience, mathematical good taste, or whatever else of the people or organizations proposing it.  What was long a plausible conjecture—that the NSA covertly influences cryptographic standards to give itself backdoors, and that otherwise-inexplicable vulnerabilities in deployed cryptosystems are sometimes there because the NSA wanted them there—now looks close to an established fact.  In cryptography, then, it’s not just for idle academic reasons that you’d like a publicly-available trail of research papers and source code, open to criticism and improvement by anyone, that takes you all the way from the presumed hardness of an underlying mathematical problem to the security of your system under whichever class of attacks is relevant to you.

Schneier’s final piece of advice is this: “Trust the math.  Encryption is your friend.”

“Trust the math.”  On that note, here’s a slightly-embarrassing confession.  When I’m watching a suspense movie (or a TV show like Homeland), and I reach one of those nail-biting scenes where the protagonist discovers that everything she ever believed is a lie, I sometimes mentally recite the proof of the Karp-Lipton Theorem.  It always calms me down.  Even if the entire universe turned out to be a cruel illusion, it would still be the case that NP ⊂ P/poly would collapse the polynomial hierarchy, and I can tell you exactly why.  It would likewise be the case that you couldn’t break the GGM pseudorandom function without also breaking the underlying pseudorandom generator on which it’s based.  Math could be defined as that which can still be trusted, even when you can’t trust anything else.

Firewalls

So, last week I was at the Fuzzorfire workshop at the Kavli Institute for Theoretical Physics in Santa Barbara, devoted to the black hole firewall paradox.  (The workshop is still going on this week, but I needed to get back early.)  For some background:

The original paper by Almheiri et al. (from July 2012, so now “ancient history”)
New York Times article by Dennis Overbye
Scientific American article by Jennifer Ouellette
Blog post by John Preskill

I had fantasies of writing a long, witty blog post that would set out my thoughts about firewalls, full of detailed responses to everything I’d heard at the conference, as well as ruminations about Harlow and Hayden’s striking argument that computational complexity might provide a key to resolving the paradox.  But the truth is, I’m recovering from a nasty stomach virus, am feeling “firewalled out,” and wish to use my few remaining non-childcare hours before the semester starts to finish writing papers.  So I decided that better than nothing would be a hastily-assembled pastiche of links.

First and most important, you can watch all the talks online.  In no particular order:

My talk (about the computational complexity underpinnings of the Harlow-Hayden argument)
Stephen Hawking’s 10-minute talk by videoconference, denying that firewalls form, and basically repeating his position from his black hole bet concession speech of 2004 (I confess that I don’t really understand his arguments)
Lenny Susskind’s ER=EPR talk
Bill Unruh’s entertaining talk denouncing the other participants’ obsession with unitarity, and defending what he sees as the simplest solution to all the black hole information problems: information dropped into a black hole is simply gone forever, “buh-bye!”
All the other talks

Here’s my own attempt to summarize what’s at stake, adapted from a comment on Peter Woit’s blog (see also a rapid response by Lubos):

As I understand it, the issue is actually pretty simple. Do you agree that

(1) the Hawking evaporation process should be unitary, and

(2) the laws of physics should describe the experiences of an infalling observer, not just those of an observer who stays outside the horizon?

If so, then you seem forced to accept

(3) the interior degrees of freedom should just be some sort of scrambled re-encoding of the exterior degrees, rather than living in a separate subfactor of Hilbert space (since otherwise we’d violate unitarity).

But then we get

(4) by applying a suitable unitary transformation to the Hawking radiation of an old enough black hole before you jump into it, someone ought to be able, in principle, to completely modify what you experience when you do jump in.  Moreover, that person could be far away from you—an apparent gross violation of locality.

So, there are a few options: you could reject either (1) or (2). You could bite the bullet and accept (4). You could say that the “experience of an infalling observer” should just be to die immediately at the horizon (firewalls). You could argue that for some reason (e.g., gravitational backreaction, or computational complexity), the unitary transformations required in (4) are impossible to implement even in principle. Or you could go the “Lubosian route,” and simply assert that the lack of any real difficulty is so obvious that, if you admit to being confused, then that just proves you’re an idiot.  AdS/CFT is clearly relevant, but as Polchinski pointed out, it does surprisingly little to solve the problem.

Now, what Almheiri et al. (AMPS) added to the simple logical argument above was really to make the consequence (4) more “concrete” and “vivid”—by describing something that, in principle, someone could actually do to the Hawking radiation before jumping in, such that after you jumped in, if there wasn’t anything dramatic that happened—something violating local QFT and the equivalence principle—then you’d apparently observe a violation of the monogamy of entanglement, a basic principle of quantum mechanics.  I’m sure the bare logic (1)-(4) was known to many people before AMPS: I certainly knew it, but I didn’t call it a “paradox,” I just called it “I don’t understand black hole complementarity”!

At any rate, thinking about the “Hawking radiation decoding problem” already led me to some very nice questions in quantum computing theory, which remain interesting even if you remove the black hole motivation entirely. And that helped convince me that something new and worthwhile might indeed come out of this business, despite how much fun it is. (Hopefully whatever does come out won’t be as garbled as Hawking radiation.)

For continuing live updates from the workshop, check out John Preskill’s Twitter feed.

Or you can ask me to expand on various things in the comments, and I’ll do my best.  (As I said in my talk, while I’m not sure that the correct quantum description of the black hole interior is within anyone‘s professional expertise, it’s certainly outside of mine!  But I do find this sort of thing fun to think about—how could I not?)

Unrelated, but also of interest: check out an excellent article in Simons Science News by Erica Klarreich, about the recent breakthroughs by Reichardt-Unger-Vazirani, Vazirani-Vidick, and others on classical command of quantum systems.

Twitl-Optimized

Today I experiment with “tweeting”: writing

Last week at QCrypt in Waterloo: http://2013.qcrypt.net This week at CQIQC in Toronto: http://tinyurl.com/kfexzv6 Back with Lily in between

While we debate D-Wave, ID Quantique et al. quietly sold ~100 quantum crypto devices. Alas, market will remain small unless RSA compromised

One speaker explained how a photon detector works by showing this YouTube video: http://tinyurl.com/k8x4btx Couldn’t have done better

Luca Trevisan asks me to spread the word about a conference for LGBTs in technology: www.outforundergrad.org/technology

Steven Pinker stands up for the Enlightenment in The New Republic: “Science Is Not Your Enemy” http://tinyurl.com/l26ppaf

Think Pinker was exaggerating?  Read Leon Wieseltier’s defiantly doofusy Brandeis commencement speech: http://tinyurl.com/jwhj8ub

Black-hole firewalls make the New York Times, a week before the firewall workshop at KITP (I’ll be there): http://tinyurl.com/kju9crj

You probably already saw the Schrodinger cat Google doodle: http://tinyurl.com/k8et44p For me, the ket was much cooler than the cat

While working on BosonSampling yesterday, (1/6)pi^2 and Euler-Mascheroni constant made unexpected unappearances.  What I live for

The SuperScott and Morgan Freeman FAQ

Last week I appeared on an episode of Through the Wormhole with Morgan Freeman, a show on the Science Channel.  (See also here for a post on Morgan Freeman’s Facebook page.)  The episode is called “Did God Create Evolution?”  The first person interviewed is the Intelligent Design advocate Michael Behe.  But not to worry!  After him, they have a parade of scientists who not only agree that Chuck Darwin basically had it right in 1859, but want to argue for that conclusion using ROBOTS!  and MATH!

So, uh, that’s where I come in.  My segment features me (or rather my animated doppelgänger, “SuperScott”) trying to color a chessboard two colors, so that no two neighboring squares are colored the same, using three different approaches: (1) an “intelligent design” approach (which computer scientists would call nondeterminism), (2) a brute-force, exhaustive enumeration approach, and (3) an “evolutionary local search” approach.

[Spoiler alert: SuperScott discovers that the local search approach, while not as efficient as intelligent design, is nevertheless much more efficient than brute-force search.  And thus, he concludes, the arguments of the ID folks to the effect of "I can't see a cleverer way to do it, therefore it must be either brute-force search or else miraculous nondeterminism" are invalid.]

Since my appearance together with Morgan Freeman on cable TV raises a large number of questions, I’ve decided to field a few of them in the following FAQ.

Q: How can I watch?

Amazon Instant Video has the episode here for $1.99.  (No doubt you can also find it on various filesharing sites, but let it be known that I’d never condone such nefarious activity.)  My segment is roughly from 10:30 until 17:40.

Q: Given that you’re not a biologist, and that your research has basically nothing to do with evolution, why did they ask to interview you?

Apparently they wanted a mathematician or computer scientist who also had some experience spouting about Big Ideas.  So they first asked Greg Chaitin, but Chaitin couldn’t do it and suggested me instead.

Q: Given how little relevant expertise you have, why did you agree to be interviewed?

To be honest, I was extremely conflicted.  I kept saying, “Why don’t you interview a biologist?  Or at least a computational biologist, or someone who studies genetic algorithms?”  They replied that they did have more bio-oriented people on the show, but they also wanted me to provide a “mathematical” perspective.  So, I consulted with friends like Sean Carroll, who’s appeared on Through the Wormhole numerous times.  And after reflection, I decided that I do have a way to explain a central conceptual point about algorithms, complexity, and the amount of time needed for natural selection—a point that, while hardly “novel,” is something that many laypeople might not have seen before and that might interest them.  Also, as an additional argument in favor of appearing, MORGAN FREEMAN!

So I agreed to do it, but only under two conditions:

(1) At least one person with a biology background would also appear on the show, to refute the arguments of intelligent design.

(2) I would talk only about stuff that I actually understood, like the ability of local search algorithms to avoid the need for brute-force search.

I’ll let you judge for yourself to what extent these conditions were fulfilled.

Q: Did you get to meet Morgan Freeman?

Alas, no.  But at least I got to hear him refer repeatedly to “SuperScott” on TV.

Q: What was the shooting like?

Extremely interesting.  I know more now about TV production than I did before!

It was a continuing negotiation: they kept wanting to say that I was “on a quest to mathematically prove evolution” (or something like that), and I kept telling them they weren’t allowed to say that, or anything else that would give the misleading impression that what I was saying was either original or directly related to my research.  I also had a long discussion about the P vs. NP problem, which got cut for lack of time (now P and NP are only shown on the whiteboard).  On the other hand, the crew was extremely accommodating: they really wanted to do a good job and to get things right.

The most amusing tidbit: I knew that local search would take O(n4) time to 2-color an nxn chessboard (2-coloring being a special case of 2SAT, to which Schöning’s algorithm applies), but I didn’t know the constant.  So I wrote a program to get the specific number of steps when n=8 (it’s about 5000).  I then repeatedly modified and reran the program during the taping, as we slightly changed what we were talking about.  It was the first coding I’d done in a while.

Q: How much of the segment was your idea, and how much was theirs?

The chessboard was my idea, but the “SuperScott” bit was theirs.  Luddite that I am, I was just going to get down on hands and knees and move apples and oranges around on the chessboard myself.

Also, they wanted me to speak in front of a church in Boston, to make a point about how many people believe that God created the universe.  I nixed that idea and said, why not just do the whole shoot in the Stata Center?  I mean, MIT spent $300 million just to make the building where I work as “visually arresting” as possible—at the expense of navigability, leakage-resilience, and all sorts of other criteria—so why not take advantage of it?  Plus, that way I’ll be able to crack a joke about how Stata actually looks like it was created by that favorite creationist strawman, a tornado passing through a junkyard.

Needless to say, all the stuff with me drawing complexity class inclusion diagrams on the whiteboard, reading my and Alex Arkhipov’s linear-optics paper, walking around outside with an umbrella, lifting the umbrella to face the camera dramatically—that was all just the crew telling me what to do.  (Well, OK, they didn’t tell me what to write on the whiteboard or view on my computer, just that it should be something sciencey.  And the umbrella thing wasn’t planned: it really just happened to be raining that day.)

Q: Don’t you realize that not a word of what you said was new—indeed, that all you did was to translate the logic of natural selection, which Darwin understood in 1859, into algorithms and complexity language?

Yes, of course, and I’m sorry if the show gave anyone the impression otherwise.  I repeatedly begged them not to claim newness or originality for anything I was saying.  On the other hand, one shouldn’t make the mistake of assuming that what’s obvious to nerds who read science blogs is obvious to everyone else: I know for a fact that it isn’t.

Q: Don’t you understand that you can’t “prove” mathematically that evolution by natural selection is really what happened in Nature?

Of course!  You can’t even prove mathematically that bears crap in the woods (unless crapping in the woods were taken as part of the definition of bears).  To the writers’ credit, they did have Morgan Freeman explain that I wasn’t claiming to have “proved” evolution.  Personally, I wish Freeman had gone even further—to say that, at present, we don’t even have mathematical theories that would explain from first principles why 4 billion years is a “reasonable” amount of time for natural selection to have gotten from the primordial soup to humans and other complex life, whereas (say) 40 million years is not a reasonable amount.  One could imagine such theories, but we don’t really have any.  What we do have is (a) the observed fact that evolution did happen in 4 billion years, and (b) the theory of natural selection, which explains in great detail why one’s initial intuition—that such evolution can’t possibly have happened by “blind, chance natural processes” alone—is devoid of force.

Q: Watching yourself presented in such a goony way—scribbling Complicated Math Stuff on a whiteboard, turning dramatically toward the camera, etc. etc.—didn’t you feel silly?

Some of it is silly, no two ways about it!  On the other hand, I feel satisfied that I got across at least one correct and important scientific point to hundreds of thousands of people.  And that, one might argue, is sufficiently worthwhile that it should outweigh any embarrassment about how goofy I look.

Three announcements

1. As many of you probably know, this week my EECS colleague Hal Abelson released his 180-page report on MIT’s involvement in the Aaron Swartz case.  I read the whole thing, and I recommend it if you have any interest in this case.  My take is that, far from being the “whitewash” that some people described it as, the report (if you actually delve into it) clearly and eloquently explains how MIT failed to live up to its own standards, even as it formally followed the rules.  The central insight here is that the world expects MIT to behave, not like some other organization would behave if someone hid a laptop in its supply closet to download the whole JSTOR database, insulted and then tried to flee from its security officers when questioned, etc. etc., but rather with perspective and imagination—worrying less about the security of its facilities than about the future of the world.  People expect MIT, of all places, to realize that the people who pull these sorts of shenanigans in their twenties sometimes become Steve Jobs or Richard Feynman (or for that matter, MIT professor Robert Morris) later in their lives, and therefore to speak up in their defense.  In retrospect, I wish Swartz’s arrest had sparked a debate about the wider issues among MIT’s students, faculty, and staff.  I think it’s likely that such a debate would have led to pressure on the administration to issue a statement in Swartz’s support.  As it was (and as I pointed out in this interview), most people at MIT, even if they’d read about the arrest, weren’t even aware of the issue’s continued existence, let alone of MIT’s continued role in it, until after Swartz had already committed suicide.  For the MIT community—which includes some prominent supporters of open access—to have played such a passive role is one of the many tragedies that’s obvious with hindsight.

2. Shafi Goldwasser has asked me to announce that the fifth Innovations in Theoretical Computer Science (ITCS) conference will be held in Princeton, a town technically in New Jersey, on January 12-14, 2014.  Here’s the conference website; if you want to submit a paper, the deadline is coming up soon, on Thursday, August 22.

3. As the summer winds to a close, I’m proud to announce my main goals for the upcoming academic year.  Those goals are the following:

(a) Take care of Lily.

(b) Finish writing up old papers.

It feels liberating to have no higher aspirations for an entire year—and for the aspirations I have to seem so modest and so achievable.  On the other hand, it will be all the more embarrassing if I fail to achieve even these goals.

Microsoft: From QDOS to QMA in less than 35 years

This past week I was in Redmond for the Microsoft Faculty Summit, which this year included a special session on quantum computing.  (Bill Gates was also there, I assume as our warmup act.)  I should explain that Microsoft Research now has not one but two quantum computing research groups: there’s Station Q in Santa Barbara, directed by Michael Freedman, which pursues topological quantum computing, but there’s also QuArC in Redmond, directed by Krysta Svore, which studies things like quantum circuit synthesis.

Anyway, I’ve got two videos for your viewing pleasure:

An interview about quantum computing with me, Krysta Svore, and Matthias Troyer, moderated by Chris Cashman, and filmed in a studio where they put makeup on your face.  Just covers the basics.
A session about quantum computing, with three speakers: me about “what quantum mechanics is good for” (quantum algorithms, money, crypto, and certified random numbers), then Charlie Marcus about physical implementations of quantum computing, and finally Matthias Troyer about his group’s experiments on the D-Wave machines.  (You can also download my slides here.)

This visit really drove home for me that MSR is the closest thing that exists today to the old Bell Labs: a corporate lab that does a huge amount of openly-published, high-quality fundamental research in math and CS, possibly more than all the big Silicon-Valley-based companies combined.  This research might or might not be good for Microsoft’s bottom line (Microsoft, of course, says that it is, and I’d like to believe them), but it’s definitely good for the world.  With the news of Microsoft’s reorganization in the background, I found myself hoping that MS will remain viable for a long time to come, if only because its decline would leave a pretty gaping hole in computer science research.

Unfortunately, last week I also bought a new laptop, and had the experience of PowerPoint 2013 first refusing to install (it mistakenly thought it was already installed), then crashing twice and losing my data, and just generally making everything (even saving a file) harder than it used to be for no apparent reason.  Yes, that’s correct: the preparations for my talk at the Microsoft Faculty Summit were repeatedly placed in jeopardy by the “new and improved” Microsoft Office.  So not just for its own sake, but for the sake of computer science as a whole, I implore Microsoft to build a better Office.  It shouldn’t be hard: it would suffice to re-release the 2003 or 2007 versions as “Office 2014″!  If Mr. Gates took a 2-minute break from curing malaria to call his former subordinates and tell them to do that, I’d really consider him a great humanitarian.

The Collision Lower Bound After 12 Years

Streaming video is now available for the talks at the QStart conference, a couple weeks ago at Hebrew University in Jerusalem.  If you’re the sort of person who likes watching quantum information talks, then check out the excellent ones by Ray Laflamme, John Martinis, Umesh Vazirani, Thomas Vidick, Jacob Bekenstein, and many others.

My own contribution—the first “backwards-facing, crusty, retrospective” talk I’ve ever given—was called The Collision Lower Bound After 12 Years (click here for the slides—and to answer the inevitable question, no, I have no idea how to open PowerPoint files in your favorite free-range, organic computing platform).  Briefly, the collision lower bound is the theorem that even a quantum computer needs at least ~n1/3 steps to find a duplicate in a long list of random numbers between 1 and n, even assuming the list is long enough that there are many, many duplicates to be found.  (Moreover, ~n1/3 steps are known to suffice, by the BHT algorithm, a clever adaptation of Grover’s search algorithm.  Also, for simplicity a “step” means a single access to the list, though of course a quantum algorithm can access multiple list elements in superposition and it still counts as one step.)

By comparison, for classical algorithms, ~√n steps are necessary and sufficient to find a collision, by the famous Birthday Paradox.  So, just like for Grover’s search problem, a quantum computer could give you a modest speedup over classical for the collision problem, but only a modest one.  The reason this is interesting is that, because of the abundance of collisions to be found, the collision problem has a great deal more structure than Grover’s search problem (though it has less structure than Shor’s period-finding problem, where there famously is an exponential quantum speedup).

One “obvious” motivation for the collision problem is that it models the problem of breaking collision-resistant hash functions (like SHA-256) in cryptography.  In particular, if there were a superfast (e.g., log(n)-time) quantum algorithm for the collision problem, then there could be no CRHFs secure against quantum attack.  So the fact that there’s no such algorithm at least opens up the possibility of quantum-secure CRHFs.  However, there are many other motivations.  For example, the collision lower bound rules out the most “simpleminded” approach to a polynomial-time quantum algorithm for the Graph Isomorphism problem (though, I hasten to add, it says nothing about more sophisticated approaches).  The collision problem is also closely related to Statistical Zero Knowledge (SZK) proof protocols, so that the collision lower bound leads to an oracle relative to which SZK is not in BQP.

Probably the most bizarre motivation to other people, but for some reason the most important one to me back in 2001, is that the collision problem is closely related to the problem of sampling the entire trajectories of hidden variables, in hidden-variable theories such as Bohmian mechanics.  The collision lower bound provides strong evidence that this trajectory-sampling problem is hard even for a quantum computer—intuitively because a QC can’t keep track of the correlations between the hidden-variable positions at different times.  The way I like to put it is that if, at the moment of your death, your entire life history flashed before you in an instant (and if a suitable hidden-variable theory were true, and if you’d performed an appropriate quantum interference experiment on your own brain during your life), then you really could solve the collision problem in only O(1) steps.  Interestingly, you still might not be able to solve NP-complete problems—I don’t know!  But you could at least do something that we think is hard for a quantum computer.

I proved the first collision lower bound in 2001 (actually, a week or so after the 9/11 attacks), after four months of sleepless nights and failed attempts.  (Well actually, I only got the weaker lower bound of ~n1/5; the ~n1/3 was a subsequent improvement due to Yaoyun Shi.  Before ~n1/5, no one could even rule out that a quantum computer could solve the collision problem with a constant number of steps (!!), independent of n—say, 4 steps.)  It was the first thing I’d proved of any significance, and probably the most important thing I did while in grad school.  I knew it was one of the favorite problems of my adviser, Umesh Vazirani, so I didn’t even tell Umesh I was working on it until I’d already spent the whole summer on it.  I figured he’d think I was nuts.

Bonus Proof Explanation!

The technique that ultimately worked was the polynomial method, which was introduced to quantum computing four years prior in a seminal paper of Beals et al.  In this technique, you first suppose by contradiction that a quantum algorithm exists to solve your problem that makes very few accesses to the input bits—say, T.  Then you write out the quantum algorithm’s acceptance probability (e.g., the probability that the algorithm outputs “yes, I found what I was looking for”) as a multivariate polynomial p in the input bits.  It’s not hard to prove that p has degree at most 2T, since the amplitudes in the quantum algorithm can be written as degree-T polynomials (each input access increases the degree by at most 1, and unitary transformations in between input accesses don’t increase the degree at all); then squaring the amplitudes to get probabilities doubles the degree.  (This is the only part of the method that uses anything specific to quantum mechanics!)

Next, you choose some parameter k related to the problem of interest, and you let q(k) be the expectation of p(X) over all inputs X with the parameter equal to k.  For example, with the collision problem, it turns out that the “right” choice to make is to set k=1 if each number appears exactly once in your input list, k=2 if each number appears exactly twice, k=3 if each number appears exactly three times, and so on.  Then—here comes the “magic” part—you show that q(k) itself is a univariate polynomial in k, again of degree at most 2T.  This magical step is called “symmetrization”; it can be traced at least as far back as the famous 1969 book Perceptrons by Marvin Minsky and Seymour Papert.  In the case of the collision problem, I still have no explanation, 12 years later, for why symmetrization works: all I can say is that you do the calculation, and you cancel lots of things from both the numerator and the denominator, and what comes out at the end is a low-degree polynomial in k.  (It’s precisely because I would never have predicted such a “zany coincidence,” that I had to stumble around in the dark for 4 months before I finally discovered by chance that the polynomial method worked.)

Anyway, after applying symmetrization, you’re left with a low-degree univariate polynomial q with some very interesting properties: for example, you need 0≤q(k)≤1 for positive integers k, since then q(k) represents an averaged probability that your quantum algorithm does something.  You also need q(1) to be close to 0, since if k=1 then there no collisions to be found, and you need q(2) to be close to 1, since if k=2 then there are lots of collisions and you’d like your algorithm to find one.  But now, you can appeal to a theorem of A. A. Markov from the 1890s, which implies that no low-degree polynomial exists with those properties!  Hence your original efficient quantum algorithm can’t have existed either: indeed, you get a quantitative lower bound (a tight one, if you’re careful) on the number of input accesses your algorithm must have made.  And that, modulo some nasty technicalities (e.g., what if k doesn’t evenly divide the size of your list?), is how the collision lower bound works.

So, in the first half of my QStart talk, I explain the collision lower bound and its original motivations (and a little about the proof, but no more than what I said above).  Then in the second half, I survey lots of extensions and applications between 2002 and the present, as well as the many remaining open problems.  For example, I discuss the tight lower bound of Ambainis et al. for the “index erasure” problem, Belovs’s proof of the element distinctness lower bound using the adversary method, and my and Ambainis’s generalization of the collision lower bound to arbitrary symmetric problems.  I also talk about Mark Zhandry’s recent breakthrough (sorry, am I not allowed to use that word?) showing that the GGM construction of pseudorandom functions is secure against quantum adversaries, and how Zhandry’s result can be seen—in retrospect, anyway—as yet another application of the collision lower bound.

Probably of the most general interest, I discuss how Daniel Harlow and Patrick Hayden invoked the collision lower bound in their striking recent paper on the AMPS black hole “firewall” paradox.  In particular they argued that, in order to uncover the apparent violation of local quantum field theory at the heart of the paradox, an observer falling into a black hole would problem need to solve a QSZK-complete computational problem.  And of course, the collision lower bound furnishes our main piece of evidence that QSZK-complete problems really should require exponential time even for quantum computers.  So, Harlow and Hayden argue, the black hole would already have evaporated before the observer had even made a dent in the requisite computation.

Now, the Harlow-Hayden paper, and the AMPS paradox more generally, really deserve posts of their own—just as soon as I learn enough to decide what I think about them.  For now, I’ll simply say that, regardless of how convinced you are by Harlow and Hayden’s argument (and, a bit like with my free-will essay, it’s not clear how convinced the authors themselves are!), it’s one of the most ambitious syntheses of computational complexity and physics I’ve ever seen.  You can disagree with it, but to read the paper (or watch the talk, streaming video from Strings’2013 here) is to experience the thrill of seeing black hole physics related to complexity theory by authors who really know both.

(In my own talk on the collision lower bound, the short segment about Harlow-Hayden generated more questions and discussion than the rest of the talk combined—with me being challenged to defend their argument, even with Patrick Hayden right there in the audience!  I remarked later that that portion of the talk was itself a black hole for audience interest.)

In totally unrelated news, Quantum Computing Since Democritus made Scientific American’s list of best summer books!  I can’t think of a more appropriate honor, since if there’s any phrase that captures what QCSD is all about, “sizzling summer beach read” would be it.  Apparently there will even be an online poll soon, where y’all can go and vote for QCSD as your favorite.  Vote early and often, and from multiple IP addresses!

The Ghost in the Quantum Turing Machine

I’ve been traveling this past week (in Israel and the French Riviera), heavily distracted by real life from my blogging career.  But by popular request, let me now provide a link to my very first post-tenure publication: The Ghost in the Quantum Turing Machine.

Here’s the abstract:

In honor of Alan Turing’s hundredth birthday, I unwisely set out some thoughts about one of Turing’s obsessions throughout his life, the question of physics and free will. I focus relatively narrowly on a notion that I call “Knightian freedom”: a certain kind of in-principle physical unpredictability that goes beyond probabilistic unpredictability. Other, more metaphysical aspects of free will I regard as possibly outside the scope of science. I examine a viewpoint, suggested independently by Carl Hoefer, Cristi Stoica, and even Turing himself, that tries to find scope for “freedom” in the universe’s boundary conditions rather than in the dynamical laws. Taking this viewpoint seriously leads to many interesting conceptual problems. I investigate how far one can go toward solving those problems, and along the way, encounter (among other things) the No-Cloning Theorem, the measurement problem, decoherence, chaos, the arrow of time, the holographic principle, Newcomb’s paradox, Boltzmann brains, algorithmic information theory, and the Common Prior Assumption. I also compare the viewpoint explored here to the more radical speculations of Roger Penrose. The result of all this is an unusual perspective on time, quantum mechanics, and causation, of which I myself remain skeptical, but which has several appealing features. Among other things, it suggests interesting empirical questions in neuroscience, physics, and cosmology; and takes a millennia-old philosophical debate into some underexplored territory.

See here for an interesting discussion over on Less Wrong.  I welcome further discussion in the comments section of this post, and will jump in myself after a few days to address questions.  There are three reasons for the self-imposed delay: first, general busyness.  Second, inspired by the McGeoch affair, I’m trying out a new experiment, in which I strive not to be on such an emotional hair-trigger about the comments people leave on my blog.  And third, based on past experience, I anticipate comments like the following:

“Hey Scott, didn’t have time to read this 85-page essay that you labored over for two years, struggling to make everything as clear as you could.  So, can you please just summarize your argument in the space of a blog comment?  Also, based on the other comments here, I have an objection that I’m sure never occurred to you.  Oh, wait, just now scanning the table of contents…”

So, I decided to leave some time for people to RTFM (Read The Free-Will Manuscript) before I entered the fray.

For now, just one remark: some people might wonder whether this essay marks a new “research direction” for me.  While it’s difficult to predict the future (even probabilistically ), I can say that my own motivations were exactly the opposite: I wanted to set out my thoughts about various mammoth philosophical issues once and for all, so that then I could get back to complexity, quantum computing, and just general complaining about the state of the world.

The tightrope of truth and courtesy

A reader calling him- or herself “A Merry Clown” left a comment on my previous post which was so wise, I decided it had to be promoted to a post of its own.

Scientific discourse is the art of juggling decorum, truth and humor. A high-wire feat, attempted under imposing shadows cast by giants and above the distraction of merry dancing clowns.

The “appropriate” tone for scientific discourse seems to be:

(a) Cordial. Always credit others for their hard work and good intentions (allow or at least pretend that others are basically well-intentioned, except in rare situations where there is proof of egregious misconduct).

(b) Biting, merciless and hard-nosed on the substantive issues. The truth deserves no less.

Perhaps the harsher (b) is, the gentler and more thorough (a) should be. After-all, human beings are what they are.

Certainly, provided one adequately treads through the niceties in (a), there’s no reason to worry about hurting anyone’s feelings in (b). Anyone who makes scientific claims in a professional or public arena should be prepared to put on their big boy pants or their big girl pants and have their claims face the brutal gauntlet of scientific scrutiny. All attempts should be made to avoid even the appearance that any part of (b) contains personal barbs or insults (unless these barbs happen to be to be hilarious.)

Outside of science the rule is: whoever flings the horseshit the hardest wins.

Essentially, what Shtetl-Optimized readers got to see this past week was me falling off the high wire (with tenure the safety net below? ).  I failed at a purely human level—though admittedly, while attempting a particularly difficult tightrope walk, and while heavily distracted by the taunts of both giants and clowns.  I’ve already apologized to Cathy McGeoch for insulting her, but I reiterate my apology now, and I extend the apology to any colleagues at MIT who might have been offended by anything I said.  I’ll strive, in future posts, to live up to a higher standard of cordiality, composure, and self-control.

At the scientific level—i.e., at level (b)—I stand by everything I wrote in the previous post and the comments therein.

D-Wave: Truth finally starts to emerge

Two years ago almost to the day, I announced my retirement as Chief D-Wave Skeptic.  But—as many readers predicted at the time—recent events (and the contents of my inbox!) have given me no choice except to resume my post.  In an all-too-familiar pattern, multiple rounds of D-Wave-related hype have made it all over the world before the truth has had time to put its pants on and drop its daughter off in daycare.  And the current hype is particularly a shame, because once one slices through all the layers of ugh—the rigged comparisons, the “dramatic announcements” that mean nothing, the lazy journalists cherry-picking what they want to hear and ignoring the inconvenient bits—there really has been a huge scientific advance this past month in characterizing the D-Wave devices.  I’m speaking about the experiments on the D-Wave One installed at USC, the main results of which finally appeared in April.  Two of the coauthors of this new work—Matthias Troyer and Daniel Lidar—were at MIT recently to speak about their results, Troyer last week and Lidar this Tuesday.  Intriguingly, despite being coauthors on the same paper, Troyer and Lidar have very different interpretations of what their results mean, but we’ll get to that later.  For now, let me summarize what I think their work has established.

Evidence for Quantum Annealing Behavior

For the first time, we have evidence that the D-Wave One is doing what should be described as “quantum annealing” rather than “classical annealing” on more than 100 qubits.  (Note that D-Wave itself now speaks about “quantum annealing” rather than “quantum adiabatic optimization.”  The difference between the two is that the adiabatic algorithm runs coherently, at zero temperature, while quantum annealing is a “messier” version in which the qubits are strongly coupled to their environment throughout, but still maintain some quantum coherence.)  The evidence for quantum annealing behavior is still extremely indirect, but despite my “Chief Skeptic” role, I’m ready to accept what the evidence indicates with essentially no hesitation.

So what is the evidence?  Basically, the USC group ran the D-Wave One on a large number of randomly generated instances of what I’ll call the “D-Wave problem”: namely, the problem of finding the lowest-energy configuration of an Ising spin glass, with nearest-neighbor interactions that correspond to the D-Wave chip’s particular topology.  Of course, restricting attention to this “D-Wave problem” tilts the tables heavily in D-Wave’s favor, but no matter: scientifically, it makes a lot more sense than trying to encode Sudoku puzzles or something like that.  Anyway, the group then looked at the distribution of success probabilities when each instance was repeatedly fed to the D-Wave machine.  For example, would the randomly-generated instances fall into one giant clump, with a few outlying instances that were especially easy or especially hard for the machine?  Surprisingly, they found that the answer was no: the pattern was strongly bimodal, with most instances either extremely easy or extremely hard, and few instances in between.  Next, the group fed the same instances to Quantum Monte Carlo: a standard classical algorithm that uses Wick rotation to find the ground states of “stoquastic Hamiltonians,” the particular type of quantum evolution that the D-Wave machine is claimed to implement.  When they did that, they found exactly the same bimodal pattern that they found with the D-Wave machine.  Finally they fed the instances to a classical simulated annealing program—but there they found a “unimodal” distribution, not a bimodal one.  So, their conclusion is that whatever the D-Wave machine is doing, it’s more similar to Quantum Monte Carlo than it is to classical simulated annealing.

Curiously, we don’t yet have any hint of a theoretical explanation for why Quantum Monte Carlo should give rise to a bimodal distribution, while classical simulating annealing should give rise to a unimodal one.  The USC group simply observed the pattern empirically (as far as I know, they’re the first to do so), then took advantage of it to characterize the D-Wave machine.  I regard explaining this pattern as an outstanding open problem raised by their work.

In any case, if we accept that the D-Wave One is doing “quantum annealing,” then despite the absence of a Bell-inequality violation or other direct evidence, it’s reasonably safe to infer that there should be large-scale entanglement in the device.  I.e., the true quantum state is no doubt extremely mixed, but there’s no particular reason to believe we could decompose that state into a mixture of product states.  For years, I tirelessly repeated that D-Wave hadn’t even provided evidence that its qubits were entangled—and that, while you can have entanglement with no quantum speedup, you can’t possibly have a quantum speedup without at least the capacity to generate entanglement.  Now, I’d say, D-Wave finally has cleared the evidence-for-entanglement bar—and, while they’re not the first to do so with superconducting qubits, they’re certainly the first to do so with so many superconducting qubits.  So I congratulate D-Wave on this accomplishment.  If this had been advertised from the start as a scientific research project—”of course we’re a long way from QC being practical; no one would ever claim otherwise; but as a first step, we’ve shown experimentally that we can entangle 100 superconducting qubits with controllable couplings”—my reaction would’ve been, “cool!”  (Similar to my reaction to any number of other steps toward scalable QC being reported by research groups all over the world.)

No Speedup Compared to Classical Simulated Annealing

But of course, D-Wave’s claims—and the claims being made on its behalf by the Hype-Industrial Complex—are far more aggressive than that.  And so we come to the part of this post that has not been pre-approved by the International D-Wave Hype Repeaters Association.  Namely, the same USC paper that reported the quantum annealing behavior of the D-Wave One, also showed no speed advantage whatsoever for quantum annealing over classical simulated annealing.  In more detail, Matthias Troyer’s group spent a few months carefully studying the D-Wave problem—after which, they were able to write optimized simulated annealing code that solves the D-Wave problem on a normal, off-the-shelf classical computer, about 15 times faster than the D-Wave machine itself solves the D-Wave problem!  Of course, if you wanted even more classical speedup than that, then you could simply add more processors to your classical computer, for only a tiny fraction of the ~$10 million that a D-Wave One would set you back.  Some people might claim it’s “unfair” to optimize the classical simulated annealing code to take advantage of the quirks of the D-Wave problem.  But think about it this way: D-Wave has spent ~$100 million, and hundreds of person-years, optimizing the hell out of a special-purpose annealing device, with the sole aim of solving this one problem that D-Wave itself defined.  So if we’re serious about comparing the results to a classical computer, isn’t it reasonable to have one professor and a few postdocs spend a few months optimizing the classical code as well?

As I said, besides simulated annealing, the USC group also compared the D-Wave One’s performance against a classical implementation of Quantum Monte Carlo.  And maybe not surprisingly, the D-Wave machine was faster than a “direct classical simulation of itself” (I can’t remember how many times faster, and couldn’t find that information in the paper).  But even here, there’s a delicious irony.  The only reason the USC group was able to compare the D-Wave one against QMC at all, is that QMC is efficiently implementable on a classical computer!  (Albeit probably with a large constant overhead compared to running the D-Wave annealer itself—hence the superior performance of classical simulated annealing over QMC.)  This means that, if the D-Wave machine can be understood as reaching essentially the same results as QMC (technically, “QMC with no sign problem”), then there’s no real hope for using the D-Wave machine to get an asymptotic speedup over a classical computer.  The race between the D-Wave machine and classical simulations of the machine would then necessarily be a cat-and-mouse game, a battle of constant factors with no clear asymptotic victor.  (Some people might conjecture that it will also be a “Tom & Jerry game,” the kind where the classical mouse always gets the better of the quantum cat.)

At this point, it’s important to give a hearing to three possible counterarguments to what I’ve written above.

The first counterargument is that, if you plot both the runtime of simulated annealing and the runtime of the D-Wave machine as functions of the instance size n, you find that, while simulated annealing is faster in absolute terms, it can look like the curve for the D-Wave machine is less steep.  Over on the blog “nextbigfuture”, an apparent trend of this kind has been fearlessly extrapolated to predict that with 512 qubits, the D-Wave machine will be 10 billion times faster than a classical computer.  But there’s a tiny fly in the ointment.  As Troyer carefully explained to me last week, the “slow growth rate” of the D-Wave machine’s runtime is, ironically, basically an artifact of the machine being run too slowly on small values of n.  Run the D-Wave machine as fast as it can run for small n, and the difference in the slopes disappears, with only the constant-factor advantage for simulated annealing remaining.  In short, there seems to be no evidence, at present, that the D-Wave machine is going to overtake simulated annealing for any instance size.

The second counterargument is that the correlation between the two “bimodal distributions”—that for the D-Wave machine and that for the Quantum Monte Carlo simulation—is not perfect.  In other words, there are a few instances (not many) that QMC solves faster than the D-Wave machine, and likewise a few instances that the D-Wave machine solves faster than QMC.  Not surprisingly, the latter fact has been eagerly seized on by the D-Wave boosters (“hey, sometimes the machine does better!”).  But Troyer has a simple and hilarious response to that.  Namely, he found that his group’s QMC code did a better job of correlating with the D-Wave machine, than the D-Wave machine did of correlating with itself!  In other words, calibration errors seem entirely sufficient to explain the variation in performance, with no need to posit any special class of instances (however small) on which the D-Wave machine dramatically outperforms QMC.

The third counterargument is just the banal one: the USC experiment was only one experiment with one set of instances (albeit, a set one might have thought would be heavily biased toward D-Wave).  There’s no proof that, in the future, it won’t be discovered that the D-Wave machine does something more than QMC, and that there’s some (perhaps specially-designed) set of instances on which the D-Wave machine asymptotically outperforms both QMC and Troyer’s simulated annealing code.  (Indeed, I gather that folks at D-Wave are now assiduously looking for such instances.)  Well, I concede that almost anything is possible in the future—but “these experiments, while not supporting D-Wave’s claims about the usefulness of its devices, also don’t conclusively disprove those claims” is a very different message than what’s currently making it into the press.

Comparison to CPLEX is Rigged

Unfortunately, the USC paper is not the one that’s gotten the most press attention—perhaps because half of it inconveniently told the hypesters something they didn’t want to hear (“no speedup”).  Instead, journalists have preferred a paper released this week by Catherine McGeoch and Cong Wang, which reports that the D-Wave machine outperformed the classical CPLEX optimization package by a factor of ~3600, on Ising spin problems involving 439 bits.  Wow!  That sounds awesome!  But before rushing to press, let’s pause to ask ourselves: how can we reconcile this with the USC group’s result of no speedup?

The answer turns out to be painfully simple.  CPLEX is a general-purpose, off-the-shelf exact optimization package.  Of course an exact solver can’t compete against quantum annealing—or for that matter, against classical annealing or other classical heuristics!  Noticing this problem, McGeoch and Wang do also compare the D-Wave machine against tabu search, a classical heuristic algorithm.  When they do so, they find that an advantage for the D-Wave machine persists, but it becomes much, much smaller (they didn’t report the exact time comparison).  Amusingly, they write in their “Conclusions and Future Work” section:

It would of course be interesting to see if highly tuned implementations of, say, tabu search or simulated annealing could compete with Blackbox or even QA [i.e., the D-Wave machines] on QUBO [quadratic binary optimization] problems; some preliminary work on this question is underway.

As I said above, at the time McGeoch and Wang’s paper was released to the media (though maybe not at the time it was written?), the “highly tuned implementation” of simulated annealing that they ask for had already been written and tested, and the result was that it outperformed the D-Wave machine on all instance sizes tested.  In other words, their comparison to CPLEX had already been superseded by a much more informative comparison—one that gave the “opposite” result—before it ever became public.  For obvious reasons, most press reports have simply ignored this fact.

Troyer, Lidar, and Stone Soup

Much of what I’ve written in this post, I learned by talking to Matthias Troyer—the man who carefully experimented with the D-Wave machine and figured out how to beat it using simulated annealing, and who I regard as probably the world’s #1 expert right now on what exactly the machine does.  Troyer wasn’t shy about sharing his opinions, and while couched with qualifications, they tended toward extremely skeptical.  For example, Troyer conjectured that, if D-Wave ultimately succeeds in getting a speedup over classical computers in a fair comparison, then it will probably be by improving coherence and calibration, incorporating error-correction, and doing other things that “traditional,” “academic” quantum computing researchers had said all along would need to be done.

As I said, Danny Lidar is another coauthor on the USC paper, and also recently visited MIT to speak.  Lidar and Troyer seem to agree on the basic facts—yet Lidar noticeably differed from Troyer, in trying to give each fact the most “pro-D-Wave spin” it could possibly support.  Lidar chose to speak at our quantum group meeting, not about the D-Wave vs. simulated annealing performance comparison (which he doesn’t dispute), but about a proposal of his for incorporating quantum error-correction into the D-Wave device.  He presented this proposal, not as a reductio ad absurdum of D-Wave’s entire philosophy, but rather as a wonderful, positive opportunity to get a quantum speedup using D-Wave’s approach.

So, to summarize my current assessment of the situation: yes, absolutely, D-Wave might someday succeed—ironically, by adapting the very ideas from “the gate model” that its entire business plan has been based on avoiding, and that D-Wave founder Geordie Rose has loudly denigrated for D-Wave’s entire history!  If that’s what happens, then I predict that science writers, and blogs like “nextbigfuture,” will announce from megaphones that D-Wave has been vindicated at last, while its narrow-minded, theorem-obsessed, ivory-tower academic naysayers now have egg all over their faces.  No one will care that the path to success—through quantum error-correction and so on—actually proved the academic critics right, and that D-Wave’s “vindication” was precisely like that of the deliciousness of stone soup in the old folktale.  As for myself, I’ll probably bang my head on my desk until I sustain so much brain damage that I no longer care either.  But at least I’ll still have tenure, and the world will have quantum computers.

The Messiah’s Quantum Annealer

Over the past few days, I’ve explained the above to at least six different journalists who asked.  And I’ve repeatedly gotten a striking response: “What you say makes sense—but then why are all these prestigious people and companies investing in D-Wave?  Why did Bo Ewald, a prominent Silicon Valley insider, recently join D-Wave as president of its US operations?  Why the deal with Lockheed Martin?  Why the huge deal with NASA and Google, just announced today?  What’s your reaction to all this news?”

My reaction, I confess, is simple.  I don’t care—I actually told them this—if the former Pope Benedict has ended his retirement to become D-Wave’s new marketing director.  I don’t care if the Messiah has come to Earth on a flaming chariot, not to usher in age of peace but simply to spend $10 million on D-Wave’s new Vesuvius chip.  And if you imagine that I’ll ever care about such things, then you obviously don’t know much about me.  I’ll tell you what: if peer pressure is where it’s at, then come to me with the news that Umesh Vazirani, or Greg Kuperberg, or Matthias Troyer is now convinced, based on the latest evidence, that D-Wave’s chip asymptotically outperforms simulated annealing in a fair comparison, and does so because of quantum effects.  Any one such scientist’s considered opinion would mean more to me than 500,000 business deals.

The Argument from Consequences

Let me end this post with an argument that several of my friends in physics have explicitly made to me—not in the exact words below but in similar ones.

“Look, Scott, let the investors, government bureaucrats, and gullible laypeople believe whatever they want—and let D-Wave keep telling them what’s necessary to stay in business.  It’s unsportsmanlike and uncollegial of you to hold D-Wave’s scientists accountable for whatever wild claims their company’s PR department might make.  After all, we’re in this game too!  Our universities put out all sorts of overhyped press releases, but we don’t complain because we know that it’s done for our benefit.  Besides, you’d doubtless be trumpeting the same misleading claims, if you were in D-Wave’s shoes and needed the cash infusions to survive.  Anyway, who really cares whether there’s a quantum speedup yet or no quantum speedup?  At least D-Wave is out there trying to build a scalable quantum computer, and getting millions of dollars from Jeff Bezos, Lockheed, Google, the CIA, etc. etc. to do so—resources more of which would be directed our way if we showed a more cooperative attitude!  If we care about scalable QCs ever getting built, then the wise course is to celebrate what D-Wave has done—they just demonstrated quantum annealing on 100 qubits, for crying out loud!  So let’s all be grownups here, focus on the science, and ignore the marketing buzz as so much meaningless noise—just like a tennis player might ignore his opponent’s trash-talking (‘your mother is a whore,’ etc.) and focus on the game.”

I get this argument: really, I do.  I even concede that there’s something to be said for it.  But let me now offer a contrary argument for the reader’s consideration.

Suppose that, unlike in the “stone soup” scenario I outlined above, it eventually becomes clear that quantum annealing can be made to work on thousands of qubits, but that it’s a dead end as far as getting a quantum speedup is concerned.  Suppose the evidence piles up that simulated annealing on a conventional computer will continue to beat quantum annealing, if even the slightest effort is put into optimizing the classical annealing code.  If that happens, then I predict that the very same people now hyping D-Wave will turn around and—without the slightest acknowledgment of error on their part—declare that the entire field of quantum computing has now been unmasked as a mirage, a scam, and a chimera.  The same pointy-haired bosses who now flock toward quantum computing, will flock away from it just as quickly and as uncomprehendingly.  Academic QC programs will be decimated, despite the slow but genuine progress that they’d been making the entire time in a “parallel universe” from D-Wave.  People’s contempt for academia is such that, while a D-Wave success would be trumpeted as its alone, a D-Wave failure would be blamed on the entire QC community.

When it comes down to it, that’s the reason why I care about this matter enough to have served as “Chief D-Wave Skeptic” from 2007 and 2011, and enough to resume my post today.  As I’ve said many times, I really, genuinely hope that D-Wave succeeds at building a QC that achieves an unambiguous speedup!  I even hope the academic QC community will contribute to D-Wave’s success, by doing careful independent studies like the USC group did, and by coming up with proposals like Lidar’s for how D-Wave could move forward.  On the other hand, in the strange, unlikely event that D-Wave doesn’t succeed, I’d like people to know that many of us in the QC community were doing what academics are supposed to do, which is to be skeptical and not leave obvious questions unasked.  I’d like them to know that some of us simply tried to understand and describe what we saw in front of us—changing our opinions repeatedly as new evidence came in, but disregarding “meta-arguments” like my physicist friends’ above.  The reason I can joke about how easy it is to bribe me is that it’s actually kind of hard.