## The Hiring Scott Aaronson FAQ

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_{2} norm instead of the L_{1} 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?

Comment #1 May 5th, 2007 at 4:23 pm

About gender balance… I think it can only be adressed at this point if some CS theorists undergo a gender reassignment surgery!

…

uhu.. Just a joke, folks, no need to lecture me about gender identity and all.

Comment #2 May 5th, 2007 at 4:26 pm

So, did they give you offers at the end?

Comment #3 May 5th, 2007 at 4:33 pm

I hope you get into Stanford and can help boost our program (if we even have one) up into the top. That’d be excellent.

Comment #4 May 5th, 2007 at 4:59 pm

So, did they give you offers at the end?Patience, my friend, patience. All will be revealed in time.

Comment #5 May 5th, 2007 at 6:49 pm

Scott, I spoke to you during your interview at Waterloo (understandably, none of my questions made it into the FAQ).

What you may not know is that Waterloo is actually home to

twocompletely independent, top-notch quantum research centres. Oh sure, there’s the usual PI/IQC bunch. But just a stone’s throw away from PI, in the first floor of a nearby condo complex, there’s also the Quantum Power Centre of Canada. As I’m sure you know, they market and demonstrate an advanced healing device called the EPFX, the “Electro Physiological Frequency Xrroid”. From their web page:(And so on…)

This facility is on my path from home to shopping, so I pass by it frequently, and think of you every time. They would doubtlessly stand to gain a great deal with a person of your expertise in town. I’m sure you’d have many probing questions to ask them at one of their open houses, and I would pay good money to watch that exchange.

Comment #6 May 5th, 2007 at 7:36 pm

You better hope they don’t grade you on class.

Comment #7 May 5th, 2007 at 8:47 pm

Sounds like you are smitten by what Witten has written.

Comment #8 May 5th, 2007 at 8:55 pm

Did someone actually asked the last one ? Or did you ‘rewrite’ it from the polite form it was asked in ?

Comment #9 May 5th, 2007 at 11:23 pm

That “extremely male” response was just… baffling. I don’t understand at all how that perspective has anything to do with gender.

Come to Caltech? Pleease? Teach Quantum Computing Since Democritus here!!

Comment #10 May 6th, 2007 at 12:27 am

Inspired by one of the questions…

How many theorists and experimentalists – worldwide – work on quantum computing and quantum information theory?ISI Web of Knowledge cites 2,231 authors with papers

# published between Jan 2005 and today

#

quantum computer(s) / computation / computing / informationand/orqubit(s)in the title.So, 2,000-3,000 researchers might be a good guess?

Comment #11 May 6th, 2007 at 1:51 am

Did someone actually asked the last one ? Or did you ‘rewrite’ it from the polite form it was asked in ?Obviously I didn’t tape-record the questions, and my memory is highly fallible. But yes, phrases like “similar to postmodernism,” “circular,” and “no real ideas” most certainly did occur in this “question.”

Comment #12 May 6th, 2007 at 2:15 am

“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.”

If quantum mechanics is false and quantum computers show it to be so, that would quite cool. But couldn’t quantum mechanics be false, for reasons which have nothing to do with quantum computing? (It isn’t clear what the questioner is getting at.) In that case, I don’t know how relevant quantum computing would be, except probably some of its techniques would be useful in analyzing the next physical model. Of course, this would be extremely surprising.

On the other hand, if large quantum computers are built soon, then these will be our strongest tools for studying quantum mechanics (I think), and thus perhaps the most likely experimental tool for disproving quantum mechanics.

Comment #13 May 6th, 2007 at 4:40 am

Those questions about ‘male perspective’ and postmodernism go a long way to reinforcing my stereotypes about academia. Were they asked with any indication of humor or sarcasm?

Since you’re in waterloo, have you ever checked out bicycle forest?

Comment #14 May 6th, 2007 at 4:49 am

Bram, the comment about ‘male perspective’ was made with a large dose of humor; the one about postmodernism was not.

Mostof the interviewers I met were friendly and interesting and asked excellent, pointed questions — and even if they were skeptical about quantum computing or CS theory in general, they were willing to be swayed by evidence. Naturally, though, it’s the few hostile interviewers who are more salient in my mind!Comment #15 May 6th, 2007 at 6:09 am

How come you didn’t mention the D-Wave effort along the lines of previous schemes like NMR, ion trap, photonics, etc.?

Comment #16 May 6th, 2007 at 6:30 am

Because D-Wave hasn’t supplied evidence that they’ve built any coherent qubits at all! I interpreted the question as one of what’s been reported in the published literature.

Comment #17 May 6th, 2007 at 6:52 am

Scott, you deserve the best, I hope you get the job you want the most (Berkeley?). I loved the honesty of the reply to the question about vision; it seems so true, and not just in CS research, but probably in many branches of mathematics. It makes me wonder why many others don’t hesitate at all before detailing grandiose visions in reponse to these questions.

