Shtetl-Optimized

What better way to procrastinate than to hear an Australian radio show interview me about the quantum query complexity of the collision problem, public-key cryptography, interactive proofs, computational intractability as a law of physics, and my great love for my high school? The first part of the program is about Australia’s population of cane toads (or rather, “tie-oads”). Then at 32:40, they start in with a report on the FQXi conference in Iceland, and interviews with Max Tegmark, Fred Adams, and Simon Saunders. I’m from 39:10 to 46:50.

A few comments/corrections:

• The interviewer, Pauline Newman, asks me about the practical implications of the collision lower bound, and then cuts to me talking about how quantum computers could break the RSA cryptosystem. Of course, the connection is only an indirect one (the collision lower bound is what gives hope that one could design collision-resistant hash functions that, unlike RSA, are secure even against quantum attacks).

• I said that, when trying to solve jigsaw puzzles or schedule airline flights, there doesn’t seem to be anything one can do that’s fundamentally better than trying every possibility. I should have added, “in the worst case.”

• The reason I mentioned how old I was when IP=PSPACE was proved is not that I’m a narcissist (though I am), but because in a section that was cut, Pauline asked me if I proved IP=PSPACE, and I was trying to make it clear that I didn’t. The theorem was proved by Shamir, building on work of Lund, Fortnow, Karloff, and Nisan.

• Pauline’s assertion that I “took off on a snowmobile without [my] passenger” and “left a distinguished physicist stranded on a glacier” is a gross exaggeration. What happened was, I waited and waited for someone — anyone — to climb onto my snowmobile. When no one did (maybe because everyone was scared by my abysmal driving ability), I figured I should just go.

Anyway, at least the um’s and uh’s seem to have been under control, compared to my interview with Lance two years ago.

I know I’ve been a derelict blogger since moving to MIT, allowing far, far too many of you to concentrate on work. But today I’m back with some quality procrastination material.

My colleague (and sometime überliberal commenter on this blog) Aram Harrow points me to a safety video for German forklift-truck drivers, which was posted to YouTube with English subtitles. As Aram says, it starts slow but is definitely worth watching to the end.

It’s funny: just this weekend, I was volunteering with the Cornell Alumni Association at the Greater Boston Food Bank. My job was to unload 40-pound boxes of canned goods from a forklift truck and place them on a conveyor belt. (And no, this is not something I’d normally do. Normally I’d offer to write a check to pay for ten people stronger than I am to unload boxes for the needy. Long story short, I was invited to do this by an individual of female persuasion.)

The whole time I was unloading boxes, I too was a bit worried about forklift safety — but, as I now know, not nearly as worried as I should have been.

…but it’s been discovered by empirical observation that the universe is not, as you famously claimed, the “ultimate free lunch.” Rather, the FQxi Conference on Foundational Questions in Physics and Cosmology in Reykjavik, Iceland is the ultimate free lunch.

Speaking of which, above you can see the discoverer of cosmic inflation himself, together with theoretical physicist Lawrence Krauss on his left, chatting on a glacier only minutes after engaging in a snowball fight.

And your humble blogger, who still can’t parallel park, hoping he’ll be able to steer a snowmobile without falling into any 1000-foot crevices.

Here I am with Cosmic Variance‘s Mark Trodden (who blogged earlier about this conference, saving me a good deal of work).

The dirt above is all area where the glacier previously was, but retreated over the last few decades.

To all those who say global warming is a myth: lo, I have watched a glacier melting with mine own eyes.

The geothermally-heated lagoon where part of the conference was held.

And just in case debating unfalsifiable cosmic hypotheses in a lagoon isn’t tacky enough, a PBS crew (from a show called “Closer to Truth”) was there to film it.

This is said to be the official divide between the North American and European tectonic plates.

In North America this would be a major tourist attraction with hotels, casinos, cotton candy shops, etc. Here it’s just another waterfall.

Curse me lucky charms, there’s no pot o’ gold!

I just got back from a conference in Reykjavik, Iceland (!), on “Foundational Questions in Physics and Cosmology.” Photos and trip report coming soon. For now, please content yourself with the following remarks, which I delivered to the assembled pontificators after a day of small-group conversation in a geothermally-heated lagoon.

I’ve been entrusted to speak for our group, consisting of myself, Greg Chaitin, Max Tegmark, Paul Benioff, Caslav Brukner, and Graham Collins.

Our group reached no firm conclusions about anything whatsoever.

Part of the problem was that one of our members — Max Tegmark — was absent most of the time. He was preoccupied with more important matters, like posing for the TV cameras.

So, we tried to do the best we could in Max’s absence. One question we talked about a lot was whether the laws of physics are continuous or discrete at a fundamental level. Or to put it another way: since, as we learned from Max, we’re literally living in a mathematical object, does that object contain a copy of the reals?

