Shtetl-Optimized

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?

A lot has happened this past week concerning my job prospects for next year. I didn’t want to comment on the situation while it was still in flux, but now that the options are all on the table, I might as well let people know, and solicit advice about what to do.

First the bad news: against my and many other people’s expectations, I will not be starting a tenure-track position in CS this coming fall. Several of my interviews were cancelled, while at the schools where I did interview, I’ve been told that other candidates were chosen. Again and again I heard the same story: that while there was initially strong support for my application (particularly among theorists), concerns had arisen about some of my “extra-academic activities.”

A phone conversation last night, with someone I’ll call Prof. X from University Y, was typical. Prof. X started by explaining that, while the whole “blog” phenomenon had passed by him personally, some questions had come up during a hiring committee meeting with the more junior faculty — and, to get straight to the point, was it true that I wrote one of these “blogs” myself?

Yes, I said.

And was it true that this “blog” was known, in large part, for a debate about “battling vaginas”?

Biting vaginas, I corrected him.

And was it also true that I made frequent pronouncements about C*-algebras, modern art, and even string theory and loop quantum gravity, despite knowing next to nothing about any of these things?

Yes, I said.

And was it also true that, in the past few days, I’d spent much of my time defending the General Theory of Relativity against someone who calls himself “assman”?

Yes, I said.

Prof. X said he hoped I’d understand that, as far as he was concerned, I could write whatever I damn well pleased, but that, in an age of increasing sensitivities, and particularly in the wake of the well-known Luboš Motl debacle at Harvard, concerns had naturally arisen over whether a department could afford to gamble on someone with an “erratic personality.”

As you can imagine, this was all pretty depressing and unexpected for me. But I haven’t yet told you the second part of the story — which is that, over the last two days, some interesting new options have opened up.

On Thursday I got a call from Geordie Rose, asking whether I wanted to come work for D-Wave Systems in Vancouver. He said D-Wave had been stung by the criticism from experts following its announcement of the “world’s first commercial quantum computer,” and wanted to prevent a recurrence. So their idea was to hire an “in-house skeptic,” similar to the “white hats” hired by computer security companies to try and break their systems. I told Geordie I’d think about it, but that it mostly just depended on what sort of compensation package they could put together.

Meanwhile a second option has come up. Yesterday I got a call from the provost at Maharishi University of Management in Fairfield, Iowa, who wanted to know if I’d come to MUM to jump-start their quantum computing group. Apparently the Maharishi himself recently came across my paper on NP-complete Problems and Physical Reality, and, based on its contents, thought I’d make a perfect fit for MUM’s physics department. In particular, he wants me to lead a new project on whether NP-complete problems can be solved in polynomial time via “NDTM” (Nondeterministic Transcendental Meditation), thereby — as I wrote in the paper — making humanity one with God. The provost also reminded me that all the food at MUM is organic and vegetarian, so I wouldn’t have to worry about pork.

I have mixed feelings about all of this. On the one hand, I’ve been on a “conventional academic track” my whole life, so leaving that behind will be a big adjustment for me. On the other hand, perhaps this is a decision I already made a while ago — specifically, the moment I started this blog.

I’m told that the first rule of blogging is: “never, ever apologize for the long delay in updating your blog.” As it turns out, I have no need to apologize. You see, for the past ten days, I’ve been on an intense, meeting-packed, emotionally-draining sightseeing vacation around the United States. The places I picked to see on my vacation — more-or-less at random — included Princeton, New Jersey; the Hyde Park neighborhood of Chicago; and the southern riverbank of Cambridge, Massachusetts. To get the most out of my vacation, I made sure to wear my best nerd attire everywhere I went, and to sample all the fine restaurants, seminar rooms, and offices of computer science department chairs and deans. And since I still haven’t had enough R&R, in April I’m going on a second vacation — this time to Pasadena, Palo Alto, and other exotic locations on the west coast. As with everything else about my personal life, you can be sure to learn all the juicy details, in real-time, right here on this blog.

