Quantum Computing Since DemocritusWritten by noted quantum computing theorist Scott Aaronson, this book takes readers on a tour through some of the deepest ideas of maths, computer science and physics. Full of insights, arguments and philosophical perspectives, the book covers an amazing array of topics. Beginning in antiquity with Democritus, it progresses through logic and set theory, computability and complexity theory, quantum computing, cryptography, the information content of quantum states and the interpretation of quantum mechanics. There are also extended discussions about time travel, Newcomb's Paradox, the anthropic principle and the views of Roger Penrose. Aaronson's informal style makes this fascinating book accessible to readers with scientific backgrounds, as well as students and researchers working in physics, computer science, mathematics and philosophy. |
Contents
Atoms and the void | 1 |
Sets | 8 |
Gödel Turing and friends | 18 |
Minds and machines | 29 |
Paleocomplexity | 44 |
P NP and friends | 54 |
Randomness | 71 |
Crypto | 93 |
Proofs | 186 |
How big are quantum states? | 200 |
Skepticism of quantum computing | 217 |
Learning | 228 |
Interactive proofs circuit lower bounds and more | 243 |
Fun with the Anthropic Principle | 266 |
Free will | 290 |
Time travel | 307 |
Other editions - View all
Common terms and phrases
3SAT actually advice Alice and Bob Alright amplitudes answer argument assume assumption axioms basic black hole Boolean called chapter circuit lower bounds classical computer coin complex numbers complexity classes complexity theory computational complexity computer science coNP cosmological constant cryptosystems CTCs decoherence define Democritus derandomize encode entropy event horizon example exists exponentially factoring finite function give given going Grover's algorithm halting problem hard hidden-variable theory hypothesis infinite input integers interactive proof intuition math mathematical matrix means measurement NP-complete oracle output P/poly physicists physics polynomial hierarchy possible PostBQP postselection predict probabilistic probability protocol prove pseudorandom PSPACE quantum computing quantum mechanics qubits queries question random bits real numbers result sample Scott Shor's algorithm simulate solvable solve NP-complete problems sort space string Student suppose talking Theorem there's things Turing machine unitary universe variables vector verifier