One of us — me — argued that this is actually an ill-posed question. For it’s entirely consistent with current knowledge that our universe is discrete at the level of observables — including energy, length, volume, and so on — but continuous at the level of quantum amplitudes. As an analogy, consider a classical coin that’s heads with probability p and tails with probability 1-p. To describe p, you need a continuous parameter — and yet when you observe the coin, you get just a single bit of information. Is this mysterious? I have trouble seeing why it should be.

We also talked a lot about the related question of how much information is “really” in a quantum state. If we consider a single qubit — α|0〉 + β|1〉 — does it contain one bit of classical information, since that’s how many you get from measuring the qubit; two bits, because of the phenomenon of superdense coding; or infinitely many bits, since that’s how many it takes to specify the qubit?

You can probably guess my answer to this question. You may have heard of the “Shut Up and Calculate Interpretation of Quantum Mechanics,” which was popularized by Feynman. I don’t actually adhere to that interpretation: I like to discuss things that neither I nor anyone else has any idea about, which is precisely why I came to this wonderful conference in Iceland. I do, however, adhere to the closely-related “What Kind of Answer Were You Looking For?” Interpretation.

So for example: if you ask me how much information is in a quantum state, I can show you that if you meant A then the answer is B, whereas if you meant C the answer is D, etc. But suppose you then say “yes, but how much information is really there?” Well, imagine a plumber who fixes your toilet, and explains to you that if the toilet gets clogged you do this; if you want to decrease its water usage you do that, etc. And suppose you then ask: “Yes, but what is the true nature of toilet-ness?” Wouldn’t the plumber be justified in responding: “Look, buddy, you’re paying me by the hour. What is it you want me to do?”

A more subtle question is the following: if we consider an entangled quantum state |ψ〉 of n qubits, does the amount of information in |ψ〉 grow exponentially with n, or does it grow linearly or quadratically with n? We know that to specify the state even approximately you need an exponential amount of information — that was the point Paul Davies made earlier, when he argued (fallaciously, in my opinion) that an entangled state of 400 qubits already violates the holographic bound on the maximum number of bits in the observable universe. But what if we only want to predict the outcomes of those measurements that could be performed within the lifetime of the universe? Or what if we only want to predict the outcomes of most measurements drawn from some probability distribution? In these cases, recent results due to myself and others show that the amount of information is much less than one would naïvely expect. In particular, the number of bits grows linearly rather than exponentially with the number of qubits n.

We also talked about hidden-variable theories like Bohmian mechanics. The problem is, given that these theories are specifically constructed to be empirically indistinguishable from standard quantum mechanics, how could we ever tell if they’re true or false? I pointed out that this question is not quite as hopeless as it seems — and in particular, that the issue we discussed earlier of discreteness versus continuity actually has a direct bearing on it.

What is Bohmian mechanics? It’s a theory of the positions of particles in three-dimensional space. Furthermore, the key selling point of the theory is that the positions evolve deterministically: once you’ve fixed the positions at any instant of time, in a way consistent with Born’s probability rule, the particles will then move deterministically in such a way that they continue to obey Born’s rule at all later times. But if — as we’re told by quantum theories of gravity — the right Hilbert space to describe our universe is finite-dimensional, one can prove that no theory of this sort can possibly work. The reason is that, if you have a system in the state |A〉 and it’s mapped to (where |A〉, |B〉, and |C〉 are all elements of the hidden-variable basis), then the hidden variable (which starts in state |A〉) is forced to make a random jump to either |B〉 or |C〉: you’ve created entropy where there wasn’t any before. The way Bohm gets around this problem is by assuming the wavefunctions are continuous. But in a finite-dimensional Hilbert space, every wavefunction is discontinuous!

We also talked a good deal about the many-worlds interpretation of quantum mechanics — in particular, what exactly it means for the parallel worlds to “exist” — but since there’s some other branch of the wavefunction where I told you all about that, there’s no need to do so in this one.

Oh, yeah: we also talked about eternal inflation, and more specifically the following question: should the “many worlds” of inflationary cosmology be seen as just a special case of the “many worlds” of the Everett interpretation? More concretely, should the quantum state you ascribe to your surroundings be a probabilistic mixture of all the inflationary “bubbles” that you could possibly find yourself in?

Other topics included Bell inequalities, the definition of randomness, and probably others I’ve forgotten about.

Finally, I wanted to take the liberty of mentioning a truly radical idea, which arose in a dinner conversation with Avi Loeb and Fotini Markopoulou. This idea is so far-out and heretical that I hesitate to bring it up even at this conference. Should I go ahead?

Moderator: Sure!

Well, OK then. The idea was that, when we’re theorizing about the nature of the universe, we might hypothetically want some way of, you know, “testing” whether our theories are right or not. Indeed, maybe we could even go so far as to “reject” the theories that don’t succeed in explaining stuff. As I said, though, this is really just a speculative idea; much further work would be needed to flesh it out.

