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
Sets | 8 |
Minds and machines | 29 |
Paleocomplexity | 44 |
P NP and friends | 54 |
Randomness | 71 |
Crypto | 93 |
18 | 194 |
How big are quantum states? | 200 |
Learning | 228 |
Interactive proofs circuit lower bounds and more | 243 |
Fun with the Anthropic Principle | 267 |
Free will | 290 |
Time travel | 307 |
Cosmology and complexity | 325 |
Ask me anything | 343 |
363 | |
Other editions - View all
Common terms and phrases
able accept actually advice algorithm already answer argument assume assumption basic believe bits black hole bound called certainly chapter circuit classical closed complexity constant course CTCs define distribution don’t efficiently equal error example exists experiment exponentially fact factoring fixed function give given going hand happens hard human idea input interesting it’s kind least look machine means measurement Nature never NP-complete observation obvious oracle output physics pick polynomial positive possible predict principle probability problem proof prove quantum computing quantum mechanics qubits question random reason result rule sample satisfying Scott seems simply simulate solve sort space steps string Student suppose talking tell that’s Theorem theory there’s things true trying Turing universe vector verifier you’re