COS 576          Fall 2006 N O N S T A N D A R D C O M P U T A T I O N Exploring the physical limits of computation and nonstandard ways to compute. Topics include: Reversible computation, conservative logic, Maxwell's Demon, the thermodynamics of computing and the essential cost of erasure, the complexity of analog computing, Physical Church's Thesis, quantum computing algorithms, cellular automata... Computation with: Billiard balls, cellular automata, lattice gasses, optical solitons, photons, quantum mechanical systems, chemical systems, DNA, biological cells... Students will be encouraged to pursue topics that particularly interest them. Undergraduates and visitors welcome.

Ken Steiglitz ken@cs.princeton.edu Schedule: 3:00-4:20 Monday and Wednesday Room 102, CS Building Guest Lecturers: Constantin Brif, October 23, "Robustness of quantum computing to control errors" William F. Brinkman November 8 "Implementation of quantum computing: superconductors and spins in semiconductors (GaAs and Si)" Steve Lyon November 15 "Implementation of quantum computing: trapped ions, atoms, and electrons on helium" Ron Weiss December 7 (class moved from Dec. 6) "Synthetic Biology and genetic computing"

Papers, Books, and Links: Foundations Reversible Cellular Aut. Quantum DNA Molecular Bio. Cells Analog General Books on Reserve Assignments Term paper report schedule

---

Topics and Recommended Reading (continually updated)

Part I: Quantum computing (Theory)

• General text and reference   [Nielson and Chuang 2002];
  click here for Table of Contents, errata, and free sample;
• Single-particle intererence, a local probabilistic classical computer (probabilistic TM) can't simulate quantum mechanics
  (Feynman really is a genius)   [Feynman 1982]
• Further introduction to and background for quantum mechanics   [Mermin 2002]
• Photons, quibits, entangled states, no-cloning theorem
• A very simple problem with a fast quantum solution   [Deutsch and Jozsa 1992]
• Secure key distribution, superdense coding, quantum teleportation
• A quantum game  [Meyer 1999]
• Shor's Quantum Fourier Transform and application to factoring
• Grover's quantum search algorithm

Part II: Foundations

• Moore's Law   [Moore 1965],   [Keyes 1988]
• Reversible computing, preview   [Bennett 1988]
• Conservative logic   [Fredkin and Toffoli 1982]
• Heat generation in computation   [Landauer 1961]
• Reversible computing   [Bennett 1973]
• Thermodynamics of computation   [Bennett 1982]

Part III: Analog computing

• Complexity of analog computation [Vergis, Steiglitz, and Dickinson 1986]

Part IV: Quantum computing (Implementation)

• Chapter 7 of [Nielson and Chuang 2002], [DiVincenzo 2004]

Part V: Cellular Automata and Embedded Computation

• Origins, Wolfram's statistical mechanics of CAs, universality results [Wolfram (ed.) 1986]
• Computing with physical solitons, the Manakov system, polarization state, universality, bistability  [Jakubowski, Steiglitz, Squier 2001], [Rand, Steiglitz, Prucnal 2005]