Yesterday I loaded up my Prius with books, computers, bedsheets, a garbage bag full of underwear, and a summer student named Eyal Dechter, and we drove for twelve hours from Waterloo to MIT. This drive, while historic, was largely uneventful; the main obstacle we encountered along the way was the state of New York. Still, it was good to have someone around to share the driving, argue about the survival prospects of the human race, and point out when I left my parking brake on.

In return for helping deliver me to my new job alive, Eyal asked for just one thing: a list of papers in quantum computing and information that make explicit connections to foundational issues in physics, connections that even a physicist could recognize as such. (If we allowed implicit connections, we’d have to include pretty much every quantum computing paper ever written.)

There are many requests I can’t satisfy, but this isn’t one of them.

[AbramsLloyd] [AharonovJonesLandau] [Bacon] [BlumeKohoutHayden] [BriegelRaussendorf] [CavesFuchsSchack] [vanDam] [FarhiEtAl] [FreedmanKitaevWang] [Fuchs] [GottesmanPreskill] [Hardy] [Hardy] [KitaevMayersPreskill] [LiuChristandlVerstraete] [Lloyd] [Nielsen] [Smolin] [Spekkens] [TerhalDiVincenzo] [TonerBacon] [Vidal]

Notes:

1. The above list was produced by a rigorous selection process, which consisted of listing 21 papers that popped into my head. If I missed your favorite, tell me.
2. I deliberately excluded papers that try to sugarcoat esoteric complexity theorems no one would care about otherwise, by throwing around ill-digested physics buzzwords that the author probably saw in a pop-science magazine (for example, [A.] [A.] [A.] [A.] [A.-Ambainis]).

I’ve been in San Diego all week for the FCRC (Federated Computing Research Conference), which just wrapped up yesterday. I was here for Complexity’2007, but, lawless rebel that I am, I also crashed some of the talks at STOC’2007. Highlights:

• Many of my friends wanted to skip the plenary talk on “Computer Science: Past, Present, and Future,” by past Computing Research Association Chair Ed Lazowska. But I urged them to go despite the title, since I’d met Lazowska when I interviewed at the University of Washington, and immediately concluded that this is the guy we want in charge of our field. As it turned out, Lazowska gave the most rousing defense of computer science research I’ve ever heard. Here’s what I remember: 2004 was the first year that human beings produced more transistors than grains of rice (~10 quintillion). Academic computer science research more than paid for itself over the last two decades by producing at least 15 billion-dollar industries. Computer scientists should be tackling the biggest issues in the world, including climate change and third-world poverty (Lazowska mentioned a project he’s involved with to put thousands of sensors under the ocean near the Northwest US, thereby “reducing oceanography to a computer science problem,” as well as a project of his student Tapan Parikh, to let illiterate farmers in India and Guatemala upload financial records via cellphones with intermittent access). Computer scientists should bring self-driving cars from prototype to reality, thereby saving some of the 45,000 people in the US alone who die in auto accidents every year. The future of theoretical computer science lies in transforming the other sciences (math, physics, economics, biology) via computational thinking. Had Watson and Crick been computer scientists, they would’ve realized immediately that the real import of their discovery had nothing to do with the biochemical details, and everything to do with the fact that DNA is a digital code. A piece of computer science (P vs. NP) is what many now consider the preeminent open problem in mathematics. Quantum computing might not work but certainly merits a huge effort. Our introductory CS courses suck. We’ve been doing a terrible job recruiting women. Update (6/23): Slides for Ed Lazowska’s talk, as well as another inspiring talk by Christos Papadimitriou, can be found here.

• I gave a talk on my paper with Greg Kuperberg, on quantum versus classical proofs and advice.

• I gave another talk on the paper “Quantum t-designs”, by my colleagues Andris Ambainis and Joe Emerson. Why? Because Joe couldn’t make it to San Diego, and Andris lost his passport. As I promised Andris, the vast majority of the talk was not delivered in my imitation of his voice.

• Sergey Yekhanin gave a talk on his paper “Towards 3-query locally decodable codes of subexponential length,” which not only won the Danny Lewin Best Student Paper Award but also shared the STOC’07 Best Paper Award. Not to toot my own breakthrough-recognition horn, but … you saw it here first.

• Ryan Williams, the pride of Alabama, won the Complexity Best Student Paper Award for his excellent paper “Time-space tradeoffs for counting NP solutions modulo integers.” This marks the second time Ryan has won this award, as well as the first time the award has been given twice to a former Cornell undergrad and resident of Telluride House in the late 1990’s (no … wait). So what did Ryan prove? Alright, suppose you have O(n^1.8) time and n^o(1) memory, and you want to count the number of satisfying assignments of a Boolean formula, modulo a prime number p. Then there’s at most one prime p for which you can do this. Ryan has no idea which prime, and conjectures in any case that it doesn’t exist. I’m not making this up.

