COS 576 - Papers, Books, & Links

Foundations and Limits

 J. D. Bekenstein, "Energy Cost of Information Transfer", Phys. Rev. Lett., vol. 46, no. 10, pp. 623-626, March 9, 1981.

C. H. Bennett, "Logical Reversibility of Computation", IBM J. of Res. and Develop., vol. 17, pp. 525-532, November, 1973.

C. H. Bennett, "The Thermodynamics of Computation - A Review", Int. J. Theoretical Physics, vol. 21, no. 12, pp. 905-940, December, 1982.

C. H. Bennett, "Notes on the History of Reversible Computation", IBM Journal of Res. and Develop., vol. 32, no. 1, pp. 16-23, January 1988.

C. H. Bennett, "Notes on Landauer's Principle, Reversible Computation, and Maxwell's Demon", Studies in History and Philosophy of Modern Physics, vol 34, pp. 501-510, 2003.

D. Deutsch, "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer", Proc. Royal Society of London, Series A: Mathematical and Physical Sciences, vol. 400, no. 1818, pp. 97-117, Jul. 8, 1985.

D. Deutsch, "Is There a Fundamental Bound on the Rate at Which Information Can Be Processed?", Phys. Rev. Lett., vol. 48, no. 4, pp. 286-288, Jan. 25, 1982.

R. P. Feynman, "Simulating Physics with Computers", Int. J. Theor. Physics, vol 21, no. 6/7, pp. 467-488, 1982.

(On reserve) R. P. Feynman, Feynman and computation : exploring the limits of computers, (Anthony J.G. Hey, ed.), Westview Press, Reading, MA, 2002.

E. Fredkin and T. Toffoli, "Conservative logic", Int. J. of Theor. Phys., vol. 21, pp. 219-253, 1982.

R. W. Keyes, "Miniaturization of Electronics and its Limits", IBM J. Res. Develop., vol. 32, pp. 24-28, 1988.

R. Landauer, "Irreversibility and heat generation in the computing process", IBM J. Res. Develop., pp. 183-191, July 1961.

(On reserve) H. S. Leff and A. F. Rex (eds.), Mawell's Demon: Entropy, Information, Computing, Princeton University Press, Princeton, 1990.

S. Lloyd, V. Giovannetti, and L. Maccone, "Physical Limits to Communication", Phys. Rev. Lett., vol. 93, no. 10, Sept. 3, 2004, 100501.

D. A. Meyer, "Quantum Strategies," PRL, 82 1052 (1999).

G. E. Moore, "Cramming more components onto integrated circuits", Electronics, vol. 38, no. 8, April 19, 1965.

M. C. Parker and S. D. Walker, "Information transfer and Landauer's principle", Optics Communications, vol. 229, pp. 23-27, 2004.

E. A. Poe, "Maelzel's Chess-Player," Southern Literary Journal, April 1836; Edgar Allan Poe's anticipation of the Turing Machine in his discussion of the calculating machine of Mr. Babbage.

A. Vergis, K. Steiglitz, and B. Dickinson, "The Complexity of Analog Computation", Mathematics and computers in simulation, vol. 28, pp. 91-113, 1986.

A. C-C. Yao, "Classical Physics and the Church-Turing Thesis", J. ACM, vol. 50, no. 1, pp. 100-105, 2003. W. H. Zurek, "Reversibility and stability of information processing systems", Phys. Rev. Lett., vol. 53, no. 4, pp. 391-394, July 23, 1984.

Reversible Computing: Controversy

W. Porod, R. O. Grondin, D. K. ferry, G. Porod, "Dissipation in computation," Phys. Rev. Lett., vol. 52, no. 3, pp. 232-235, 16 Jan. 1984.

A. L. Robinson, "Computing without dissipating energy," Science, vol. 223, pp. 1164-1166, 16 March 1984.

C. J. Bennett, "Thermodynamically reversible computation", Phys. Rev. Lett., vol. 53, no. 12, p. 1202, 17 Sept. 1984.

