Our current research into the Physics of Computation is the continuation of a long and productive train of research that our group has been involved in for over 15 years. This research produced many of the original results on the theory of reversible computation (including reversible cellular automata), and has more recently included pioneering work on lattice gas simulations of physics and results on Quantum Computation.
The thread that ties all of our research together (including our CA work) is an attempt to push the theoretical descriptions that people use to model computation, and those that are used to model physics, closer together: to make models of computation more physical, and to adapt computations to run on these more physical computers.
This has been a very forward looking endeavor: engineers are only now beginning to discuss reversible computing at conferences on low-power computers. Quantum-scale computing devices are only now being attempted in the laboratory. FPGA's are a descendant of CA's that have only recently become popular as computing components.
The recent result by Peter Shor, that a quantum mechanical computer can factor in polynomial time, has stimulated a lot of interest in the Theory of Computation community. The basic idea is that in quantum mechanics, a physical system can be thought of as performing many dynamical evolutions simultaneously, with only the result of one of them being observed at the end-quantum theory predicts the relative probabilities of seeing the various possible outcomes. If each of these dynamical evolutions is a distinct computation, then you have a uniquely quantum form of parallelism. Interference effects can make the probability of seeing the results of certain computations much more likely than others, so that effectively all of the probability can be put, in the case of Shor's algorithm, on states that contain the answer to the factoring problem.
We've been having discussions with researchers around the Lab and around MIT about this topic, aimed at understanding this result better and seeing if we can actually build a Shor-type quantum computer. We also recently had Peter Shor visit here and give a talk on his quantum factoring result, in a joint Physics of Computation and Theory of Computation seminar. Other recent seminar speakers also include:
These talks have all been part of the Physics of Computation Seminar: a series on adapting computers and computations to the constraints of, and opportunities afforded by, microphysics; and on the development and application of the physical theory of computation and information.
Our Quantum Computation and our more theoretical CA researches are funded under ARPA's Ultra project (one of only two theoretical groups funded by this project). One of our physics Ph.D.'s this year was Michael Biafore, who got his degree working on research related to our Quantum Computing activities (thesis title: ``Few Body Cellular Automata: a methodology for extracting useful computation from physical interactions''[]). Mike is now a Post Doc in our group, and he was actually the instigator and driving force behind our application for the Ultra grant which now supports him.
Finally, the Turin (Italy) Workshop on ``Quantum Computation'' that we organized last year (along with Bennett, Penrose, and others) will be held again late this summer. Last year's meeting included all of the major workers in the fields of quantum cryptography and quantum computation, and we expect to have a similar group this year.