Shtetl-Optimized

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?

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