I’ve just come from a thin strip of volcanic ash near Antarctica, on which no mammal except bats set foot until a thousand years ago, and which today is mostly inhabited by sheep and by people who say “nigh-oh” when they mean “no.” I’m referring, of course, to New Zealand — or as the locals call it, “Middle Earth.” My colleague Andris Ambainis and I were in Auckland for four days, en route to QIP’2007 in Brisbane. While there, we were fed and sheltered by our friend Miriam and her boyfriend David. Miriam was both my housemate and officemate my first year at Berkeley; she now does user-interface research for a web-design company called Shift. You can see some of her handiwork, and learn more about her sheep-intensive homeland, by visiting this website. Hey, if Miriam took you around a place like this

you’d shill for her too.So, now that I was surrounded by one of the last relatively-intact wildernesses on Earth, what did I do there? If it were up to me, mostly blog, eat, and check email. Fortunately Miriam didn’t let me get away with my default ways, and repeatedly dragged me by my ears on Cultural Learning Experiences. And that’s what allows me to present the following Shtetl-Optimized New Zealand Educational Supplement.

• Auckland is almost certain to be destroyed sometime in the next few millennia by one of the fifty or so active volcanoes it’s built on. On the bright side, like most of the world’s current cities, it will probably be underwater long before that.

• New Zealand is the first place I’ve visited where the ozone hole is a serious everyday concern. Especially now, in summertime, when the hole over Antarctica is largest, you’re not supposed to go outside for even a few minutes without sunblock.

• I’d always imagined the Maori as a nearly-extinct people who lived on reservations doing tribal dances for tourists. Actually they’re ~15% of the population, and have so assimilated with the pakehas (whites) that these days Maori kids get sent to special schools, weekend programs, etc. to retain something of their language and culture. (Like Hebrew day school but with more jade weapons.) Andris and I did see a traditional Maori war-dance, but you could tell that the people doing it were going to check their text messages as soon as it was over.

• New Zealand was pretty much the last habitable landmass on Earth to be reached by human beings — not even the Maori got there until 1000AD. By comparison, the Aboriginals were already in Australia by 50,000BC. So why was New Zealand so much harder to reach than Australia? When we examine a mapa possible answer suggests itself: because New Zealand is so friggin’ far from everything else. Australia is practically in swimming distance from Southeast Asia by comparison. Because of this, reaching New Zealand and the other Pacific Islands took advances in boat-building and navigation that only happened recently in human history. Here’s another thing I never really appreciated before: the people who did get to these islands weren’t just drifting around randomly in their canoes. They knew exactly what they were doing. Like the Europeans who came later, they were setting out repeatedly on large, organized expeditions with the specific goal of finding new islands, returning to where they started from, and then coming back to the new islands with a settling party. Ideally the new islands would be chock-full of tasty animals like the moa that, unused to land-based predators, could then be hunted to extinction.

Alright, enough book-learnin’ — let’s see some more pictures.

NerdNote: When I first published this post, it mysteriously refused to show up. Finally I figured out the problem: I’d listed the date as January 29 (which it is here in Australia), but the WordPress software thought it was still January 28, and that it should therefore wait a day before updating!

Here are the PowerPoint slides for a physics colloquium I gave at Caltech yesterday, on “Computational Intractability as a Law of Physics.” The talk was delivered, so I was told, in the very same auditorium where Feynman gave his Lectures on Physics. At the teatime beforehand, I was going to put both milk and lemon in my tea to honor the old man, but then I decided I actually didn’t want to.

I’m at Caltech till Tuesday, at which point I leave for New Zealand, to visit my friend Miriam from Berkeley and see a country I always wanted to see, and thence to Australia for QIP. This Caltech visit, my sixth or seventh, has been every bit as enjoyable as I’ve come to expect: it’s included using Andrew Childs as a straight man for jokes, shootin’ the qubits with Shengyu Zhang, Aram Harrow, and Robin Blume-Kohout, and arguing with Sean Carroll over which one of us is the second-funniest physics blogger (we both agree that Luboš is the funniest by far). Indeed, John Preskill (my host) and everyone else at the Institute for Quantum Information have been so darn hospitable that from now on, I might just have to shill for quantum computing theory.

