Quantum Computing and the Nature of Computation

With the increasing miniaturization inherent in Moore's law, computation must inevitably approach the limit where classical physics gives way to quantum mechanics. Over the last decade, the field of quantum computation has demonstrated that this cross-over has a dramatic impact on fundamental notions in computation: the modified Church-Turing thesis - one of the underpinings of computational complexity theory - is violated, prime factorization can be carried out efficiently thus rendering cryptosystems such as RSA unsafe, and certain communication protocols can be speeded up exponentially. In this lecture I will describe these developments and sketch our current understanding of the power and limits of quantum computation.