Special Topics in Algorithmic Aspects of Quantum Computing

Spring 2003
Course Information

Instructor: Dr. Andreas Klappenecker

Prerequisite

Programming skills and basic linear algebra. You do not need any background in quantum physics.

Course materials

M.A. Nielson, I.L. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000.
A. Yu. Kitaev, A.H. Shen, M.N. Vyalyi: Classical and Quantum Computation, AMS 2002.
We will provide additional lecture notes.

Grading:

Midterm exam: 25%
Final term project: 25%
Assignments: 45%
Culture: 5%

The assignments consist of one little project, which will allow you to build a simulator of a quantum computer, and paper and pencil homeworks.

Course Goals

The course gives an introduction to algorithmic aspects of quantum computing. It will cover the quantum circuit model, basic algorithms, and new design methods for quantum circuits. At the end of the course, you should be familiar with

the quantum circuit model,
basic quantum algorithms covered in the course,
design methods for quantum algorithms,
quantum error control codes and fault-tolerant computations,
some results in quantum complexity theory.

Course Contents

A tentative list of topics that will be covered in the course:

Basic Algorithms of Quantum Computing
Teleportation
Simulation of a Quantum Computer
Factoring and Discrete Logarithms
Search Algorithms
Design Methods for Quantum Algorithms
Quantum Cryptography
Quantum Complexity Theory
Quantum Error Control Codes
Fault-Tolerant Computing

Computer Use

Some materials will be available only on the web. Some announcements will be made by e-mail.