Quest for the Quantum Computer

Taking readers to the cutting edge of physics, mathematics, and computer science, Julian Brown tells the dramatic story of the groundbreaking efforts to create a fundamentally new kind of computer that would be astronomically more powerful than today’s machines. In 1998, a team of researchers announced they had produced the world’s first quantum computer in a cup of chloroform. In fascinating, fully accessible detail, Brown explains the ideas that led up to this accomplishment and explores the mind-stretching implications of this leap into the bizarre world of quantum physics. “The Quest for the Quantum Computer” is a riveting look at what promises to be one of the most important scientific and technological ideas of the twenty-first century. 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