Speaking of Witten, how in the world did that guy transfer into physics from his field? I read that he was a history student.

Comment #18 May 6th, 2007 at 9:28 am

Scott:

I emailed Umesh and he never responded, which I took as an extremely bad sign — how little I knew back then!This is highly off-topic, but ever since Umesh teased us with a description of it in the comments a while back, I’ve been trying to track down a copy of “Relativizing versus Nonrelativizing Techniques: the Role of Local Checkability”. There is even a (dead) link to it on his home page. I sent him an email asking about it, but alas, no response.

Not that you don’t have anything better to do with your time, but do you still have a copy of this manuscript lying around that you could upload?

Comment #19 May 6th, 2007 at 10:37 am

Kurt: I just called Umesh up, and he promises me that the link from his homepage will be working by the end of today.

(I do have an earlier draft of the paper, but Umesh asked me not to upload it, calling it “rough” and “embarrassing.”)

Comment #20 May 6th, 2007 at 10:41 am

Thanks!

Comment #21 May 6th, 2007 at 10:57 am

I loved this post. I am sure I can use some of the insights directly in my PhD defense soon enough! Good luck with the job search!

Comment #22 May 6th, 2007 at 11:01 am

Kaveh, GeekInThePink, Stuart, Domenic: Thanks!!

Comment #23 May 6th, 2007 at 12:09 pm

scott, i also loved your refreshing reply about “vision”. i am reminded of a research proposal that dror bar-natan had posted on his homepage — he said something like “above everything, i intend to follow my nose”. all the best with your search!

Comment #24 May 6th, 2007 at 12:29 pm

I completely agree about the vision thing. What’s more, in my experience, interviewers are actually impressed by the kind of answer you gave – it’s more promising to get a non-traditional response that’s been thought out than a canned traditional one.

Comment #25 May 6th, 2007 at 3:48 pm

How many theorists and experimentalists – worldwide – work on quantum computing and quantum information theory?A brave answer might have been: “I foresee that during the coming century, one person in 100,000 will pursue research in quantum information theory (QIT). And furthermore, each theorist will write, during his or her lifetime, at least one article that has fundamental and enduring value for QIT—meaning, sufficient value to justify a lifetime’s sincere endeavor by that person.”

Now let’s work the numbers. Ten billion people, one QIT person per hundred thousand — thats 100,000 theorists, and therefore, 100,000 QIT articles “of fundamental and enduring value” to be written in the coming century.

Obviously, QIT is destined to be a growth industry!

Just to state a personal opinion, the above numbers are IMHO a pretty good estimate of the size and achievements of the QIT community in the coming century (‘cuz why else read the QIT literature, and Scott’s blog?).

Comment #26 May 6th, 2007 at 5:20 pm

Scott,

I have a (stupid) question.

> 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

I assume that this threshold would be a function of the number of qubits and that the really interesting question is how this function looks like. Is this correct or does asking such a question reveal that I am a physicist?

Comment #27 May 6th, 2007 at 6:09 pm

Wolfgang: No, constant

really doesmean constant! That’s what surprised a lot of people about the Threshold Theorem.In particular, under a typical gate and noise model, you can tolerate an error rate per qubit per time step of about 10

^{-5}, and still do universal quantum computation. Intuitively, once the error rate falls below a certain critical point, you start being able to correct errors faster than they occur. You can thereby make theeffectiveerror rate arbitrarily small, by applying multiple layers of error-correction recursively.Indeed, the main question these days is “just” to pin down the value of the threshold. It’s known (again, in a typical model) that if the error rate per qubit per time step is more than 45%, then you

can’tdo universal quantum computation — i.e., anything you can do can be simulated efficiently by a classical computer. So there’s a gap of several orders of magnitude between the known upper and lower bounds. But people are working hard to close that gap, and while rigorous results are hard to come by, there are some tantalizing numerics suggesting that much higher error rates (i.e., 1-3%) should be tolerable.Comment #28 May 7th, 2007 at 2:44 am

I would basically agree with your summary of the state of experiments, but would point out that you

canprepare an NMR quantum computer in an almost pure state, as described in Phys. Rev. Lett.93, 040501 (2004) and subsequent papers.Sadly this only works for 2 qubits at the moment; in principle this could be extended, but it’s not yet a plausible route.

Comment #29 May 7th, 2007 at 4:43 am

Hey wolfgang, to put it in physics speak, the threshold is related to a phase transition. You can nearly think about the threshold as the temperature below which a coherent quantum order can exist. Okay, very roughly.

(Now if I’m in a bad mood I might quible with “arbitrarily long” as arbitrarily long requires the log of arbitarily many qubits )

Comment #30 May 7th, 2007 at 8:07 am

Scott,

Re your answer to Wolfgang,

