Chapter 1.
Atoms and empty space
Chapter 2.
set
Chapter 3.
Gödel, Turing, and their comrades
Chapter 4.
Mind and Machine
Chapter 5.
Paleozoic complexity theory
Chapter 6.
P and NP, their comrades
Chapter 7.
randomness
Chapter 8.
Encryption
Chapter 9.
quantum
Chapter 10.
Quantum computing
Chapter 11.
Penrose
Chapter 12.
Loss of connection and hidden variables
Chapter 13.
proof
Chapter 14.
How big is a quantum state?
Chapter 15.
Skepticism about quantum computing
Chapter 16.
learning
Chapter 17.
Interactive proofs, circuit lower bounds, and some topics
Chapter 18.
Playing with the anthropic principle
Chapter 19.
free will
Chapter 20.
time travel
Chapter 21.
Cosmology and Complexity
Chapter 22.
Ask anything

Target audience for this book

It is easily accessible to readers with a background in science or students majoring in physics, computer science, mathematics, or philosophy.

Structure of this book

Chapter 1 goes back as far as possible to the 'beginning' and begins with a story about the ancient Greek philosopher Democritus.
To summarize Democritus's views, as inferred from the records that have survived to the present, all natural phenomena arise primarily through complex interactions among a few kinds of tiny 'atoms' that swirl around in empty space.

Chapters 2 and 3 briefly shift the focus of the discussion and explain mathematics, the most profound knowledge we possess, which does not rely on "unknown facts" about the physical world.
We will begin by examining set theory, logic, and computability theory, which are the areas of mathematics that have been least influenced by physics to date.
In this course, we introduce the great discoveries of Cantor, Frege, Gödel, Turing, Church, and Cohen, which will help you understand the field of mathematical reasoning.
Moreover, in the process of showing why not all areas of mathematics can be reduced to 'certain mechanical procedures', it explains to what extent reduction is possible and what exactly is meant by calling it a 'mechanical procedure'.

Chapter 4 examines the tedious debate over whether the human mind also follows a "regular, mechanical procedure."
Chapter 5 introduces computational complexity theory, a modern cousin of computability theory.
This theory plays an important role in later chapters.
In particular, we will show how computational complexity can be used to transform "deep philosophical mysteries" such as the limits of perception into incredibly difficult mathematical challenges that reflect many of the very things we consider limits of perception.
Mathematical puzzles like these can contain most of what we want to know.
A representative example of this transformation is the P vs. NP problem.
This is explained in Chapter 6.


Chapter 7 introduces various uses of classical randomness in computational complexity as well as other areas as a warm-up for quantum computing.
Chapter 8 introduces the story of how the concept of computational complexity was applied to cryptography theory and applications in the early 1970s, leading to groundbreaking results.
Chapter 9 introduces the author's view that quantum mechanics is a 'generalized theory of probability'.
Chapter 10 introduces the fundamentals of quantum theory of computation, which is the author's field of expertise and was born from the combination of quantum mechanics and computational complexity theory.


Chapter 11 takes time to critique the ideas of Sir Roger Penrose.
Lord Penrose is famous for arguing that the human brain is not just a quantum computer, but a quantum gravitational computer.
So, humans can solve Turing-incomputable problems, and Gödel's incompleteness theorem is presented as the basis for this.
In this process, we will examine whether we can find some truth in Penrose's conjecture.