P. Benioff, "Comment on 'Dissipation in computation'," Phys. Rev. Lett., vol. 53, no. 12, p. 1203, 17 Sept. 1984.

T. Toffoli, "Comment on 'Dissipation in computation'," Phys. Rev. Lett., vol. 53, no. 12, p. 1204, 17 Sept. 1984.

R. Landauer, "Dissipation in computation," Phys. Rev. Lett., vol. 53, no. 12, p. 1205, 17 Sept. 1984.

Cellular Automata and Embedded Computation

(On reserve) A. Adamatzky, Computing in nonlinear media and automata collectives, Bristol; Philadelphia: Institute of Physics, 2001.

(On reserve) A. Adamatzky, Collision-Based Computing, Springer-Verlag, London, 2002. (Ordered for reserve)

D. Farmer, T. Toffoli, and S. Wolfram (eds.), "Cellular Automata", Proceedings of an Interdisciplinary Workshop, Los Alamos, NM, March 7-11, 1983, North-Holland, Amsterdam.

B. Fuchssteiner, "Filter automata admitting oscillating carrier waves", Appl. Math. Lett., vol. 4, no. 6, pp. 23-26, 1991.

M. H. Jakubowski, K. Steiglitz, and R. K. Squier, "Computing with solitons: A review and prospectus", Multiple-Valued Logic, vol. 6, nos. 5-6, pp. 439-462, 2001.

M. Land and R. K. Belew, "No Perfect Two-State Cellular Automata for Density Classification Exists", Phys. Rev. Lett., vol. 74, no. 25, pp. 5148-5150, 19 June 1995.

Melanie Mitchell's papers

D. Rand, K. Steiglitz, and P. R. Prucnal, "Signal standardization in collision-based soliton computing," Int. J. of Unconventional Computing, vol. 1, pp. 31-45, 2005.

K. Steiglitz, "Time-gated Manakov spatial solitons are computationally universal", Phys. Rev. E, vol. 63, 16608, January 2001.

K. Steiglitz, "Multistable collision cycles of Manakov spatial solitons", Phys. Rev. E, vol. 63, 46607, April 2001.

K. Steiglitz, Lecture notes, 2001 Complex Systems Summer School, Santa Fe Institute, Santa Fe, NM, June 2001. Click here for six-on-a-page version. Santa Fe, NM, June 2001. Click here for one-on-a-page version.

T. Tokihiro, D. Takahashi, J. Matsukidaira, and J. Satsuma, "From Soliton Equations to Integrable Celluar Automata through a Limiting Procedure," Phys. Rev. Lett., vol. 76, no. 18, pp. 3247-3250, April 29, 1996.

T. Toffoli and N. Margolis, Cellular Automata Machines: A New Environment for Modeling, MIT Press, Cambridge MA, 1987.

S. Wolfram (ed.), Theory and Applications of Cellular Automata, World Scientific Publishing Co., Hong Kong (distributed by Taylor and Francis, Philadelphia), 1986, pp. 333-342.

(On reserve) S. Wolfram, A new kind of science, Wolfram Media, Champaign, IL, 2002.

At W. Edwin Clark's home page, a web site devoted to reviews of the above (and not without some humor): click here.

Quantum Computing

 D. Aharonov, W. van Dam, J. Kempe, Z. Landau, Seth Lloyd, and O. Regev, "Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation", May 18, 2004, quant-ph/0405098.

S. C. Benjamin, "Schemes for Parallel Quantum Computation Without Local Control of Quibits", April 22, 2001, quant-ph/9909007; Cellular-automata-like implementations of quantum computing.

S. Bose, P.L. Knight, M. Murao, M.B. Plenio, V. Vedral, "Implementations of Quantum Logic: Fundamental and Experimental Limits", Phil.Trans.Roy.Soc.Lond. A356 (1998) 1823. A discussion of the present practicality of cold ions in a linear trap for large scale computation, with negative conclusions.

