Program

Quantum computation is an intellectually challenging and exciting area that touches on the foundations of both computer science and quantum physics. It provides the first credible challenge to the 'modified Church-Turing thesis,' which states that any 'reasonable' model of computation can be efficiently simulated by a probabilistic Turing Machine. Indeed, quantum computers can factorize integers in polynomial time, thus calling into question the security of much of modern cryptography. The breakthroughs in quantum error-correction call into question established wisdom about the stabilization of quantum states, and together with the experimental success in small-scale quantum computation this area has already had a significant impact on quantum physics.Quantum computation and information theory have drawn on a number of mathematical areas, including computational complexity theory, group representation theory, topology and information theory. Moreover, there is every reason to believe that sophisticated mathematics will play a central role in further developments in the field.Invited participants include Andris Ambainis, Michael Ben-Or, Vladimir Buzek, Rusins Freivalds, Daniel Gottesman, Markus Grassl, Lisa Hales, Sean Hallgren, Vivien Kendon, Adrian Kent, Zeph Landau, Debbie Leung, Samuel Lomonaco, Frederic Magniez, Dominic Mayers, Ashwin Nayak, Arun Pati, Sandu Popescu, Daniel Rockmore, Mary Beth Ruskai, Miklos Santha, Leonard Schulman, Ashish Thapliyal, Willem van Dam, and Andreas Winter. Additional participants will be participating for shorter periods. MSRI is grateful for the support of this program by the Office of Naval Research. For another current opportunity in this field, see http://www.aro.army.mil/research/qcbaa02/qcbaa02.pdf.