Reading
See also Science Fiction Reading

June 18

• Daniel Hillis, The Pattern on the Stone, Chapters 2-3 (pp. 21--59), Basic Books, 1998.
• Stephen Brown and Jonathan Rose, ``FPGA and CPLD Architectures: A Tutorial,'' in IEEE Design and Test of Computers, Vol. 12, No. 2, Summer 1996, pp. 42-57. PDF
• David J. Eck, The Most Complex Machine, Chapters 1-4 (pp. 1--135), A. K. Peters, 2000. (Eck's course web page)
• Melanie Mitchel, "Computation in Cellular Automata: A Selected Review"

In T. Gramss, S. Bornholdt, M. Gross, M. Mitchell, and T. Pellizzari, Nonstandard Computation, pp. 95--140. Weinheim: VCH Verlagsgesellschaft, 1998. PDF
• Marvin Minsky, "Computation: Finite and Infinite Machines," Chapters 12, 13, 14 (pp. 219--281), Prentice Hall, 1967.

June 19

• André DeHon. Dynamically Programmable Gate Arrays: A Step Toward Increased Computational Density. In Proceedings of the Fourth Canadian Workshop on Field-Programmable Devices, pages 47-54, May 1996. [abstract, paper, and slide links].
• International Technology Roadmap for Silicon, 2001 edition. Roadmap Index. Suggesting Reading: Executive Summary, Process Integration, and Interconnect chapters.

June 20

• Charles E. Leiserson, ``VLSI Theory and Parallel Supercomputing,'' in Proceedings of the 1989 Caltech Decennial VLSI Conference. Also Appears as MIT/LCS/TM-402.
• André DeHon. ``Balancing Interconnect and Computation in a Reconfigurable Computing Array (or, why you don't really want 100% LUT utilization).'' In Proceedings of the International Symposium on Field Programmable Gate Arrays, pages 125--134, February 1999. [abstract, paper, and slide links].
• Minsky, Chapters 6-7 (pp. 117--145).
• CS 129 Lecture Notes on Stack Machines, Yaser Abu-Mostafa and Erik Winfree

June 21

• G. M. Amdahl, G. A. Blaauw, Frederick P. Brooks, Jr., ``Architecture of the IBM System/360'', In IBM Journal of Research and Development, pages 87--101, April 1964.
• Leonid A. Levin, "Fundamentals of Computing," SIGACT News 27(3) 1996. PS  PDF
• CS 129 Lecture Notes on NP-Completeness, Yaser Abu-Mostafa and Erik Winfree.
• Marcus Hutter, "The Fastest and Shortest Algorithm for All Well-Defined Problems,"  International Journal of Foundations of Computer Science, 13:3 (2002) pp. 431--443. PDF

June 24

• Norman Margolus, ``Crystalline Computation,'' Chapter 18 of Feynman and Computation, Perseus Books, 1999. PDF
• Richard Feynman, Feynman Lectures on Computation, Perseus Books, 2000.

June 25

• Norman Margolus, ``Universal CA's based on the collisions of soft spheres,'' to appear in New Constructions in Cellular Automata edited by David Griffeath and Cristopher Moore, 2002. PDF
• H. F. Leff and A. F. Rex, Maxwell's Demon: Entropy, Information, and Computing, Institute of Physics Publishing, 1990.

June 26

• Norman Margolus, ``An Embedded DRAM Architecture for Large-Scale Spatial-Lattice Computations'' in Proceedings fo the 27th Annual International Symposium on Computer Architecture page 149, 2000. PDF
• Norman Margolus, ``An FPGA architecture for DRAM-based systolic computations,'' in Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines, page 2, 1997. PDF
• Marcello Magnasco, ``Szilard's Heat Engine'' in Europhysics Letters, 33(8), pp. 583--588, 1996. PDF
• Marcello Magnasco, ``Chemical Kinetics is Turing Universal'' in Physical Review Letters, 78(6), pp. 1190--1193, 1997. PDF

June 27

• Norman Margolus and Lev Levitin, ``The Maximum Speed of Dynamical Evolution,'' in Physica D, page 188, 1998. PDF
• Norman Margolous, ``Looking at Nature as a Computer,'' in Proceedings of the Workshop on Digital Perpectives, Washington DC, August 2001. PDF
• Gordon Hammes, "Thermodynamics and Kinetics for the Biological Sciences." John Wiley and Sons. 2000. 
• Charles Bennett,  "The Thermodynamics of Computation -- a Review." Int. J. Theor. Phys. 21: 905-940 (1982). PDF
• M. A. Gibson and J. Bruck, "Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels." J. Phys. Chem. A 104:1876-1889 (2000). PDF
• explore the papers collected for CS 191b.

June 28

 

• Thomas F. Knight, Jr., Biobricks Web Site. Paper there on BioBrick standard assembly ideas and initial catalog.
• E. Winfree, F. Liu, Lisa A. Wenzler, and N. C. Seeman, "Design and Self-Assembly of Two-Dimensional DNA Crystals."  Nature 394: 539-544 (1998). PDF
• Paul Rothemund and Erik Winfree, "The Program-Size Complexity of Self-Assembled Squares," STOC 2000.  PDF
• N. Seeman et. al., "New Motifs in DNA Nanotechnology." Nanotechnology 9: 257-273 (1998). PDF
• B. Yurke, A. J. Turberfield, A. P. Mills, Jr., F. G. Simmel, and J. L. Neumann, "A DNA-Fuelled Molecular Machine Made of DNA."  Nature 406: 605-608 (2000). PDF

July 1

• John Von Neuman, ``Proabilistic Logic and the Synthesis of Reliable Organisms from Unreliable Components,'' in Automata Studies edited by Claude Shannon and John McCarthy, 1956. [PDF]
• Nicholas Pippenger, ``Developments in `The Synthesis of Reliable Organisms from Unreliable Components', '' in Proceedings of the Symposia of Pure Mathematics, Volume 50, pp. 311--324, 1990. [PDF]
• Nicholas Pippenger, additional references for reliable organisms, 2002. [JPG]

July 8

• André DeHon. Array-Based Architecture for Molecular Electronics. In Proceedings of the First Workshop on Non-Silicon Computation, February 2002. [abstract, paper, and slide links].

July 11

• A. Ambainis. Quantum query algorithms and lower bounds (A survey). [PS]

July 12

N.B. Hideo has provided a large number of useful references. The numbers at the end note the suggested reading priority of the 4 or 5 papers on each implementation technique. Hideo reccomends you read the three -1 papers (QED-1, ION-1, NMR-1) for the lecture.

• Q. A. Truchette, C. J. Hood, W. Lange, H. Mabuchi, and H. J. Kimble, ``Measurement of Conditional Phase Shifts for Quantum Logic,'' in Physical Review Letters 75(25), pp. 4710--4713, December 18, 1995. [PDF] (QED-1)
• D. Kielpinski, C. Monroe, and D. J. Wineland, ``Architecture for a Large-Scale Ion-Trap Quantum Computer,'' in Nature 417, pp. 709--711, June 13, 2002. [PDF] (ION-1)
• L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, ``Experimental Realization of Shor's Quantum Factoring Algorithm using Nuclear Magnetic Resonance,'' Nature, 414, pp. 883--887, December 2001. [PDF] (NMR-1)
• J. I. Cirac, P. Zoller, H. J. Kimble, and H. Mabuchi, ``Quantum State Transfer and Entanglement Distribution among Distant Nodes in Quantum a Network,'' in Physical Review Letters 78(16), pp. 3221--3224, April 21, 1997. [PDF] (QED-2)
• J. Ye, D. W. Vermooy, and H. J. Kimble, ``Trapping of Single Atoms in Cavity QED,'' in Physical Review Letters 83(24), pp. 4987--4990, December 13, 1999. [PDF] (QED-3)
• T. Pellizzari, S. A. Gardiner, J. I. Cirac, and P. Zoller ``Decoherence, Continuous Observations, and Quantum Computing: A Cavity QED Model,'' in Physical Review Letters 75(21), pp. 3788--3791, November 20, 1995. [PDF] (QED-4)
• C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano, and D. J. Wineland, ``Demonstration of a Fundamental Quantum Logic Gate,'' in Physical Review Letters 75(25), pp. 4714--4717, December 18, 1995. [PDF] (ION-2)
• B. E. King, C. S. Wood, C. J. Myatt, Q. A. Turchette, D. Leibried, W. M. Itano, C. Monroe, and D. J. Wineland, ``Cooling the Collective Motion of Trapped Ions to Initialize a Quantum Register,'' in Physical Review Letters 81(7), pp. 1525--1528, August 17, 1998. [PDF] (ION-3)
• D. J. Wineland, C. Monroe, W. M. Itano, D. Leibried, B. E. King, D. M. Meekhof, ``Experimental Issues in Coherent Quantum-State Manipulation of Trapped Atomic Ions,'' in Journal of Research of the National Institute of Standards and Technology 103(3), pp. 259--328, May-June, 1998. [PDF] (ION-4)
• D. Kielpinski, V. Meyer, M. A. Rowe, C. A. Sackett, W. M. Itano, C. Monroe, and D. J. Wineland, ``A Decoherence-Free Quantum Memory Using Trapped Ions,'' in Science 291, pp. 1013--1015, February 9, 2001. [PDF] (ION-5)
• J. I. Cirac and P. Zoller, ``Quantum Computations with Cold Trapped Ions,'' in Physical Review Letters 74(20), pp. 4091--4094, May 15, 1995. [PDF] (ION-6)
• T. F. Havel, D. G. Cory, S. Lloyd, N. Boulant, E. M. Fortunato, M. A. Pravia, G. Teklermariam, Y. S. Weinstein, A. Battacharyya, and J. Hou, ``Quantum Information Processing by Nuclear Magnetic Resonance Spectroscopy,'' in American Journal of Physics, 70(3), pp. 345--362, March 2002. [PDF] (NMR-2)
• N. C. Menicucci and Carlton M. Caves, ``Local Realistic Model for the Dynamics of Bulk-Ensemble NMR Information Processing,'' in Physical Review Letters 88(16), pp. 167901-1--4, April 22, 2002. [PDF] (NMR-3)
• S. L Braunstein, C. M. Caves, R. Jozsa, N. Linden, S. Popescu, and R. Schack, ``Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing,'' in Physical Review Letters 83(5), pp. 1054--1057, August 2, 1999. [PDF] (NMR-4)
• I. L. Chuang, L. M. K. Vandersypen, X. Zhou, D. W. Leung, and S. Lloyd, ``Experimental Realization of a Quantum Algorithm,'' Nature, 393, pp. 143--146, May 14 1998. [PDF] (NMR-5)
• Peter W. Shor, ``Scheme for reducing decoherence in quantum memory,'' in Phys. Rev. A 52, pp. R2493-2496, 1995.
• A.R. Calderbank and Peter W. Shor, ``Good quantum error-correcting codes exist,'' in Phys. Rev. A 54, pp. 1098-1106, 1996.