Introduction to Quantum Information Processing
CS 667, C&O 681, PHYS 767
Fall 2006

Notes
● Current room is BFG 2125
● Information about the projects, including a list of topics, appears below (updated 06/11/9)
● The written component of your project is due December 15, 2006

Course TA
Sarvagya Upadhyay (supadhya@cs.uwaterloo.ca)
Office hours: Mondays and Fridays 1:00-2:00pm in DC2114

Assignments (worth 60% of the final grade)
Assignment 1 (due October 3)
Assignment 2 (due October 24)
Assignment 3 (due November 7)
Assignment 4 (due November 23)
Assignment 5 (optional, to replace one of the previous four; due December 14)

Projects (worth 40% of the final grade)
Each project consists of a written component and an oral presentation to the class. It should explain and analyze some topic in quantum information processing, selected with the approval of the instructor. Your presentation should be about 30 minutes in length and your written component is not required to be of any particular length, but around 10 pages would be typical (PDF, PS, and Word are acceptable formats). You should explain the topic in your own words, at a level accessible to your classmates.

The written component of your project is due December 15, 2006. It can be submitted by hardcopy or electronically.

List of Possible Project Topics
[ PDF format, Word format ]
Note that you are welcome to pursue a project topic that is not on the list. In any event, you should seek approval from the instructor for your project topic.

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---including Waterloo---are experimenting with technologies for implementing quantum information processing devices. The goal of this course is to present theoretical aspects of quantum computing, including the design and analysis of quantum algorithms, cryptographic protocols, and various issues in information and complexity theory.

Instructor
Richard Cleve (cleve@cs.uwaterloo.ca)

Office Hours
By appointment

Objectives
Quantum Information Processing (QIP) seeks to exploit the quantum features of Nature to provide a qualitatively different and more powerful way of processing information than "classical" physics seems to allow. This course aims to give basic foundation in the field of quantum information processing (often just called "quantum computing"). QIP is a multidisciplinary subject and therefore this course will introduce fundamental concepts in theoretical computer science and physics that will enable students to pursue further study in various aspects of QIP.

Intended Audience
This course is intended for graduate students majoring in CS, C&O or Physics. For students specializing in Quantum Computing or Quantum Information Processing, this is appropriate as a first course from which more advanced/specialized courses may be taken. For students not specializing in these areas, this course may be taken for breadth.

Prerequisites
A solid background in basic linear algebra (a strong performance in MATH 235 or Phys 364&365 should suffice) is necessary. Students will likely encounter at least one subject with which they have very little familiarity; this is expected. Familiarity with theoretical computer science or quantum mechanics will be an asset, though most students will not be familiar with both. The required background in both these areas will be presented in the course.

References
Quantum Computation and Quantum Information, by Nielsen and Chuang (Cambridge University Press)

Outline of Topics
- General introduction to the quantum mechanical framework, including protocols for superdense coding and teleportation.
- Simple quantum algorithms, including the algorithms of Deutsch, Deutsch-Jozsa, and Simon.
- Classical and quantum models of computation, simulations between them, and basic complexity classes.
- Shor's factoring algorithm, including the quantum Fourier transform, and order-finding.
- Grover's search algorithm, including amplitude amplification, and applications to combinatorial search problems.
- Quantum error correction, including Shor's 9-qubit code and Calderbank-Shor-Steane (CSS) codes.
- Physical realizations of quantum information processing devices.
- Introduction to quantum cryptography, including the Bennett-Brassard (BB84) scheme and the bit commitment problem.
- Nonlocal operations and communication complexity.