Prerequisite courses: Probability, Computation Theory. Familiarity with linear algebra is an asset, but necessary elements will be reviewed.

Not examinable in 2005-6.

Aims

The aims of the course are to introduce students to the basics of
the quantum model of computation. The model will be used to study
algorithms for phase estimation and the hidden subgroup problem
(factorising integers) and amplitude
amplification (searching).

Lectures

Preliminaries/linear algebra review I.
Motivation, qubits, measurement,

Preliminaries/linear algebra review II.
quantum gates and networks.

Algorithms III.
Factoring , breaking the RSA cryptosystem, discrete logarithm problem
(El Gamal cryptosystem).

Algorithms IV.
Simon's problem, hidden subgroup problem.

Algorithms V.
Quantum searching and counting.

Objectives

At the end of the course students should

understand the basics of the quantum model of computation

know some interesting applications of quantum information processing

be familiar with the most important quantum algorithms and their
analysis

Recommended reading

Nielsen, M.A. & Chuang, I.L. (2000). Quantum computation and quantum information. Cambridge University Press.
Mosca, M. (1999). Quantum computer algorithms; D. Phil. Thesis; available at http://www.cacr.math.uwaterloo.ca/ mmosca/moscathesis.ps