Julian Brown

Contents

Foreword by David Deutsch

1. Late-Night Quantum Thoughts

Life in Other Universes

The Quantum AI Experiment

Exploring Hilbert Space

The End of Moore?s Law?

From Bill Gates to Quantum Gates

The Hunter-Gatherers Take a Quantum Leap

2. God, the Universe, and the Reversible Computer

The Computer That Just Coasts

Shannon?s Information Theory

The Puzzle of Maxwell?s Demon

Much Ado About kT

Landauer?s Principle

The Reversible Computer

Reversibility and the Laws of Physics

Is the Universe a Computer?

The Fredkin Gate

The Billiard Ball Computer

The God Game

Low-Energy Computing

3. The Logic of the Quantum Conspiracy

Feynman?s U-Turn

Journey Into the Quantum Realm

Strange Correlations

The EPR Puzzle

Designer Hamiltonians

A Matter of Interpretation

The Case for Many Universes

The Universal Quantum Computer

The Turing Principle

4. Quantum Parallelism

The New Paradigm

The Meaning of Superposition

Counting on the Qubits

The Square Root of NOT

Rotations in Quantum Space

Controlled-NOT and the Toffoli Gate

Playing the Markets with a Quantum Computer

Turbocharged Algorithms

Tractability vs. Intractability

The Traveling Salesman Problem

Does P Equal NP?

Consulting the Oracle

5. Code Breaking and the Shor Algorithm

The Problem of Factorization

Secret Codes

Public-Key Cryptography

How Diffie-Hellman Works

The RSA Alogrithm

How RSA Works

Cryptography and the Real World

The Challenge of RSA-129

Factoring by E-Mail

Factorization Takes a Quantum Leap

Heat, Sound, and Fourier Series

Light, Music, and Fourier Transforms

The Quantum FFT

6. Privacy Lost, Privacy Regained

Messages from Across the Quantum Channel

All About Eve

Dial Q for Qubits

Quantum Clones and Counterfeit Coins

How to Send a Quantum Valentine

The Rise and Fall of Quantum Bit Commitment

Cryptography by Entanglement

Quantum Compression

Beam Me Up, Atom by Atom

7. How to Build a Quantum Computer

Going Universal

Two-Bit Processors

The Polymer Machine

The Trouble with Decoherence

Trapping the Atom

Flying Qubits

The Doctors of Spin

How Useful Is NMR Quantum Computation?

Connecting the Quantum Dots

Runners in the Quantum Race

8. Quantum Error Correction and Other Algorithms

Processing in the Dark

Democracy Among the Qubits

Three-Bit Quantum Error Correction

How Does Quantum Error Correction Scale?

Crossing the Error Threshold

Creating the GHZ State

Take a Ride on the Universal Quantum Simulator

Searching a Quantum Phone Directory

Amadeus and the Quantum Complexity Puzzle

The Shape of Quantum Circuits to Come

9. Visions of the Quantum Age

A Quantum Computing Road Map

Nanotechnology and the Singularity

DNA Computing

Clones, Consciousness, and the Indivisible Soul

Quantum Gravity and the Measurement Problem

Is the Brain a Quantum Computer?

Why Is the Universe Comprehensible?

Trading Histories for Universes

Are Decoherent Histories the Answer?

The Quantum Universe and the Omega Point

Appendix A

Appendix B

Appendix C

Appendix D

Appendix E

Appendix F

Appendix G

Appendix H

Notes

Bibliography

Index