In these first few chapters, our aim is to establish a firm grounding so that we can address some fundamental questions regarding information transmission over quantum channels. This area of study has become known as “quantum Shannon theory” in the broader quantum information community, in order to distinguish this topic from other areas of study in quantum information science. In this text, we will use the terms “quantum Shannon theory” and “quantum information theory” somewhat interchangeably. We will begin by briefly overviewing several fundamental aspects of the quantum theory. Our study of the quantum theory, in this chapter and future ones, will be at an abstract level, without giving preference to any particular physical system such as a spin-1/2 particle or a photon. This approach will be more beneficial for the purposes of our study, but, here and there, we will make some reference to actual physical systems to ground us in reality.

You may be wondering, what is quantum Shannon theory and why do we name this area of study as such? In short, quantum Shannon theory is the study of the ultimate capability of noisy physical systems, governed by the laws of quantum mechanics, to preserve information and correlations. Quantum information theorists have chosen the name quantum Shannon theory to honor Claude Shannon, who single-handedly founded the field of classical information theory, with a groundbreaking 1948 paper (Shannon, 1948).

All physical systems register bits of information, whether it be an atom, an electrical current, the location of a billiard ball, or a switch. Information can be classical, quantum, or a hybrid of both, depending on the system. For example, an atom or an electron or a superconducting system can register quantum information because the quantum theory applies to each of these systems, but we can safely argue that the location of a billiard ball registers classical information only. These atoms or electrons or superconducting systems can also register classical bits because it is always possible for a quantum system to register classical bits.

The term information, in the context of information theory, has a precise meaning that is somewhat different from our prior “everyday” experience with it. Recall that the notion of the physical bit refers to the physical representation of a bit, and the information bit is a measure of how much we learn from the outcome of a random experiment. Perhaps the word “surprise” better captures the notion of information as it applies in the context of information theory.

This chapter begins our formal study of classical information. Recall that Chapter 2 overviewed some of the major operational tasks in classical information theory. Here, our approach is somewhat different because our aim is to provide an intuitive understanding of information measures, in terms of the parties who have access to the classical systems.

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?