This morning, a reader named Bill emailed me the following:

I stumbled upon [Quantum Computing Since Democritus Lecture 9] by accident and it seemed quite interesting but I was ultimately put off (I stopped reading it) by all the references to god. As a scientist (and athiest) I think personal religious beliefs should be left out of scientific papers/lectures, you shouldn’t assume your readers/listeners have the same beliefs as yourself…..it just alienates them.

Dear Bill,

I’m impressed — you seem to know more about my personal religious beliefs than I do! If you’d asked, I would’ve told you that I, like yourself, am what most people would call a disbelieving atheist infidel heretic. I became one around age fourteen, shortly after my bar mitzvah, and have remained one ever since.

Admittedly, though, “atheist” isn’t exactly the right word for me, nor even is “agnostic.” I don’t have any stance toward the question of God’s existence or nonexistence that involves the concept of belief. For me, beliefs are for things that might eventually have some sort of observable consequence for someone. So for example, I believe P is different from NP. I believe I’d like some delicious Peanut Chews today. I believe the weather this January isn’t normal for planet Earth over the last 10,000 years, and that we and our Ford Escorts are not entirely unimplicated. I believe eating babies and voting for Republicans is wrong. I believe neo-Darwinism and the SU(3)xSU(2)xU(1) Standard Model (though not its supersymmetric extensions, at least until I see the evidence). I believe that if the God of prayer couldn’t get off His lazy ass during the Holocaust, or the Rwandan or Cambodian genocides, then He must not be planning to do so anytime soon — and hence, “trusting in faith” is utter futility.

But when it comes to the more ethereal questions — the nature of consciousness and free will, the resolution of the quantum measurement problem, the validity of the cosmological anthropic principle or the Continuum Hypothesis, the existence of some sort of intentionality behind the laws of physics, etc. — I don’t have any beliefs whatsoever. I’m not even unsure about these questions, in the same Bayesian sense that I’m unsure about next week’s Dow Jones average (or for that matter, this week’s Dow Jones average). All I have regarding the metaphysical questions is a long list of arguments and counterarguments — together with a vague hope that someone, someday, will manage to clarify what the questions even mean.

To me, the most remarkable thing you said was that, despite being otherwise interested in my lecture, you literally stopped reading it because of some tongue-in-cheek references to an Einsteinian God. That reminds me of a funny story. When I was a student at Berkeley, my mom kept pestering me to go to the campus Hillel for Friday night dinners. And to be honest, despite all the pestering, I was tempted to go. My temptation was largely driven by two factors that, for want of more refined terminology, I will call “free food” and “females.” For some reason, both factors, but particularly the second, were in short supply in the computer science department.

And yet, I couldn’t bring myself to go. Every time I passed the Hillel, I had this vision of a translucent Richard Dawkins (sometimes joined by Bertrand Russell) floating before me on the front steps, demanding that I justify the absurd Bronze Age myths that, by entering the Hillel building, I would implicitly be endorsing. “Come now, Scott,” Richard and Bertrand would say, with their elegant Oxbridge accents. “You don’t really believe that tosh, do you?”

“No, most assuredly not, good Sirs,” I would reply, and shuffle back to the dorm to work on my problem set. (The thought of spending Friday night at, say, a beer party never even occurred to me.)

Then, one Friday, I had a revelation: if God doesn’t exist, then in particular, He doesn’t give a shit where I go tonight. There’s no vengeful sky-Dawkins, measuring my every word and deed against some cosmic code of atheism. There’s no Secular-Humanist Yahweh who commanded His infidel flock at Sci-nai not to believe in Him. So if I want to go to the Hillel, then as long as I’m not hurting anyone or lying about my beliefs, I should go. If I don’t want to go, I shouldn’t go. To do otherwise wouldn’t merely be silly; it would actually be irrational.

