To remind you, this book is based on a course I taught in 2006. On the last day of class, I followed the great tradition pioneered by Richard Feynman, in which the last class should be one where you can ask the teacher anything. Feynman's rule was that you could ask about anything except politics, religion, or the final exam. In my case, there was no final exam, and I didn't even make politics or religion off-limits. This chapter collects some of the questions people asked me, together with my responses. Student: Do you often think about using computer science to limit or give us a hint about physical theories? Do you think that we'll be able to discover physical theories which give more powerful models than quantum computation? Scott: Is BQP the end of the road, or is there more to be found? That's a fantastic question, and I wish more people would think about it. I’m being a bit of a politician here and not answering directly, because obviously the answer is “I don't know.” I guess the whole idea with science is that if we don't know the answer, we don't try to sprout one out of our butt or something. We try to base our answers on something. So, everything we know is consistent with the idea that quantum computing is the end of the road. Greg Kuperberg had an analogy I really liked. He said that there are people who keep saying that we've gone from classical to quantum mechanics so what other surprises are in store? But maybe that's like first assuming the Earth is flat, and then on discovering that it's round, saying who knows, maybe it has the topology of a Klein bottle. There's a surprise in a given direction, but once you've assimilated it, there may not be any further surprise in that same direction.
To remind you, this book is based on a course I taught in 2006. On the last day of class, I followed the great tradition pioneered by Richard Feynman, in which the last class should be one where you can ask the teacher anything. Feynman's rule was that you could ask about anything except politics, religion, or the final exam. In my case, there was no final exam, and I didn't even make politics or religion off-limits. This chapter collects some of the questions people asked me, together with my responses. Student: Do you often think about using computer science to limit or give us a hint about physical theories? Do you think that we'll be able to discover physical theories which give more powerful models than quantum computation? Scott: Is BQP the end of the road, or is there more to be found? That's a fantastic question, and I wish more people would think about it. I’m being a bit of a politician here and not answering directly, because obviously the answer is “I don't know.” I guess the whole idea with science is that if we don't know the answer, we don't try to sprout one out of our butt or something. We try to base our answers on something. So, everything we know is consistent with the idea that quantum computing is the end of the road. Greg Kuperberg had an analogy I really liked. He said that there are people who keep saying that we've gone from classical to quantum mechanics so what other surprises are in store? But maybe that's like first assuming the Earth is flat, and then on discovering that it's round, saying who knows, maybe it has the topology of a Klein bottle. There's a surprise in a given direction, but once you've assimilated it, there may not be any further surprise in that same direction.
Last chapter, we talked about whether quantum states should be thought of as exponentially long vectors, and I brought up class BQP/qpoly and concepts like quantum advice. Actually, I’d say that the main reason why I care is something I didn't mention last time, which is that it relates to whether we should expect quantum computing to be fundamentally possible or not. There are people, like Leonid Levin and Oded Goldreich, who just take it as obvious that quantum computing must be impossible. Part of their argument is that it's extravagant to imagine a world where describing the state of 200 particles takes more bits then there are particles in the universe. To them, this is a clear indication something is going to break down. So part of the reason that I like to study the power of quantum proofs and quantum advice is that it helps us answer the question of whether we really should think of a quantum state as encoding an exponential amount of information. So, on to the Eleven Objections. Works on paper, not in practice. Violates Extended Church–Turing Thesis. Not enough “real physics.” Small amplitudes are unphysical. Exponentially large states are unphysical. Quantum computers are just souped-up analog computers. Quantum computers aren't like anything we've ever seen before. Quantum mechanics is just an approximation to some deeper theory. Decoherence will always be worse than the fault-tolerance threshold. We don't need fault-tolerance for classical computers. Errors aren't independent. What I did is to write out every skeptical argument against the possibility of quantum computing that I could think of. We'll just go through them, and make commentary along the way. Let me just start by saying that my point of view has always been rather simple: it's entirely conceivable that quantum computing is impossible for some fundamental reason. If so, then that's by far the most exciting thing that could happen for us. That would be much more interesting than if quantum computing were possible, because it changes our understanding of physics. To have a quantum computer capable of factoring 10000-digit integers is the relatively boring outcome – the outcome that we'd expect based on the theories we already have.
If you have a restless intellect, it is very likely that you have played at some point with the idea of investigating the meaning and conceptual foundations of quantum mechanics. It is also probable (albeit not certain) that your intentions have been stopped on their tracks by an encounter with some version of the "Shut up and calculate" command. You may have heard that everything is already understood. That understanding is not your job. Or, if it is, it is either impossible or very difficult. Maybe somebody explained to you that physics is concerned with "hows" and not with "whys"; that whys are the business of "philosophy" ---you know, that dirty word. That what you call "understanding" is just being Newtonian; which of course you cannot ask quantum mechanics to be. Perhaps they also added some norms: The important thing a theory must do is predict; a theory must only talk about measurable quantities. It may also be the case that you almost asked "OK, and why is that?", but you finally bit your tongue. If you persisted in your intentions and the debate got a little heated up, it is even possible that it was suggested that you suffered of some type of moral or epistemic weakness that tend to disappear as you grow up. Maybe you received some job advice such as "Don't work in that if you ever want to own a house". I have certainly met all these objections in my short career, and I think that they are all just wrong. In this somewhat personal document, I try to defend that making sense of quantum mechanics is an exciting, challenging, important and open scientific endeavor. I do this by compulsively quoting Feynman (and others), and I provide some arguments that you might want to use the next time you confront the mentioned "opinions". By analogy with the anti-rationalistic Copenhagen command, all the arguments are subsumed in a standard answer to it: "Shut up and let me think"
Fifteen years ago, I mused in a Reference Frame column on how different generations of physicists differed in the degree to which they thought that the interpretation of quantum mechanics remains a serious problem. I declared myself to be among those who feel uncomfortable when asked to articulate what we really think about the quantum theory, adding that “If I were forced to sum up in one sentence what the Copenhagen interpretation says to me, it would be ‘Shut up and calculate!’” In the intervening years, I've come to hold a milder and more nuanced opinion of the Copenhagen view, but that should be the subject of another column. The subject of this one is the habit of misquotation or misattribution that afflicts our profession, a rather different example of which I pointed out a few months ago. Given my capacity for intellectual development (“inconsistency,” in the terminology deployed in the current American political season), it's fortunate that I've now reached an age at which I tend to forget about things I've written more than a few years ago. Indeed, I find it downright irritating when somebody asks me questions about papers I wrote a mere half dozen years ago, naively identifying me with the author of those ancient texts. Until quite recently, I had no memory of ever having written such a childishly brusque dismissal of such an exquisitely subtle point of view, much less of having published it in so widely read a venue. This amnesia, combined with the evolution in my thinking that had distanced me from my long-forgotten words, may explain why I was initially somewhat puzzled by the slight sensation of discomfort that passed over me when, browsing the e-print archive earlier this year, I read a characterization of Max Born's probability rule as “the favorite ingredient of what has been nicknamed, after Feynman's famous dictum, the shut up and calculate interpretation of quantum mechanics.” I yield to nobody in my admiration for Richard Feynman's aphorisms on the nature of quantum mechanics. Indeed, long ago I published a poem consisting of nothing more than a resetting as verse of a paragraph Feynman had written about his own attitude toward the quantum theory, in his now (but not then) famous article that launched the whole field of quantum computation. I like to think I have devoured everything Feynman ever wrote on the character of quantum mechanics.
Alright, so now we've got this beautiful theory of quantum mechanics, and the possibly-even-more-beautiful theory of computational complexity. Clearly, with two theories this beautiful, you can't just let them stay single – you have to set them up, see if they hit it off, etc. And that brings us to the class BQP : Bounded-Error Quantum Polynomial-Time. We talked in Chapter 7 about BPP , or Bounded-Error Probabilistic Polynomial-Time. Informally, BPP is the class of computational problems that are efficiently solvable in the physical world if classical physics is true. Now we ask, what problems are efficiently solvable in the physical world if (as seems more likely) quantum physics is true? To me it’s sort of astounding that it took until the 1990s for anyone to really seriously ask this question, given that all the tools for asking it were in place by the 1960s or even earlier. It makes you wonder, what similarly obvious questions are there today that no one’s asking?
In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.