• Guy Kindler gave a talk on his amazing paper with Uri Feige and Ryan O’Donnell, “Understanding parallel repetition requires understanding foams.” Read the paper: the title is literally true.

• I saw Terence Tao.

• Ronald de Wolf and Harry Buhrman are reading this entry over my shoulder right now as I sit in the airport terminal typing.

• As I watched the conference regulars — Lance Fortnow, Bill Gasarch, Harry Buhrman (yes, Harry, you got another mention — happy?), Ken Regan, etc. — banter and drink coffee, I realized that the IEEE Conference on Computational Complexity desperately needs an official theme song. The song should have real complexity-theoretic content, but nevertheless be a little edgier than Find the Longest Path. So without further ado, I present to you a preliminary effort along these lines, due to Troy Lee and myself (aka “Nerdy by Nature”):
  

  You down with SPP (Yeah you know me)
  You down with SPP (Yeah you know me)
  You down with SPP (Yeah you know me)
  Who’s down with SPP (Every last attendee)

  (Note: BPP and ZPP also would’ve fit the meter, but those are really more appropriate for STOC than Complexity.)

  Update (6/20): We may have a winner, Aaron Sterling’s I Just Do Theory. (Thanks to Bill Gasarch for the pointer.)

They rejected me for undergrad. They rejected me for grad school. And for reasons best known to them, in July they’re going to let me loose on their campus as an Assistant Professor of Electrical Engineering and Computer Science.

This decision was one of the hardest I’ve ever made. I was lucky to have a half-dozen fantastic offers (apparently, larding your job talk with jokes actually works). I asked myself: can I really see myself as an “MIT person”? Can I deal with the pressure, the competitiveness, the non-rectangular Stata Center offices, the winters said to be even worse than Waterloo’s? Wouldn’t I prefer (for example) to return to my alma mater, and bask in the familiar sunshine of the People’s Republic of Berkeley — a place whose politics make Cambridge, Massachusetts look like Oklahoma City?

In the end, though, MIT simply refused to cooperate in giving me a good reason to turn it down. Among the considerations that tilted me toward Cambridge, the most important by far was the high caliber of ice cream available there. Other factors included the chance to get in some quality arguing time with Ed Farhi; students who solve your open problems before you’ve even finished stating them; the urge to spread the Gospel of Vazirani I imbibed at Berkeley in relatively virgin territory; and MIT’s role as a publicly-visible platform from which to pursue my central ambition in life, fighting doofosity wherever and whenever I find it. And, of course, a strong desire to be closer to Luboš Motl.

But just as I was getting ready to sign the contract, a sticking point emerged that threatened to derail the entire decision. My brother, David, had already taken the address aaronson@mit.edu. Luckily for me, though, David graduated just last week with a bachelor’s in math, and Srini Devadas, MIT’s Associate Head for Computer Science, has assured me in writing that I can have David’s address as soon as it lapses. As a new faculty member, I was even formally able to present David’s degree to him:

Let me end this post with a plea to any superstar undergrads who (when you’re not procrastinating by reading this blog) are considering applying to grad school in theoretical computer science. Sure, your decision might seem like an obvious one, but please give the “unBerkeley” a chance. If you do decide come to Cambridge, MA, there will now be someone around who you can work with — I mean, y’know, besides Demaine, Goemans, Goldwasser, Indyk, Karger, Kelner, Kleitman, Leighton, Lynch, Micali, Mitzenmacher, Rivest, Rubinfeld, Shor, Sipser, Sudan, Vadhan, Valiant, …

Besides defending quantum computing day and night, having drinks with Cosmic Variance‘s Sean Carroll, and being taken out to dinner at lots of restaurants with tablecloths, the other highlight of my job interview tour was meeting a friendly, interesting, articulate divinity student on the flight from San Francisco to Philadelphia, who tried to save my soul from damnation.

Here’s how it happened: the student (call him Kurt) was reading a Christian theological tract, while I, sitting next to him, was reading Russell on Religion. (This is true.) I sheepishly covered the spine of my book, trying to delay the inevitable conversation — but it finally happened, when Kurt asked me how I was liking ole’ Bert. I said I was liking him just fine, thank you very much.

Kurt then made some comment about the inadequacy of a materialistic worldview, and how, without God as the basis of morality, the whole planet would degenerate into what we saw at Virginia Tech. I replied that the prevention of suffering seemed like a pretty good basis for morality to me.

“Oh!” said Kurt. “So then suffering is bad. How do you know it’s bad?”

“How do you know it’s bad?”

“Because I believe the word of God.”

“So if God said that suffering was good, that would make it good?”

