We discussed the major noiseless quantum communication protocols such as teleportation, super-dense coding, their coherent versions, and entanglement distribution in detail in Chapters 6, 7,and 8. Each of these protocols relies on the assumption that noiseless resources are available. For example, the entanglement distribution protocol assumes that a noiseless qubit channel is available to generate a noiseless ebit. This idealization allowed us to develop the main principles of the protocols without having to think about more complicated issues, but in practice, the protocols do not work as expected under the presence of noise.

Given that quantum systems suffer noise in practice, we would like to have a way to determine how well a protocol is performing. The simplest way to do so is to compare the output of an ideal protocol to the output of the actual protocol using a distance measure of the two respective output quantum states. That is, suppose that a quantum information-processing protocol should ideally output some quantum state ∣ψ⟩, but the actual output of the protocol is a quantum state with density operator ρ. Then a performance measure P(∣ψ⟩,ρ) should indicate how close the ideal output is to the actual output. Figure 9.1 depicts the comparison of an ideal protocol with another protocol that is noisy.

This chapter introduces two distance measures that allow us to determine how close two quantum states are to each other.

The final chapter of our development of the quantum theory gives perhaps the most powerful viewpoint, by providing a mathematical tool, the purification theorem, which offers a completely different way of thinking about noise in quantum systems. This theorem states that our lack of information about a set of quantum states can be thought of as arising from entanglement with another system to which we do not have access. The system to which we do not have access is known as a purification. In this purified view of the quantum theory, noisy evolution arises from the interaction of a quantum system with its environment. The interaction of a quantum system with its environment leads to correlations between the quantum system and its environment, and this interaction leads to a loss of information because we cannot access the environment. The environment is thus the purification of the output of the noisy quantum channel.

In Chapter 3, we introduced the noiseless quantum theory. The noiseless quantum theory is a useful theory to learn so that we can begin to grasp an intuition for some uniquely quantum behavior, but it is an idealized model of quantum information processing. In Chapter 4, we introduced the noisy quantum theory as a generalization of the noiseless quantum theory. The noisy quantum theory can describe the behavior of imperfect quantum systems that are subject to noise.

This chapter demonstrates the power of both coherent communication from Chapter 7 and the particular protocol for entanglement-assisted classical coding from the previous chapter. Recall that coherent dense coding is a version of the dense coding protocol in which the sender and receiver perform all of its steps coherently. Since our protocol for entanglement-assisted classical coding from the previous chapter is really just a glorified dense coding protocol, the sender and receiver can perform each of its steps coherently, generating a protocol for entanglement-assisted coherent coding. Then, by exploiting the fact that two coherent bits are equivalent to a qubit and an ebit, we obtain a protocol for entanglement-assisted quantum coding that consumes far less entanglement than a naive strategy would in order to accomplish this task. We next combine this entanglement-assisted quantum coding protocol with entanglement distribution (Section 6.2.1) and obtain a protocol for which the channel's coherent information (Section 12.5) is an achievable rate for quantum communication. This sequence of steps demonstrates an alternate proof of the direct part of the quantum channel coding theorem stated in Chapter 23.

Entanglement-assisted classical communication is one generalization of superdense coding, in which the noiseless qubit channel becomes an arbitrary noisy quantum channel while the noiseless ebits remain noiseless. Another generalization of super-dense coding is a protocol named noisy super-dense coding, in which the shared entanglement becomes a shared noisy state ρAB and the noiseless qubit channels remain noiseless.

Now we're going to launch into something I know you've all been waiting for: a philosophical food fight about minds, machines, and intelligence!

First, though, let's finish talking about computability. One concept we'll need again and again in this chapter is that of an oracle. The idea is a pretty obvious one: we assume we have a “black box,” or “oracle,” that immediately solves some hard computational problem, and then see what the consequences are! (When I was a freshman, I once started talking to my professor about the consequences of a hypothetical “NP-completeness fairy”: a being that would instantly tell you whether a given Boolean formula was satisfiable or not. The professor had to correct me: they're not called “fairies”; they're called “oracles.” Much more professional!)