(Incidentally, once I went, I found that the other secularists there greatly outnumbered the believers. I did stop going after a year or two, but only because I’d gotten bored with it.)

What I’m trying to say, Bill, is this: you can go ahead and indulge yourself. If some of the most brilliant unbelievers in history — Einstein, Erdös, Twain — could refer to a being of dubious ontological status as they would to a smelly old uncle, then why not the rest of us? For me, the whole point of scientific rationalism is that you’re free to ask any question, debate any argument, read anything that interests you, use whatever phrase most colorfully conveys your meaning, all without having to worry about violating some taboo. You won’t endanger your immortal soul, since you don’t have one.

If the trouble is just that the G-word leaves a bad taste in your mouth, then I invite you to try the following experiment. Every time you encounter the word “God” in my lecture, mentally substitute “Flying Spaghetti Monster.” So for example: “why would the Flying Spaghetti Monster, praise be to His infinite noodly appendages, have made the quantum-mechanical amplitudes complex numbers instead of reals or quaternions?”

Well, why would He? Any ideas?

RAmen, and may angel-hair watch over you,
Scott

Get a leg up on the competition, and offer me a tenure-track position in computer science right now! Here’s everything you’ll need to decide:

• Research Statement [PS] [PDF]
• Teaching Statement [PS] [PDF]
• CV [PS] [PDF]

In your offer letter, make sure to specify starting salary, teaching load, and the number of dimensions you’d like spacetime to have.

(Note to Luboš: Unfortunately, I wasn’t planning to apply to the Harvard physics department this year. But if you make a really convincing pitch, I might just be persuaded…)

Hearty, nontrivial Christmas greetings from SAT-a-Clause, the patron saint of theoretical computer scientists! Tomorrow night, SAT-a-Clause will once again descend all possible chimneys in parallel, nondeterministically guess which ones lead to cookies, and fill the corresponding “STOC-ings” with loads of publishable results!

As I’ve done every year since I was about 14, I’ll spend Christmas Eve at my best friend Alex’s house (this year bringing the girlfriend along). My role at Alex’s family gathering, of course, is to wage the secular-humanist War On Christmas: sanctimoniously insisting that guests say “Happy Holidays” instead of “Merry Christmas,” belching loudly during hymns and carols, mocking the Savior as a “competent if unoriginal 1^st-century rabbi,” and just generally dampening Christian faith, fomenting impiety, and advancing the cause of Satan. After all, what Christmas Eve celebration would be complete without a JudeoGrinch?

If your idea of the Christmas spirit includes, you know, peace on Earth, goodwill to all mankind, etc., you should check out this New York Times essay by Peter Singer, which Luca blogged about previously. Singer strikes me as one of the few public intellectuals who’s actually gotten wiser with age, as opposed to yet more cranky and intransigent. In this latest piece, he shows himself to be less concerned with chicken liberation than with eradicating rotavirus and malaria, less interested in the Talmudic question of whether a billionaire who’s given away 90% of his wealth is now morally obligated to give away the rest than in the practical question of how to get people to give more. I also recommend this column from last Christmas season by Nicholas Kristof — a writer who’s occassionally mistaken, never less than a mensch — in which he compares the War on Christmas to the war in Darfur, and challenges Bill O’Reilly to join him in witnessing the latter.

My sojourn in Northern California is now at an end; on Sunday I flew to my parents’ place near Philadelphia for Hanukhrismanewyears. But not before going to Stanford to give a talk to their string theory group about “Computational Complexity and the Anthropic Principle.” Here are the notes from that talk; you can think of them as a Quantum Computing Since Democritus Special Bonus Lecture.

(The best part of the talk — the lengthy arguments with Lenny Susskind, Andrei Linde, and the other stringers and cosmologists, in which I repeatedly used humor to mask my utter lack of understanding — is sadly lost to eternity. Fortunately, I’m sure that new such arguments will erupt in the comments section.)