I can’t remember Kurt’s response, but I’m sure it was eloquent and well-practiced — nothing I said really tripped him up, nor did I expect it to. Wanting to change the subject, I asked him about his family, his studies, his job, what he’d been doing in the vipers’ den of San Francisco, etc. I told him a little about quantum computing and my job search. I mused that, different though we were, we both valued something in life more than money, and that alone probably set us apart from most people on the plane. Kurt said it was fitting that I’d gone to grad school at Berkeley. I replied that, as a mere Democrat, I was one of the most conservative people there.

Finally I blurted out the question I really wanted to ask. In his gentle, compassionate, way, Kurt made it clear to me that yes, I was going to roast in hell, and yes, I’d still roast in hell even if I returned to the religion of my ancestors (that, of course, being at best a beta version of the true religion). In response, I told Kurt that when I read Dante’s Inferno in freshman English, I decided that the place in the afterlife I really wanted to go was the topmost layer of hell: the place where Dante put the “righteous unbaptized” such as Euclid, Plato, and Aristotle. There, these pre-Christian luminaries could carry on an eternal intellectual conversation — cut off from God’s love to be sure, but also safe from the flames and pitchforks. How could angels and harps possibly compete with infinite tenure at Righteous Unbaptized University? If God wanted to lure me away from that, He’d probably have to throw in the Islamic martyr package.

San Francisco to Philadelphia is a five-hour flight, and the conversation ranged over everything you might expect: the age of the earth (Kurt was undecided but leaning toward 6,000 years), whether the universe needs a reason for its existence external to itself, etc. With every issue, I resolved not to use the strongest arguments at my disposal, since I was more interested in understanding my adversary’s reasoning process — and ideally, in getting him to notice inconsistencies within his own frame of reference. Alas, in that I was to be mostly disappointed.

Here’s an example. I got Kurt to admit that certain Bible passages — in particular, the ones about whipping your slaves — reflected a faulty, limited understanding of God’s will, and could only be understood in the historical context in which they were written. I then asked him how he knew that other passages — for example, the ones condemning homosexuality — didn’t also reflect a limited understanding of God’s will. He replied that, in the case of homosexuality, he didn’t need the Bible to tell him it was immoral: he knew it was immoral because it contradicted human beings’ biological nature, gay couples being unable to procreate. I then asked whether he thought that infertile straight couples should similarly be banned from getting married. Of course not, he replied, since marriage is about more than procreation — it’s also about love, bonding, and so on. I then pointed out that gay and lesbian couples also experience love and bonding. Kurt agreed that this was true, but then said the reason homosexuality was wrong went back to the Bible.

What fascinated me was that, with every single issue we discussed, we went around in a similar circle — and Kurt didn’t seem to see any problem with this, just so long as the number of 2SAT clauses that he had to resolve to get a contradiction was large enough.

In the study of rationality, there’s a well-known party game: the one where everyone throws a number from 0 to 100 into a hat, and that player wins whose number was closest to two-thirds of the average of everyone’s numbers. It’s easy to see that the only Nash equilibrium of this game — that is, the only possible outcome if everyone is rational, knows that everyone is rational, knows everyone knows everyone is rational, etc. — is for everyone to throw in 0. Why? For simplicity, consider the case of two people: one can show that I should throw in 1/2 of what I think your number will be, which is 1/2 of what you think my number will be, and so on ad infinitum until we reason ourselves down to 0.

On the other hand, how should you play if you actually want to win this game? The answer, apparently, is that you should throw in about 20. Most people, when faced with a long chain of logical inferences, will follow the chain for one or two steps and then stop. And, here as elsewhere in life, “being rational” is just a question of adjusting yourself to everyone else’s irrationalities. “Two-thirds of 50 is 33, and two-thirds of that is 22, and … OK, good enough for me!”

I’ve heard it said that the creationists are actually perfectly rational Bayesians; they just have prior probabilities that the scientifically-minded see as perverse. Inspired by conversations with Kurt and others, I hereby wish to propose a different theory of fundamentalist psychology. My theory is this: fundamentalists use a system of logical inference wherein you only have to apply the inference rules two or three times before you stop. (The exact number of inferences can vary, depending on how much you like the conclusion.) Furthermore, this system of “bounded inference” is actually the natural one from an evolutionary standpoint. It’s we — the scientists, mathematicians, and other nerdly folk — who insist on a bizzarre, unnatural system of inference, one where you have to keep turning the modus ponens crank whether you like where it’s taking you or not.

Kurt, who looked only slightly older than I am, is already married with two kids, and presumably more on the way. In strict Darwinian terms, he’s clearly been more successful than I’ve been. Are those of us who can live with A→B or B→C or C→not(A) but not all of them at once simply evolutionary oddities, like people who have twelve fingers or can’t stand sunlight?