Is it fair (or even close to fair) to say “decoherence rate” in place of “error rate”?

Are the existing error rates closer to 45% or to .001%?

How do error rates vary as you increase or decrease the length of a timestep?

TIA

Comment #31 May 7th, 2007 at 9:57 am

Scott replies to Wolfgang:

But people are working hard to close the [threshold theorem] gap, and while rigorous results are hard to come by, there are some tantalizing numerics suggesting that much higher error rates (i.e., 1-3%) should be tolerable [in typical quantum computer designs].Scott’s remark has the following natural extension:

[…], and people are working just as hard to raise thelowerbound of the theshold theorem, which is to say, to show that for “typical” quantum systems, error rateslowerthan 45% still allow polynomial-time classical simulation.Notice that the above carefully says “people are working just as hard”, rather than “just as many people are working”!

The two problems are of precisely equal fundamental interest (obviously). From a practical point of view … well … raising the lower bound has a broader range of near-term applications.

Indeed, the following—deliberately provocative—conjecture seems natural (to me as an engineer):

Given a system composed of “n” total qubits, linked by any number of gates, having a fixed nonzero error rate per gate, and a fixed nonzero probability of correct computation, that system can be simulated with classical resources that scale polynomially in “n”That this conjecture might be compatible with the threshold theorems is (hopefully) ensured by the restriction “fixed nonzero probability of correct computation”, which is intended to force larger-n devices to allocate a larger fraction of their qubit resources to ancilla quibits and/or error correction codes.

Thinking about this conjecture leads me to imagine a hilarious Alice-and-Bob “arms race”, in which for fixed

nAlice implements a successful error detection code, which Bob then breaks by doublingn, forcing Alice to implement yet another level of error detection codes, etc.At this point it becomes pretty clear the error threshold theorems are darn tricky, and that the details of their assumptions *do* matter.

Which makes me hope that someone on Scott’s blog—please!—will explain the underlying assumptions of the threshold theorems in greater detail!

Comment #32 May 7th, 2007 at 1:01 pm

James: For simplicity, one often just models error as “depolarizing noise” (i.e., as decoherence toward the maximally mixed state), but the Threshold Theorem certainly works with more general kinds of errors. I don’t know how the threshold varies with the class of error allowed — maybe someone more versed in these things can enlighten us?

By “existing error rates,” do you mean the error rates that are achievable experimentally? That varies a lot with the technology, but in general I’d say closer to 45% than 0.001%. (5-20% seems like a pretty typical range.)

The error rate is

definedas the number of errors per qubit per timestep. Of course, if your timesteps take twice as long, thenall else being equalyou’ll encounter roughly twice as many errors per timestep. But all else isnotnecessarily equal, since slowing down the computation might also slow down the error processes.Comment #33 May 7th, 2007 at 1:02 pm

John Sidles, I may be reading your conjecture wrong — but in light of threshold theorems I think it could only be true if BQP could be classically simulated efficiently. The “fixed nonzero probability of correct computation” doesn’t seem to change anything.

Comment #34 May 7th, 2007 at 1:39 pm

Scott and Dave,

thank you for the answer. I guess, all of a sudden I begin to see why this whole quantum computing business really *is* interesting

Comment #35 May 8th, 2007 at 3:31 am

Aaron, great article! I just emailled it to everyone in our lab. Good luck with the offers (if North America is incredibly foolish and doesn’t make you any, please consider Australia, we’re keen on QI here…). BTW, would you permit me to use, with full attribution of course!, the second slide from your Powerpoint presentation?

Comment #36 May 8th, 2007 at 5:27 am

//

the second slide from your Powerpoint presentation//The slide is cool. Somebody call Penn & Teller!

Comment #37 May 8th, 2007 at 6:50 am

Sure, Andrew! But if you’re going to cite me, please call me Scott and not Aaron.

Comment #38 May 8th, 2007 at 9:27 pm

Dear Scott,

Ooops! (and bugger it, damn, and blast)

Many apologies: low caffeine + too little sleep = idiot who gets names wrong

Cheers,

Andrew

Comment #39 May 14th, 2007 at 5:34 pm

Hi Scott,

It’d be GREAT if you could join us at Stanford. All the prof’s I’ve been talking to have been talking about you and how it’d be great if you joined here.

Looking forward to your decision and seeing you at Stan!!

Ajay

Comment #40 May 18th, 2007 at 11:27 am

[…] One post of Scott’s that I like very much is his “The Hiring Scott Aaronson FAQ“, where he lists some of the questions he was asked in his job search (he is a postdoc at my alma mater, the University of Waterloo’s Department of Combinatorics and Optimization). I’ve interviewed for a job or two in the couple year’s this blog has been going, but I have not been bold enough to talk about it. Scott uses the entry as a very quick survey of what he believes in, and the interviewers don’t come across like idiots (I guess I would have asked about half the questions myself). […]