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

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### 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

actually algorithm Alice and Bob Alright amplitudes answer argument assume assumption axioms basic black hole Boolean BPPpath BQP/qpoly called chapter circuit lower bounds classical computer coin complexity classes complexity theory computational complexity computer science cosmological constant CTCs derandomize encode entropy event horizon example exists finite function give given going Grandfather Paradox halting halting problem hard Hawking radiation hidden-variable theory hypothesis input integers interactive proof intuition least matrix measurement NP-complete oracle outcome output P/poly physicists physics polynomial hierarchy polynomial-size polynomial-time possible PostBQP postselection predict probabilistic protocol prove pseudorandom PSPACE quantum advice quantum computing quantum mechanics qubits question random bits real numbers result sample Scott seems simulate solvable solve NP-complete problems sort space string Student superoperator suppose talking tell Theorem there’s things tion Turing machine unitary universe variables vector verifier what’s