1. I went on my first hot-air balloon ride (click here for photos). We landed in a Mennonite farm a half hour’s drive from Waterloo. Seven kids came out of the farmhouse to greet us, wearing caps and bonnets. These were the best-behaved kids I had ever seen in my life: they literally walked in formation, and only the oldest one spoke to us, the other six remaining silent. Having a balloon land on their farm was not at all a new experience for them.
2. I saw this xkcd cartoon, which succinctly captures a point that I’ve been trying to make for the last fifteen years, in arguments against conspiracy-mongers and other associated doofiati.
3. I read Elizabeth Kolbert’s New Yorker article about the Large Hadron Collider and the future of particle physics. I hereby nominate her for a Pulitzer; this is one of the best popular science articles I’ve ever read.
4. I saw Spider-Man 3, a profound philosophical drama that spoke to me on numerous levels. It is indeed true that with great power comes great responsibility; that we all have the capacity for good; and that, if we wish to vanquish the evil without, then we must first confront the arrogance within. My one complaint is that the Sandman was not a particularly effective villain. Let’s face it: sand just isn’t scary.
5. I got a job offer from MIT.

[Note: To clear up any confusion, I’m now lucky enough to have several great offers, and have not yet decided where I’m going, even unofficially.]

Last weekend, I got back from interviewing at the University of Washington, Stanford, Caltech, Berkeley, and Cornell. Then I fell asleep, and am only just now waking up. On this trip — surely the most exhausting I’ve ever been on — I seem to remember giving a talk on The Limits of Quantum Computers. (You’ll have to go to presentation mode to get the full effect of my PowerPoint animations, and especially the D-Wave montage on slide 2.)

The bulk of the time, however, was taken up with interviews. My interviewers — maybe 20 or 30 at each school, in CS, physics, applied math, even chemistry and electrical engineering — asked me good questions, questionable questions, hard questions, soft questions, loaded questions, lots of questions. And that’s what enables me, without further ado, to present for your reading enjoyment The Official Hiring Scott Aaronson FAQ.

[Note: The questions below are all things that I was actually asked by at least one interviewer — in some cases, by dozens of interviewers.]

Q: What will you do if quantum computing doesn’t pan out in the next 20 years?

A: This question presupposes that quantum computing should be judged as a high-risk engineering project. But that’s never been my view. My view is that it should be judged as basic science. What we’re trying to do is unify the theory of computing with our best theory of the physical world, and to perform the most stringent tests to which quantum mechanics itself has ever been subjected. For me, the payoff for better scientific understanding is not in some remote future — it’s as soon as the understanding is achieved.

Q: But why should we care about basic science?

A: Uhh, we are called the computer science department…

Q: Does quantum computing really belong in CS departments, as opposed to physics departments?

A: It belongs if we want it to belong! In my experience, the physicists have a bigger hurdle than the computer scientists in getting started with quantum computing research. All we need to do is ask ourselves: “what happens if we generalize probability theory to allow minus signs, and base it on the L₂ norm instead of the L₁ norm?” From then on it’s just the concepts we know and love: states, transformations, recursion, reductions, universality, asymptotic efficiency, and so on. Physicists, by contrast, have to learn most of this stuff for the first time. It’s been a great personal pleasure to watch physicists who once suspected that CS was devoid of intellectual content, struggle with that content while trying to learn quantum computing!

Now, if we want to take a dramatic scientific development that wouldn’t have been possible without computer science, and hand it over to the physicists on a silver platter, that’s certainly our prerogative. But is it in our interest as a field?

Q: What if quantum computing is fundamentally impossible?

A: That would be much more interesting than if it’s possible! Merely building a quantum computer would be the more boring outcome — the one consistent with all the physics we already know.

Q: But no one really questions quantum mechanics, do they?

A: Well, you just did!

Q: No, I only questioned whether quantum computing is possible. Couldn’t quantum mechanics be valid, but quantum computing still be impossible because of noise and decoherence?

A: If so, then there’s something enormous that we don’t yet understand about the relevant physics. Look, in light of the Threshold Theorem (that if the rate of decoherence per qubit per time step is smaller than some constant threshold, then one can perform an arbitrarily long quantum computation), it’s hard to maintain that we’re talking about some niggling technical issue. What we’re really talking about is this: to keep track of the state of N entangled particles, does Nature have to do an amount of computational work that increases exponentially with N? And if it doesn’t, then (turning the question around) is there an efficient classical algorithm to simulate the behavior of N entangled particles? These are not questions that will just go away for some trivial reason that everyone’s overlooked.

Q: Suppose Ed Witten spent a week thinking about it, and came up with some profound reason why quantum computing is impossible. What would you do next?

A: I’d drop whatever else I was doing, and devote all of my time to understanding the implications of his discovery for computer science and physics!

[Pause]

Of course, since this is Witten, maybe he would’ve spent a second week and worked out all the implications himself. So I guess all I can say is that to my knowledge, he hasn’t in fact been thinking about these issues.