Chapter 12 examines, one by one, what the author considers to be the core problems with the concepts of quantum mechanics.
The problem is not that the future is indeterministic (though that's okay), but that the past is also indeterministic.
Let's look at two contrasting reactions to this.
One is the most common among physicists, invoking decoherence and the effective arrow of time in the second law of thermodynamics, and the other relies on 'hidden-variable theories' such as Bohm dynamics.
Even if you don't accept the hidden variable theory, I think it raises some very interesting mathematical questions.

Chapter 13 introduces new concepts in mathematical proof (such as probabilistic proof and zero-knowledge proof).
And we apply this to understand the computational complexity of hidden variable theory.
In Chapter 14, we estimate the size of quantum states.
That is, we examine whether it encodes an exponential amount of classical information.
Let us consider this question in relation to the quantum interpretation debate and to recent research in complexity theory on quantum proof and quantum advice.

Chapter 15 examines the skeptical arguments against quantum computing.
Skeptics argue not that building a practical quantum computer is difficult (which everyone agrees is true), but that it is fundamentally impossible for several fundamental reasons.
Chapter 16 introduces Hume's problem of induction.
This leads to a discussion of the latest research findings on quantum learning theory and the learnability of quantum states.

Chapter 17 introduces several innovative results related to classical and quantum versions of interactive proof systems (e.g., IP = PSPACE, QIP = PSPACE), but focuses on non-relativizing circuit lower bounds that may shed light on the P vs. NP problem.
Chapter 18 introduces the famous Anthropic Principle and the Doomsday Argument.
(As expected) it starts from a very philosophical topic and progresses to post-selection quantum computing and PostBQP = PP.

Chapter 19 examines Newcomb's paradox and free will.
This topic continues with an explanation of Conway-Cohen's 'free will theorem' and a method for generating 'Einstein-certified random numbers' using Bell's inequality.
Chapter 20 deals with time travel.
The discussion follows a now familiar pattern, beginning with various philosophical discussions and concluding with a proof that a classical or quantum computer with a closed time-like curve has computational power completely equivalent to PSPACE (interesting counterarguments to this proof are possible, and will be discussed at length).

Chapter 21 introduces cosmology, dark energy, the Bekenstein limit, and the holographic principle.
Of course, all of these topics are discussed from the perspective of what they mean in relation to the limits of computation.
For example, how many bits can be stored or retrieved without using enough energy to create a black hole, and how many operations can be performed on those bits.

Chapter 22 serves as a kind of dessert.
The information presented here is based on the author's answers to questions received from students in the final lecture of the course "Quantum Computing since Democritus."
Covers the failure of quantum mechanics, black holes and fuzzballs, the relevance of oracle results to computational complexity, NP-completeness and creativity, 'super-quantum' correlations, de-randomization of random algorithms, the nature of science, religion, and reason, and why computer science is not a branch of physics.

Author's Note

As recently as 2013, only a very small minority viewed quantum mechanics as a theory of information and probability.
If you pick up any physics book, whether it's a popular book or a textbook, you'll find that (1) modern physics is full of all sorts of seemingly contradictory phenomena, like waves being particles or particles being waves, (2) if you look deeply into it, no one really understands these terms, (3) it takes years of intensive research just to express it mathematically, and (4) ultimately, the atomic viewpoint is not only correct, but it's the only one that matters.

All I want to know is:
Why things don't match my intuition, how to correct my thinking to fit the experimental results, and how to reason about how the real world works without being confused.
I can assure you that no physicist knows how to correct their intuition so that the behavior of subatomic particles doesn't seem crazy.
In fact, there may be no way at all.
The fact that subatomic motion is uniformly random may remain an inconvenient truth.
There is nothing to say other than, “You can find the answer using this formula.”


Fortunately, as evidenced by the research on quantum computing and quantum fundamentals over the past several decades, I believe we can now better explain quantum mechanics than simply dismiss it as an unknown fact.
To be clear from the conclusion, the perspective of this book is as follows.

Quantum mechanics is an elegant generalization of the laws of probability.
It can be seen as a generalization based on complex numbers rather than positive real numbers, with two numbers instead of one.
Applications of quantum mechanics can proceed entirely separately from the study of quantum mechanics itself.
This generalized probability theory can naturally become the foundation for developing a new computational model called the quantum computing model.
This is the very model that challenged the conventional notion of computation as something that could once be known in advance, and that theoretical computer scientists were trying to develop for their own purposes.
This direction may actually have nothing to do with physics.
In short, quantum mechanics emerged a century ago to solve specific problems in physics, but it can now be sufficiently explained from a completely different perspective.
That is, as part of the history of ideas, the limits of perception through mathematics, logic, computer science, and philosophy.

The reason I got into the field of quantum computing was not because I was curious about what quantum computers could do, but because I was curious about how the feasibility of quantum computers would affect how we view the world.
Either a practical quantum computer is feasible and the limits of perception are not what we think, or we cannot build such a computer and will have to modify the principles of quantum mechanics, or we discover a way to effectively simulate quantum mechanics on a classical computer that we have not yet considered.
These three possibilities may sound like rather bizarre conjectures, but at least one of them is true.
So, whatever the outcome, if you plagiarize an advertisement that plagiarizes my lecture notes, you can say, "That's interesting."