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