Q: How long until we have practical quantum computers?

A: In my opinion, quantum computing experiments are not yet at a stage where one can make “Moore’s Law” type predictions. We might be in the same situation with quantum computing that Babbage was with classical computing in the 1840’s. In other words, we think we know the fundamental principles, and we’re right — but the technology isn’t there yet, and might not be for a long time.

Of course, as with any technology, progress could happen faster than almost any of us expect. But I prefer to be pessimistic: that way either you’re right, or else you don’t mind being wrong!

Q: How many qubits are the experimentalists at so far?

A: It depends how you measure. People got up to twelve qubits in liquid-state NMR, the platform that was used some years ago to factor 15 into 3×5 (at least with high probability!). The trouble with liquid NMR is that no one knows how to scale it: currently the signal decreases exponentially with the number of qubits. So people turned their attention to other platforms, such as ion traps, photonics, and solid-state NMR. With these platforms the quantum computer’s state is much closer to being pure, so the prospects for scalability are much better. But manipulating the qubits is correspondingly harder. With ion traps, Rainer Blatt’s group in Innsbruck did tomography of an 8-qubit state, and other groups have done computations involving 2 or 3 qubits. With photonics, it’s easy to get a huge number of qubits that are highly coherent; the problem is that photons don’t like to talk to each other (in fact they fly right past each other), and therefore you can only apply two-qubit gates by using matter particles as intermediaries.

There are other more exotic proposals for scalable quantum computing, such as “nonabelian anyons.” With these I think it’s fair to say we’re not even at one qubit yet. But if these proposals did work, then the hope would be that they could leapfrog over the other proposals by building in error-correction for free.

Q: Which universities in North America are the major centers for quantum computing theory?

A: Right now there are four: Waterloo, Caltech, MIT, and Berkeley.

Q: Supposing we had scalable quantum computers, are your lower-bound results telling us that they would have no applications?

A: Absolutely not. Aside from their intrinsic scientific interest, quantum computers would have real applications. In my opinion, the most important would be the one so obvious that we computer scientists hardly ever talk about it: namely, simulating quantum physics and chemistry! This, of course, is what a quantum computer does in its sleep. At the same time, it’s also a fundamental problem in nanotechnology, high-temperature superconductivity, QCD, and other areas, important enough that Nobel prizes have been awarded even for ways to solve special cases efficiently on a classical computer.

Admittedly, you could say that every physical system in the universe is a quantum computer computing its own evolution! But the goal here would be to build a universal quantum simulator: a single machine that can be programmed to efficiently simulate any quantum system of interest. It’s the difference between building a wind tunnel versus writing code in order to simulate an airplane.

Now, by a sort of lucky accident, we can sometimes coax a quantum computer into solving classical problems asymptotically faster than we know how to solve them with a classical computer. The famous examples are of course (1) breaking RSA and other cryptographic codes, and (2) solving ‘generic’ search problems quadratically faster than a classical computer. These discoveries have enormous theoretical interest, but (as far I can tell) only limited practical interest. Maybe I’m wrong though.

Q: Granted that quantum computing is already interesting as basic science, do you agree that it would be more interesting if we had practical quantum computers?

A: Well, I certainly wouldn’t mind it.

Q: You work on quantum computing, yet most of your research is about how quantum computers wouldn’t be very powerful. Isn’t that a bit strange?

A: In the long run, I don’t think quantum computing research is helped by falsehood. If we’re going to be scientists and not PR flaks, then obviously we ought to welcome the truth, whichever way it goes.

But personally, I’d go even further than that. For me, a model of computation without any limitations would be like Superman without kryptonite. There just wouldn’t be a whole lot to say about it! To my way of thinking, a model that lets you factor integers efficiently but not solve NP-complete problems is actually more interesting than a model that gives you everything!

Oh, and one further point: if you’re interested (as I am) in the ultimate limits of computation, then you’re almost professionally obligated to study quantum computing. Why? Because any time you prove a limit of classical computers, you now have to ask yourself: is this something fundamental, or is it just an artifact of my working in a high-decoherence regime?

Q: Why are you so interested in the limits of computation?

A: To show that something is possible, you just have to find a way to do it. But to show that something’s not possible, you have to consider every way of doing it, and prove that none of them work. This is why negative results are so much rarer than positive results, but also why they often give us deeper understanding.

Q: That seems like an extremely male perspective! [said, jokingly, by a female interviewer]

A: I respectfully disagree. Look, as with pretty much every area of CS, we could certainly use more talented women in quantum computing theory: maybe a few dozen more Dorit Aharonovs, Julia Kempes, and Barbara Terhals. I find the gender imbalance in CS depressing, and I’ve long been interested in what it would take to correct it. But the relevant question is this: is the proportion of women working on quantum lower bounds smaller than the proportion working on quantum algorithms? I don’t think that it is.

