The puzzle from last chapter is known as Hume's Problem of Induction.

Puzzle: If you observe 500 black ravens, what basis do you have for supposing that the next one you observe will also be black?

Many people’s answer would be to apply Bayes’s Theorem. For this to work, though, we need to make some assumption such as that all the ravens are drawn from the same distribution. If we don’t assume that the future resembles the past at all, then it’s very difficult to get anything done. This kind of problem has led to lots of philosophical arguments like the following.

Suppose you see a bunch of emeralds, all of which are green. This would seem to lend support to the hypothesis that all emeralds are green. But then, define the word grue to mean “green before 2050 and blue afterwards.” Then, the evidence equally well supports the hypothesis that all emeralds are grue, not green. This is known as the grue paradox.

If you want to delve even “deeper,” then consider the “gavagai” paradox. Suppose that you’re trying to learn a language, and you’re an anthropologist visiting an Amazon tribe speaking the language. (Alternatively, maybe you’re a baby in the tribe. Either way, suppose you’re trying to learn the language from the tribe.) Then, suppose that some antelope runs by and some tribesman points to it and shouts “gavagai!” It seems reasonable to conclude from this that the word “gavagai” means “antelope” in their language, but how do you know that it doesn’t refer to just the antelope’s horn? Or it could be the name of the specific antelope that ran by. Worse still, it could mean that a specific antelope ran by on some given day of the week! There’s any number of situations that the tribesman could be using the word to refer to, and so we conclude that there is no way to learn the language, even if we spend an infinite amount of time with the tribe.

A Critical Review of Scott Aaronson's Quantum Computing since Democritus by Scott Aaronson

Quantum Computing since Democritus is a candidate for the weirdest book ever to be published by Cambridge University Press. The strangeness starts with the title, which conspicuously fails to explain what this book is about. Is this another textbook on quantum computing – the fashionable field at the intersection of physics, math, and computer science that's been promising the world a new kind of computer for two decades, but has yet to build an actual device that can do anything more impressive than factor 21 into 3 × 7 (with high probability)? If so, then what does this book add to the dozens of others that have already mapped out the fundamentals of quantum computing theory? Is the book, instead, a quixotic attempt to connect quantum computing to ancient history? But what does Democritus, the Greek atomist philosopher, really have to do with the book's content, at least half of which would have been new to scientists of the 1970s, let alone of 300 BC?

Having now read the book, I confess that I’ve had my mind blown, my worldview reshaped, by the author's truly brilliant, original perspectives on everything from quantum computing (as promised in the title) to Gödel's and Turing's theorems to the P versus NP question to the interpretation of quantum mechanics to artificial intelligence to Newcomb's Paradox to the black-hole information loss problem. So, if anyone were perusing this book at a bookstore, or with Amazon's “Look Inside” feature, I would certainly tell that person to buy a copy immediately. I’d also add that the author is extremely handsome.

There are two ways to teach quantum mechanics. The first way – which for most physicists today is still the only way – follows the historical order in which the ideas were discovered. So, you start with classical mechanics and electrodynamics, solving lots of grueling differential equations at every step. Then, you learn about the “blackbody paradox” and various strange experimental results, and the great crisis these things posed for physics. Next, you learn a complicated patchwork of ideas that physicists invented between 1900 and 1926 to try to make the crisis go away. Then, if you're lucky, after years of study, you finally get around to the central conceptual point: that nature is described not by probabilities (which are always nonnegative), but by numbers called amplitudes that can be positive, negative, or even complex.

Look, obviously the physicists had their reasons for teaching quantum mechanics that way, and it works great for a certain kind of student. But the “historical” approach also has disadvantages, which in the quantum information age are becoming increasingly apparent. For example, I’ve had experts in quantum field theory – people who've spent years calculating path integrals of mind-boggling complexity – ask me to explain the Bell inequality to them, or other simple conceptual things like Grover's algorithm. I felt as if Andrew Wiles had asked me to explain the Pythagorean Theorem.

Why have so many great thinkers found quantum mechanics so hard to swallow? To hear some people tell it, the whole source of the trouble is that “God plays dice with the universe” – that, whereas classical mechanics could in principle predict the fall of every sparrow, quantum mechanics gives you only statistical predictions.