Oracles were apparently first studied by Turing, in his 1938 PhD thesis. Obviously, anyone who could write a whole thesis about these fictitious entities would have to be an extremely pure theorist, someone who wouldn’t be caught dead doing anything relevant. This was certainly true in Turing’s case – indeed, he spent the years after his PhD, from 1939 to 1943, studying certain abstruse symmetry transformations on a 26-letter alphabet.

Anyway, we say that problem A is Turing reducible to problem B, if A is solvable by a Turing machine given an oracle for B. In other words, “A is no harder than B”: if we had a hypothetical device to solve B, then we could also solve A. Two problems are Turing equivalent if each is Turing reducible to the other. So, for example, the problem of whether a statement can be proved from the axioms of set theory is Turing equivalent to the halting problem: if you can solve one, you can solve the other.

We're going to start by beating a retreat from QuantumLand, back onto the safe territory of computational complexity. In particular, we're going to see how, in the 1980s and 1990s, computational complexity theory reinvented the millennia-old concept of mathematical proof – making it probabilistic, interactive, and cryptographic. But then, having fashioned our new pruning-hooks (proving-hooks?), we're going to return to QuantumLand and reap the harvest. In particular, I’ll show you why, if you could see the entire trajectory of a hidden variable, then you could efficiently solve any problem that admits a “statistical zero-knowledge proof protocol,” including problems like Graph Isomorphism for which no efficient quantum algorithm is yet known.

What is a proof?

Historically, mathematicians have had two very different notions of “proof.”

The first is that a proof is something that induces in the audience (or at least the prover!) an intuitive sense of certainty that the result is correct. In this view, a proof is an inner transformative experience – a way for your soul to make contact with the eternal verities of Platonic heaven.

So, in this chapter, we're going to ask – and hopefully answer – this question of whether there's free will or not. If you want to know where I stand, I’ll tell you: I believe in free will. Why? Well, the neurons in my brain just fire in such a way that my mouth opens and I say I have free will. What choice do I have?

Before we start, there are two common misconceptions that we have to get out of the way. The first one is committed by the free will camp, and the second by the anti-free-will camp.

The misconception committed by the free will camp is the one I alluded to before: if there’s no free will, then none of us are responsible for our actions, and hence (for example) the legal system would collapse. Well, I know of only one trial where the determinism of the laws of physics was actually invoked as a legal defense. It’s the Leopold and Loeb trial in 1926. Have you heard of this? It was one of the most famous trials in American history, next to the OJ trial. So, Leopold and Loeb were these brilliant students at the University of Chicago (one of them had just finished his undergrad at 18), and they wanted to prove that they were Nietzschean supermen who were so smart that they could commit the perfect murder and get away with it. So they kidnapped this 14-year-old boy and bludgeoned him to death. And they got caught – Leopold dropped his glasses at the crime scene.

Answers to puzzles from Chapter 7

Puzzle 1. We are given a biased coin that comes up heads with probability p. Using this coin, construct an unbiased coin.

Solution. The solution is the “von Neumann trick”: flip the biased coin twice, interpreting HT as heads and TH as tails. If the flips come up HH or TT, then try again. Under this scheme, “heads” and “tails” are equiprobable, each occurring with probability p(1 - p) in any given trial. Conditioned on either HT or TH occurring, it follows that the simulated coin is unbiased.

Puzzle 2. n people sit in a circle. Each person wears either a red hat or a blue hat, chosen independently and uniformly at random. Each person can see the hats of all the other people, but not his/her own hat. Based only upon what they see, each person votes on whether or not the total number of red hats is odd. Is there a scheme by which the outcome of the vote is correct with probability greater than ½?

Solution. Each person decides his/her vote as follows: if the number of visible blue hats is larger than the number of visible red hats, then vote according to the parity of the number of visible red hats. Otherwise, vote the opposite of the parity of the number of visible red hats. If the number of red hats differs from the number of blue hats by at least 2, then this scheme succeeds with certainty. Otherwise, the scheme might fail. However, the probability that the number of red hats differs from the number of blue hats by less than 2 is small – O(1/√N).

In the last chapter, we talked about the rules for first-order logic. There's an amazing result called Gödel's Completeness Theorem that says that these rules are all you ever need. In other words: if, starting from some set of axioms, you can't derive a contradiction using these rules, then the axioms must have a model (i.e., they must be consistent). Conversely, if the axioms are inconsistent, then the inconsistency can be proved using these rules alone.