In preparation for meeting Susskind and the other Stanford stringers, I made sure to brush up on both sides of the String Wars. On the anti-string side, I read Peter Woit’s Not Even Wrong and Lee Smolin’s The Trouble With Physics. On the pro-string side, I read Susskind’s The Cosmic Landscape and also spent hours talking with Greg Kuperberg, who tried to convince me that critics of string theory are as “intellectually non-serious” as quantum computing skeptics or Ralph Nader voters. I heartily recommend all three of the books.

So, what did I learn at Stanford? Among other things, that when you talk to string theorists in person, they’re much more open-minded and reasonable than you’d expect! Of course, when your de facto spokesman is the self-parodying Luboš Motl — who often manages to excoriate feminists, climatologists, and loop quantum gravity theorists in the very same sentence — it’s hard not to seem reasonable by comparison. But I’m not even talking about him.

(Conflict-of-interest warning: I’m painfully well aware that, so long as Luboš is around, I can only ever be the second-funniest physics blogger — even if the world champion in this field isn’t trying to be funny.)

In general, I’ve found that tolerance for alternative ideas, willingness to engage with counterarguments, rejection of appeals to authority, and so on are all greater when talking to string theorists in person than when attending their talks or reading their books and articles. Maybe that’s to be expected — to some extent it’s true of every field! But with string theorists, the magnitude of the difference always astonishes me.

Alright, let me get more concrete. One of the few nontrivial points of agreement between string theory and loop quantum gravity seems to be that, in any bounded region of spacetime, the number of bits of information is finite: at most ~10⁶⁹ bits per square meter of surface area, or (equivalently) at most ~1 bit per Planck area. In loop quantum gravity, this is basically because one bit of information is “stored” in each Planck area. In string theory, it’s much more subtle than that: the bits of information can’t be put into any sort of one-to-one correspondence with the Planck areas on the horizon, but they both add up to the same number. (Ignoring a factor of 4, which being a complexity theorist, I don’t care about.)

Now, much of my conversation with Susskind and fellow string theorist Steve Shenker focused on the following question: isn’t it a bizarre coincidence that the Planck areas and the bits of information should both add up to the same number, if there’s no “dual” description of string theory in which each bit (or rather qubit) is stored in a Planck area? Susskind agreed with me that such a “local” description of string theory (local on the boundary, not in the bulk) would be desirable — and that, if there isn’t such a description, then that by itself is a fundamental fact worthy of more attention. I’d expected Susskind and Shenker to brush aside my question as idle pontificating; instead, they seemed to want to reinvent string theory that very afternoon so that my question would have an answer!

When it became clear that no such reinvention of the theory was forthcoming (at least that afternoon), I suggested the following. We’ve got this one proposal, string theory, which has had some spectacular technical successes (like “explaining” the Bekenstein-Hawking entropy), but which, setting aside its other well-known problems, offers no “local” description of spacetime in terms of qubits and quantum circuits at the Planck scale. Then we’ve got this other proposal, loop quantum gravity, which has had fewer successes, but which does attempt such a local description at the Planck scale. So, if we agree that such a local description is our eventual goal, then shouldn’t an outsider guess that string theory and loop quantum gravity are probably just different footprints of the same beast — much like the different string theories themselves were found to be different limiting cases of an as-yet-unknown M-theory?

Susskind agreed that such a convergence — between the “top-down” picture of string theory, which grew out of conventional high-energy physics, and a “bottom-up” picture in terms of qubits at the Planck scale — was possible or even likely. He stressed that his opposition was not to the idea of describing spacetime in terms of local interactions of qubits, but rather to the specific technical program of loop quantum gravity, and to the exaggerated claims often made on that program’s behalf. When I reminded him that other people complain about exaggerated claims made on string theory’s behalf, he replied that the two cases were not even remotely comparable.

All in all, it was an extremely productive and enjoyable visit — one in which the conversation topics ranged over (among other things) the explanatory role of the Anthropic Principle, the possibility that the entire universe arose as a quantum fluctuation, the prospects for an efficient quantum algorithm for Graph Isomorphism, the relation between thermodynamics and quantum error-correction, and whether or not Gerard ‘t Hooft actually disbelieves quantum mechanics. Susskind told me, half-jokingly, that the Stanford string theory group was the world’s hotbed of anti-Landscape sentiment, and the arguments that I saw and participated in on my visit gave me no reason to doubt him.