Well, you know what? Whoop-de-doo! If indeterminism were the only mystery about quantum mechanics, quantum mechanics wouldn't be mysterious at all. We could imagine, if we liked, that the universe did have a definite state at any time, but that some fundamental principle (besides the obvious practical difficulties) kept us from knowing the whole state. This wouldn't require any serious revision of our worldview. Sure, “God would be throwing dice,” but in such a benign way that not even Einstein could have any real beef with it.

The real trouble in quantum mechanics is not that the future trajectory of a particle is indeterministic – it’s that the past trajectory is also indeterministic! Or more accurately, the very notion of a “trajectory” is undefined, since until you measure, there’s just an evolving wavefunction. And crucially, because of the defining feature of quantum mechanics – interference between positive and negative amplitudes – this wavefunction can’t be seen as merely a product of our ignorance, in the same way that a probability distribution can.

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?

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.

1. Works on paper, not in practice.

2. Violates Extended Church–Turing Thesis.

3. Not enough “real physics.”

4. Small amplitudes are unphysical.

5. Exponentially large states are unphysical.

6. Quantum computers are just souped-up analog computers.

7. Quantum computers aren't like anything we've ever seen before.

8. Quantum mechanics is just an approximation to some deeper theory.

9. Decoherence will always be worse than the fault-tolerance threshold.

10. We don't need fault-tolerance for classical computers.

11. 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.

I'm going to talk about the title question, but first, a little digression. In science, there's this traditional hierarchy where you have biology on top, and chemistry underlies it, and then physics underlies chemistry. If the physicists are in a generous mood, they'll say that math underlies physics. Then, computer science is over somewhere with soil engineering or some other nonscience.

Now, my point of view is a bit different: computer science is what mediates between the physical world and the Platonic world. With that in mind, “computer science” is a bit of a misnomer; maybe it should be called “quantitative epistemology.” It's sort of the study of the capacity of finite beings such as us to learn mathematical truths. I hope I’ve been showing you some of that.

How do we reconcile this with the notion that any actual implementation of a computer must be based on physics? Wouldn’t the order of physics and CS be reversed?

Well, by similar logic one could say that any mathematical proof has to be written on paper, and therefore physics should go below math in the hierarchy. Or one could say that math is basically a field that studies whether particular kinds of Turing machine will halt or not, and so CS is the ground that everything else sits on. Math is then just the special case where the Turing machines enumerate topological spaces or do something else that mathematicians care about. But then, the strange thing is that physics, especially in the form of quantum probability, has lately been seeping down the intellectual hierarchy, contaminating the “lower” levels of math and CS. This is how I’ve always thought about quantum computing: as a case of physics not staying where it’s supposed to in the intellectual hierarchy! If you like, I’m professionally interested in physics precisely to the extent that it seeps down into the “lower” levels, which are supposed to be the least arbitrary ones, and forces me to rethink what I thought I understood about those levels.

We've seen that if we want to make progress in complexity, then we need to talk about asymptotics: not which problems can be solved in 10000 steps, but for which problems can instances of size n be solved in cn2 steps as n goes to infinity? We met TIME(f(n)), the class of all problems solvable in O(f(n)) steps, and SPACE(f(n)), the class of all problems solvable using O(f(n)) bits of memory.

But if we really want to make progress, then it's useful to take an even coarser-grained view: one where we distinguish between polynomial and exponential time, but not between O(n2) and O(n3) time. From this remove, we think of any polynomial bound as “fast,” and any exponential bound as “slow.”

Now, I realize people will immediately object: what if a problem is solvable in polynomial time, but the polynomial is nn50 000? Or what if a problem takes exponential time, but the exponential is 1.000 000 01n? My answer is pragmatic: if cases like that regularly arose in practice, then it would’ve turned out that we were using the wrong abstraction. But so far, it seems like we’re using the right abstraction. Of the big problems solvable in polynomial time – matching, linear programming, primality testing, etc. – most of them really do have practical algorithms. And of the big problems that we think take exponential time – theorem-proving, circuit minimization, etc. – most of them really don't have practical algorithms. So, that’s the empirical skeleton holding up our fat and muscle.