Think about what that means. It means that Fermat's Last Theorem, the Poincaré Conjecture, or any other mathematical achievement you care to name can be proved by starting from the axioms for set theory, and then applying these piddling little rules over and over again. Probably 300 million times, but still...

How does Gödel prove the Completeness Theorem? The proof has been described as “extracting semantics from syntax.” We simply cook up objects to order as the axioms request them! And if we ever run into an inconsistency, that can only be because there was an inconsistency in the original axioms.

One immediate consequence of the Completeness Theorem is the Löwenheim–Skolem Theorem: every consistent set of axioms has a model of at most countable cardinality. (Note: One of the best predictors of success in mathematical logic is having an umlaut in your name.) Why? Because the process of cooking up objects to order as the axioms request them can only go on for a countably infinite number of steps!

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.

So why Democritus? First of all, who was Democritus? He was this Ancient Greek dude. He was born around 450 BC in this podunk Greek town called Abdera, where people from Athens said that even the air causes stupidity. He was a disciple of Leucippus, according to my source, which is Wikipedia. He's called a “pre-Socratic,” even though actually he was a contemporary of Socrates. That gives you a sense of how important he's considered: “Yeah, the pre-Socratics – maybe stick ’em in somewhere in the first week of class.” Incidentally, there's a story that Democritus journeyed to Athens to meet Socrates, but then was too shy to introduce himself.

Almost none of Democritus’s writings survive. Some survived into the Middle Ages, but they’re lost now. What we know about him is mostly due to other philosophers, like Aristotle, bringing him up in order to criticize him.

So, what did they criticize? Democritus thought the whole universe is composed of atoms in a void, constantly moving around according to determinate, understandable laws. These atoms can hit each other and bounce off, or they can stick together to make bigger things. They can have different sizes, weights, and shapes – maybe some are spheres, some are cylinders, whatever. On the other hand, Democritus says that properties like color and taste are not intrinsic to atoms, but instead emerge out of the interactions of many atoms. For if the atoms that made up the ocean were “intrinsically blue,” then how could they form the white froth on waves?

Here, we're gonna talk about sets. What will these sets contain? Other sets! Like a bunch of cardboard boxes that you open only to find more cardboard boxes, and so on all the way down.

You might ask “how is this relevant to a book on quantum computing?”

Well, hopefully we’ll see a few answers later. For now, suffice it to say that math is the foundation of all human thought, and set theory – countable, uncountable, etc. – that’s the foundation of math. So regardless of what a book is about, it seems like a fine place to start.

I probably should tell you explicitly that I’m compressing a whole math course into this chapter. On the one hand, that means I don’t really expect you to understand everything. On the other hand, to the extent you do understand – hey! You got a whole math course in one chapter! You’re welcome.

So let’s start with the empty set and see how far we get.

THE EMPTY SET.

Any questions so far?

Actually, before we talk about sets, we need a language for talking about sets. The language that Frege, Russell, and others developed is called first-order logic. It includes Boolean connectives (and, or, not), the equals sign, parentheses, variables, predicates, quantifiers (“there exists” and “for all”) – and that’s about it. I’m told that the physicists have trouble with these. Hey, I’m just ribbin’ ya. If you haven’t seen this way of thinking before, then you haven’t seen it. But maybe, for the benefit of the physicists, let’s go over the basic rules of logic.

In the last chapter, we talked about free will, superintelligent predictors, and Dr. Evil planning to destroy the Earth from his moon base. Now I’d like to talk about a more down-to-earth topic: time travel. The first point I have to make is one that Carl Sagan made: we're all time travelers – at the rate of one second per second! Har har! Moving on, we have to distinguish between time travel into the distant future and into the past. Those are very different.

Travel into the distant future is by far the easier of the two. There are several ways to do it.

• Cryogenically freeze yourself and thaw yourself out later.

• Travel at relativistic speed.

• Go close to a black hole horizon.

This suggests one of my favorite proposals for how to solve NP-complete problems in polynomial time: why not just start your computer working on an NP-complete problem, then board a spaceship traveling at close to the speed of light and return to Earth to pick up the solution? If this idea worked, it would let us solve much more than just NP. It would also let us solve PSPACE-complete and EXP-complete problems – maybe even all computable problems, depending on how much speedup you want to assume is possible. So what are the problems with this approach?