Q: What’s your vision for where your research is headed in the next 5-10 years?

A: I know I’m not supposed to say this in an interview, but I don’t have a vision. I have this annoying open problem, that conjecture, this claim that seems wrong to me. I know some people have a coherent vision for where their research is headed. And in experimental areas, obviously you have to justify what you’re going to do with your $200 million of equipment. But at least in theoretical computer science, having a “vision” always seemed incredibly difficult to me.

For example, let’s say you have a vision that you’re going to solve problem X using techniques A, B, C. Then what do you do when you find out that techniques A and C are total nonstarters — but that technique B, while it’s useless for X, does solve a completely unrelated problem Y? What you do is make up a story about how Y was the problem you wanted to solve all along! We all do that: drawing targets around where the arrows hit is simply the business we’re in.

What I can tell you is this: I’m interested in fundamental limits on what can be efficiently computed in the physical world. I look for problems that can be addressed with tools from theoretical computer science, but that also have some physical or philosophical point: something that makes me feel like the universe would be a different place if the conjecture were true than if it were false.

In the past, quantum computing has been an incredibly rich source of that sort of problem for me. But it’s never been my exclusive interest — I’ve also worked on circuit complexity, Bayesian agreement protocols, and even information retrieval and clustering. And if quantum computing ever stops being a source of conceptually rich open problems, then I’ll look for those problems somewhere else.

Q: I noticed that, on at least three occasions where you proved a new quantum lower bound, other people quickly improved it to an optimal bound. Is there a reason why you didn’t prove the optimal bounds yourself?

A: Yeah, I don’t seem to be very good at tightening my lower bounds! I’ve had more success in proving the first nontrivial lower bound for a given problem — that is, in understanding why the complexity scales exponentially rather than polynomially. After that, I’m more than happy to let others pin down the order of the exponential. Every time that’s happened, far from feeling disappointed over being “scooped,” I felt great that my work gave other people a foundation to build on.

Q: You look tired. Would you like some coffee?

A: Yes.

Q: How did you get interested in quantum computing?

A: When I first learned about programming as an 11-year-old, it wasn’t only a revelation to me because I now understood how video games worked (though that was definitely important). The real revelation was: this is how the entire universe must work! It’s all just bits getting updated by simple rules. I don’t have to understand physics if I want to understand physics.

Of course I’d heard of quantum effects, and I knew they were supposed to be important — but since I didn’t understand them, they made no difference to me. Then later, as an undergrad at Cornell, I read the early quantum computing papers, and found out that this “quantum weirdness” the physicists kept babbling about was nothing more than linear algebra over the complex numbers. “Hey, linear algebra … even I can do that!”

But I didn’t really become engrossed in quantum computing until a summer internship at Bell Labs. As a diversion from my “real” work that summer (which had to do with multivariate isotone regression), I went through the Bernstein-Vazirani paper, and managed to improve their containment BQP ⊆ P^#P to BQP ⊆ PP. Then I found out that Lov Grover worked in the same building as me, so I went and told him about my result. Well, it turned out that BQP ⊆ PP was already known — it had been proved by Adleman, DeMarrais, and Huang the year before. But one consequence of my talking to Lov was that I ended up doing an internship with him the next summer, working (mostly unsuccessfully) on quantum lower bounds. Ashwin Nayak was also working with Lov that summer; from Ashwin I found out about Umesh Vazirani’s group at Berkeley and how all the cool people were there.

After that, the main questions in my mind were whether I could get accepted to Berkeley, whether Umesh would take me on as a student, and whether I was good enough to do anything original in this field. I emailed Umesh and he never responded, which I took as an extremely bad sign — how little I knew back then! Luckily I did get in to Berkeley, I did start working with Umesh, I did stumble on some new results, and I guess the rest is history.

Q: How many people work on the computer science side of quantum computing?

A: Probably the best way to measure that is by how many people attend the annual QIP conference (for if they don’t go to QIP, do they really exist?) Last year’s QIP drew almost 200 attendees.

Q: Would you be willing to supervise grad students in classical theoretical computer science?

A: Willing is an understatement! I would love to supervise talented grad students in derandomization, circuit lower bounds, learning theory, or any of the other classical areas that I try hard to keep up with and occassionally even work on. Admittedly, when it comes to (say) list decoding, extractors, approximation algorithms, or PCP, the students would first have to teach me what’s going on, but after that I’d be happy to supervise them.

Q: What would you say if I told you that I think quantum computing is like postmodern literary criticism, just a way for people to churn out one paper after another by switching words around, citing each other in a circular way, recycling the same few mathematically trivial ideas over and over — and indeed, that the whole field of theoretical computer science has no real ideas and no connections to anything outside itself?

A: I’d say thank you very much for your opinion, and you’ve got me for — let’s see, 25 more minutes, so what can I do for you?