Computing and the laws of physics
This document is http://www.neci.nj.nec.com/homepages/wds/pucourse.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 19989 school year.
Suitable for:
Computer science, math, applied math, and/or physics grad
students, or advanced undergrads.
50word 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 spin1/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:

Homework #1 (postscript file)

Homework #1 solutions (ps file)

Homework #2 (postscript file)

Homework #2 solutions (ps file)
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. 207235 in
The universal Turing machine,
a halfcentury survey,
(ed. R.Herken)
Springer 1995 (2nd ed.). (Will hand out hardcopies in class.)
 Lecture (Sept 25):
Church's thesis meets the (Newtonian) Nbody 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 toolarge 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) 166179, II: 180193
R.P. Feynman:
Spacetime approach to nonrelativistic quantum mechanics,
Rev. Mod. Phys. 20 (1948) 367387
(321341 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) 118173
Edward Nelson:
Derivation of the Schr\"odinger equation from Newtonian mechanics,
Phys.Rev. 150,4 (Oct 1966) 10791085.
Jose E. Moyal:
Quantum mechanics as a statistical theory,
Proc. Cambridge Philos. Soc. 45 (1949) 99124
Wojciech H. Zurek:
Decoherence and the transition from quantum to classical,
Physics Today (October 1991) 3644.
See also the Letters section, pages 1315 and 8190
of the April 1993 issue. A followup paper is:
Prefered states, predictability, classicality, and the
environmentinduced decoherence,
Progr. Theor. Physics 89,2 (Feb 1993) 281312
 (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):
Energytime 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
 Review of Tipler's book!
 Completeness, Truth, undecidability, and logical
independence, or: what I discovered in the logic swamp!
 Resultants, Discriminants, and the
Groebner basis  ways to solve polynomial systems
 Some useful inequalities
 Lightning tour of algebraic structures
 Bibliography of quantum mechanics/computation related stuff I made in 1995
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
email list!
Schedule and room
Organizational meeting
Friday Sept. 18 at 3PM in 401 Fine Hall.
Schedule: lectures Tuesdays 45:30 and Fridays 34: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.