So what are we to make of the fact that, on the one hand, the string theorists are such swell folks in person, and on the other hand, even the most cursory glance at their writings will reveal that the charge of triumphalist arrogance is far from undeserved? Well, to the anti-stringers, the obvious interpretation will be that the string theorists don’t really believe their own pablum: that they say one thing in public and a completely different thing in private. To the pro-stringers, the obvious interpretation will be that, beneath the façade we all erect around ourselves, the string theorists are just scientists like anyone else: grasping at the truth, struggling to learn more, convinced that string theory is the best idea we have but ready to ditch it if something better comes along. As usual, it all depends on where you’re coming from.

Alas, as tidy as this resolution sounds, it doesn’t help me pick sides in the String Wars currently raging through the blogosphere. But then again, why do I need to pick sides? I like hanging out with the loop quantum gravity people at Perimeter Institute. I like the fact that Lee Smolin’s publisher sent me a free review copy of The Trouble With Physics. I like the recent paper by Denef and Douglas on computational complexity and the string Landscape. And I like getting an all-expenses-paid trip to Stanford to have a freewheeling, day-long intellectual conversation with the string theorists there.

I have therefore reached a decision. From this day forward, my allegiances in the String Wars will be open for sale to the highest bidder. Like a cynical arms merchant, I will offer my computational-complexity and humor services to both sides, and publicly espouse the views of whichever side seems more interested in buying them at the moment. Fly me to an exotic enough location, put me up in a swank enough hotel, and the number of spacetime dimensions can be anything you want it to be: 4, 10, 11, or even 172.9+3πi. Is it more important for a quantum gravity theory to connect to the Standard Model, or to build in background-independence from the outset? Can one use the Anthropic Principle to make falsifiable predictions? How much is riding on whether or not the LHC finds supersymmetry? I might have opinions on these topics, but they’re nothing that a cushy job offer or a suitcase full of “reimbursements” couldn’t change.

Someday, perhaps, a dramatic new experimental finding or theoretical breakthrough will change the situation vis-à-vis string theory and its competitors. Until then, I shall answer to no quantum-gravity research program, but rather seek to profit from them all.

Update (12/23): The indefatigable Luboš Motl has put up a new jeremiad against me. Taking my ‘For Sale’ announcement completely seriously, Luboš writes:

It is absolutely impossible for me to hide how intensely I despise people like Scott Aaronson … He’s the ultimate example of a complete moral breakdown of a scientist. It is astonishing that the situation became so bad that the people are not only corrupt and dishonest but they proudly announce this fact on their blogs…

In fact, I have learned that the situation is so bad that when I simply state that Aaronson’s attitude is flagrantly incompatible with the ethical standards of a scholar as they have been understood for centuries, there could be some parts of the official establishment that would support him against me. There doesn’t seem to be a single blog article besides mine that denounces Aaronson’s attitude…

The difference between [the] two of us is like the difference between a superman from the action movies who fights for the universal justice on one side and the most dirty corrupt villain on the other side. It’s like the Heaven and the Hell, freedom and feminism, careful evaluation of the climate and the alarmist hysteria, or string theory and loop quantum gravity…

I can’t tell you how proud I am to have become “the most dirty corrupt villain” in Luboš’s cosmology, and no longer just an anonymous bystander. Thanks so much, Luboš, and Merry Christmas to you too!

Update (12/24): Man oh man, I had no idea that people would take my offer so seriously! Because of this, I now feel obligated to provide a financial disclosure statement. The Stanford string theorists did not actually pay my way to California, although they offered to — most of my expenses were covered by Umesh, my adviser at Berkeley. Stanford paid for (1) one night’s hotel stay in Palo Alto, and (2) one lunch, consisting of a small cheese pizza and an iced tea.