D. Deutsch and R. Jozsa, "Rapid Solution of Problems by Quantum Computation", Proc. Royal Soc. London A, vol. 439, pp. 553-558, 1992.

D. P. DiVincenzo, "The Physical Implementation of Quantum Computation", April 22, 2001, quant-ph/0002077 (version of July 9, 2004); a good review of possible implementations.

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, "Quantum Computation by Adiabatic Evolution", Jan. 28, 2000, quant-ph/0001106.

N. D. Mermin, "From Cbits to Qbits: Teaching Computer Scientists Quantum Mechanics", July 19, 2002, http://arxiv.org/abs/quant-ph/0207118

E. Rieffel and W. Polak, "An Introduction to Quantum Computing for Non-Physicists", quant-ph/9809016, 2000.

(On reserve) M. A. Nielsen and I. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge UK, 2000.

K. P. Zetie, S. F. Adams, R. M. Tocknell, "How does a Mach-Zehnder interferometer work?" Phys. Educ., vol. 35, no. 1, January 2000, pp. 46-48.

Los Alamos e-print archive, quantum physics

John Preskill's quantum computing class at Caltech

Stanford Quantum Information Group

SICOMP special issue on quantum computability and complexity

Centre for Quantum Computation, University of Oxford; an especially good source of introductions and tutorials.

DNA Computing

 Erik Winfree's work on DNA self-assembly at Cal Tech

Molecular Computing

Cellular Computing

R. Weiss, et al., "Genetic circuit building blocks for Cellular Computation, Communications, and Signal Processing", Natural Computing, vol. 2, pp. 47-84, 2003.

Analog Computers

 News of Wilbur's linear equation solving machine

Doug Coward's Analog Computer Museum, click here

General

Solitons and Particles in Cellular Automata: a Bibliography

Embedded Computation using Solitons and Particles: a Bibliography

American Physical Society

Books on Reserve (Engineering Library)

Author/Artist: Adamatzky, Andrew.  
Title: Computing in nonlinear media and automata collectives / Andrew Adamatzky.  
Published/Created: Bristol ; Philadelphia : Institute of Physics, 2001.  
Physical Description: xiii, 395 p. : ill. ; 24 cm.  
Call Number: QP267.7 .A325 2001  
--------------------------------------------------

Title: Collision-based computing / Andrew Adamatzky, editor. 
Published/Created: London : Springer, 2002. 
Physical description: xxvii, 549 p. : ill. ; 24 cm. 
Call number: QA267.5.C45 C64 2002 
--------------------------------------------------

Author/Artist: Nielsen, Michael A. 1974- 
Title: Quantum computation 
and quantum information / Michael A. Nielsen and Isaac 
L. Chuang. Published/Created: Cambridge ; New York 
: Cambridge University Press, 2000. Physical Description: 
xxv, 676 p. : ill. ; 26 cm. 
Call Number: QA76.889.N54 2000 
--------------------------------------------------

Author/Artist: Wolfram, Stephen. Title: A new kind 
of science / Stephen Wolfram. Published/Created: Champaign, 
IL : Wolfram Media, c2002. Physical Description: xiv, 
1197 p. : iil. ; 25 cm. 
Call Number: QA267.5.C45 W67 2002 
--------------------------------------------------

Title: Maxwell's demon: entropy, information, computing / compiled by 
Harvey S. Leff and Andrew F. Rex. 
Published/Created: Princeton, N.J. : Princeton University Press, 1990. 
Physical description: xii, 349 p. : ill. ; 26 cm. 
Series: Princeton series in physics 
Call number: QC318.M35 M38 1990 
--------------------------------------------------

Title: Feynman and computation : exploring the limits of computers 
 / edited by Anthony J.G. Hey. 
Published/Created: Reading, Mass. : Westview Press, a member of 
the Perseus Books Group, c2002. 
Physical description: xxiii, 438 p. : ill. ; 23 cm. 
Call number: QC52 .F49 2002 
--------------------------------------------------------------------------------
Back to COS 576 front page