COS 576          Fall 2004 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: Wed. Nov. 17: Dr. Constantin Brif: Implementation of Quantum computing and multi-level encoding of qubits Fri. Nov. 19: Prof. Ron Weiss: Computation using living cells Wed. Dec. 8: Prof. Michael Berry: Neural computation in the retina

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

---

Topics and Recommended Reading (continually updated)

Part I: 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]
• Complexity of analog computation [Vergis, Steiglitz, and Dickinson 1986]

Part II: 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 III: Quantum computing (Implementation)

• Chapter 7 of [Nielson and Chuang 2002]

Part IV: 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]