Computing and the laws of physics

This document is http://www.neci.nj.nec.com/homepages/wds/pu-course.html

This is the home page for a seminar series of this title that Warren D. Smith (NECI) will organize in the Program of Applied and Computational Mathematics at Princeton University in the fall semester of 1998-9 school year.

Suitable for:

Computer science, math, applied math, and/or physics grad students, or advanced undergrads.

50-word description:

What do computer science and information theory have to say about the laws of physics? How do the laws of physics impose fundamental limits on computer performance - or allow greater performance than might be expected? Church's thesis, Information/Entropy, computing with unreliable computational elements, VLSI theory, quantum computing, Josephson junctions.

Philosophical statement:

The ultimate goal of research in this area is to be able to answer problems like this:

Given a computational problem. (Example: sorting some numbers with total number of bits N.) Given some laws of physics as ground rules. Given a computer made of mass M, occupying volume V, supplied with power P. Tell me: how quickly (upper and lower bounds) can that problem be solved by such a computer? Can it be solved at all? And I'm not talking about bounds like O(NlogN), I'm talking about nailing down all the constant factors that computer scientists like to leave hidden in the O's, in terms of fundamental physical constants of nature.

Related issue: how "useful" and "good" are physical theories? The more predictive power, and the easier it is computationally, to make those predictions, the more useful a theory is. Computer science offers a way to quantify these notions and compare physical theories. The most basic such question: "is theory X useful at all" is essentially the question of "Church's thesis."

I believe that research in this area will (and already has begun to) lead to new understanding of the fundamentals of physics, as well as computer science. But the impact on actual computer technology will be indirect and/or far off.

If you'd like to know more about this exciting area, come check out the seminar series!

Prerequisites:

Actually, we'll see what kind of students we have and then decide what to do. But, optimally:

Physics: Know what the Schrodinger equation is and have seen it solved for, e.g., the hydrogen atom. Know about spin-1/2, photon modes; what "entropy" and "temperature" are.
CS: Know what a Turing machine is, what the "P=NP" question is about, what "undecidability" is, a liitle about information theory, e.g. have heard of error correcting codes, and some algorithms background, e.g. know how to sort N numbers in O(NlogN) operations.
Math: Calculus, know a little (but not much) about PDEs (partial differential equations) and ODEs (ordinary DEs), and enough linear algebra to know what eigendecompositions, Hermitian matrices, and unitary matrices are.

Reading list of useful books

Homework and term paper

My feelings about rigor

Schedule; list of possible lectures

Huger list of possible topics (disorganized. Includes hyperlinks to some papers.)

Email announcement of course

Homework problem sets:

Lectures (including hyperlinks to postscript files)

Lecture (Sept 22): Introduction to computer science. Also recommend reading: C.H.Bennett: Logical depth and physical complexity, pp. 207-235 in The universal Turing machine, a half-century survey, (ed. R.Herken) Springer 1995 (2nd ed.). (Will hand out hardcopies in class.)
Lecture (Sept 25): Church's thesis meets the (Newtonian) N-body problem. (figure)
Lecture (Sept 29): Reversible computing. and A note about zero Lyapunov exponent. Also recommend reading: C.H.Bennett:
Lecture (Oct 2): Computational power of machines made of rigid parts. Supplementary table.
Lecture (Oct 6): (homework 1 due!) Notes on quantum mechanics I. A too-large list of more good things to try to read...: D. Bohm: A suggested interpretation of the quantum theory in terms of hidden variables, I: Phys. Rev. 85 (1952) 166-179, II: 180-193 R.P. Feynman: Space-time approach to nonrelativistic quantum mechanics, Rev. Mod. Phys. 20 (1948) 367-387 (321-341 in Schwinger reprint volume) R.P. Feynman and Frank Vernon: The theory of a general quantum system interacting with a linear dissipative system, Annals of Physics 24 (1963) 118-173 Edward Nelson: Derivation of the Schr\"odinger equation from Newtonian mechanics, Phys.Rev. 150,4 (Oct 1966) 1079-1085. Jose E. Moyal: Quantum mechanics as a statistical theory, Proc. Cambridge Philos. Soc. 45 (1949) 99-124 Wojciech H. Zurek: Decoherence and the transition from quantum to classical, Physics Today (October 1991) 36-44. See also the Letters section, pages 13-15 and 81-90 of the April 1993 issue. A followup paper is: Prefered states, predictability, classicality, and the environment-induced decoherence, Progr. Theor. Physics 89,2 (Feb 1993) 281-312
(Oct 9): Presentations of solutions to homework! (Hopefully by students!) Maybe more quantum...
(Oct 13): sketches of QED, decoherence. Notes on quantum mechanics II.
(Oct 16): Energy-time uncertainty principle. Bounds on memory capacity. Cloak of Invisibility? Bounds on information flux
(Oct 20): continuation of Oct 16 lecture
(Oct 23): Homework answers. Maybe begin survey of VLSI theory.

Random stuff

Email

Feel free to provide feedback at any time via email to "wds@research.NJ.NEC.COM". (Gutless? There are anonymous remailers 1, 2, 3, 4 on the net...) If you want to receive email from me about the course, tell me so via email and I'll put you on the e-mail list!

Schedule and room

Organizational meeting Friday Sept. 18 at 3PM in 401 Fine Hall. Schedule: lectures Tuesdays 4-5:30 and Fridays 3-4:30. The room is Fine 401 for now, although we are looking into changing to a larger room.

My office

Visitors office, 2nd floor of Fine Hall in applied math office area on left. Has yellow class poster on door.