Introduction: A quantum computer is a computing device that harnesses the strange power of quantum mechanics: it can exist in several states simultaneously and its computation paths can interfere with each other. It can perform some tasks exponentially faster than any classical computer (restricted to the laws of classical physics). For example, a quantum computer can factor an n-bit integer in time polynomial in n, whereas all known classical algorithms require exponential time to do this. It follows that a quantum computer can easily break many public-key cryptosystems, such as RSA. There are, however, quantum public-key cryptosystems based on the uncertainty principle, that are provably secure against any (classical or quantum) attack. Many institutions around the world are experimenting with technologies for implementing quantum information processing devices.

The goal of this course is to present the theoretical computer science aspects of quantum computing, including the design and analysis of quantum algorithms, cryptographic protocols, and various issues in information and complexity theory. The intended audience is people with a strong basic background in algorithms and mathematics at the undergraduate level (no physics background is required).

Topics: Quantum information, quantum algorithms including Shor's quantum factoring algorithm and Grover's quantum searching technique, quantum error correcting codes, quantum cryptography, quantum communication complexity, and quantum computational complexity.

Text: Quantum Computation and Quantum Information, M. Nielsen and I. Chuang (Cambridge, 2000).

Prerequisites: CPSC 413, MATH 211 or 221 (and MATH 311 is highly recommended).

Honours requirements: This course may be substituted for one of CPSC 511, 513, 517 for the Computer Science BSc Honours Program.

Instructor: Richard Cleve (cleve@cpsc.ucalgary.ca). Please contact me if you are interested.

Lecture times: Tues. and Thurs. 3:30-5:00pm.     http://pages.cpsc.ucalgary.ca/~cleve/courses/599.36/