By any objective standard, the theory of computational complexity ranks as one of the greatest intellectual achievements of humankind – along with fire, the wheel, and computability theory. That it isn't taught in high schools is really just an accident of history. In any case, we'll certainly need complexity theory for everything else we're going to do in this book, which is why the next five or six chapters will be devoted to it. So before we dive in, let's step back and pontificate about where we're going.

What I’ve been trying to do is show you the conceptual underpinnings of the universe, before quantum mechanics comes on the scene. The amazing thing about quantum mechanics is that, despite being a grubby empirical discovery, it changes some of the underpinnings! Others it doesn't change, and others it's not so clear whether it changes them or not. But if we want to debate how things are changed by quantum mechanics, then we'd better understand what they looked like before quantum mechanics.

• 1950s: Late Turingzoic

• 1960s: Dawn of the Asymptotic Age

• 1971: The Cook–Levin Asteroid; extinction of the Diagonalosaurs

• Early 1970s: The Karpian Explosion

• 1978: Early Cryptozoic

• 1980s: Randomaceous Era

• 1993: Eruption of Mt Razborudich; extinction of the Combinataurs

• 1994: Invasion of the Quantodactyls

• Mid-1990s to present: Derandomaceous Era

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.

1. 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?

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

This chapter is about Roger Penrose's arguments against the possibility of artificial intelligence, as famously set out in his books The Emperor's New Mind and Shadows of the Mind. It would be strange for a book like this one not to discuss these arguments, since, agree with them or not, they're some of the most prominent landmarks at the intersection of math, CS, physics, and philosophy. The reason we're discussing them now is that we finally have all the prerequisites (computability, complexity, quantum mechanics, and quantum computing).

Penrose's views are complicated: they involve speculations about an “objective collapse” of quantum states, which would arise from an as-yet-undiscovered quantum theory of gravity. Even more controversially, this hypothesized objective collapse would play a role in human intelligence, through its influence on cellular structures called microtubules in the brain.

But what is it that leads Penrose to make these exotic speculations in the first place? The core of Penrose’s thesis is a certain argument purporting to show that human intelligence can’t be algorithmic, for reasons related to Gödel’s Incompleteness Theorem. And therefore, some nonalgorithmic element must be sought in human brain function, and the only plausible source of such an element is new physics (coming, for example, from quantum gravity). The “Gödel argument” itself didn’t originate with Penrose: Gödel himself apparently believed some version of it (though he never published his views), and even in 1950 it was well enough known for Alan Turing to rebut it in his famous paper “Computing machinery and intelligence.” Probably the first detailed presentation of the Gödel argument in print came in 1961, from the philosopher John Lucas. Penrose’s main innovation is that he takes the argument seriously enough to explore, at length, what the universe and our brains would actually need to be like – or better, what they could possibly be like – if the argument were valid. Hence, all the stuff about quantum gravity and microtubules.

Puzzle from last chapter: What can you compute with “narrow” CTCs that only send one bit back in time?

Solution: let x be a chronology-respecting bit, and let y be a CTC bit. Then, set x := x ⊕ y and y := x. Suppose that Pr[x = 1] = p and Pr[y = 1] = q. Then, causal consistency implies p = q. Hence, Pr[x ⊕ y = 1] = p(1 - q) + q(1 - p) = 2p(1 - p).

So we can start with p exponentially small, and then repeatedly amplify it. We can thereby solve NP-complete problems in polynomial time (and indeed PP ones also, provided we have a quantum computer).

I’ll start with the “New York Times model” of cosmology – that is, the thing that you read about in popular articles until fairly recently – which says that everything depends on the density of matter in the universe. There’s this parameter Ω which represents the mass density of the universe, and if it’s greater than unity, the universe is closed. That is, the matter density of the universe is high enough that, after the Big Bang, there has to be a Big Crunch. Furthermore, if Ω > 1, spacetime has a spherical geometry (positive curvature). If Ω = 1, the geometry of spacetime is flat and there’s no Big Crunch. If Ω < 1, then the universe is open, and has a hyperbolic geometry. The view was that these are the three cases.