Prerequisite courses: Mathematical Methods for Computer Science or Mathematics for Computation Theory, Computation Theory
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 searching and factorisation. Issues in the complexity
of computation will also be explored.
Lectures
Bits and qubits.
Introduction to quantum states with motivating examples. Comparison
with classical discrete state systems.
Linear algebra.
Review of linear algebra. Vector spaces, linear operators, Dirac
notation.
Quantum mechanics.
Postulates of quantum mechanics. Evolution and measurement.
Entanglement.
Some Applications.
Bell States, Superdense Coding, No-Cloning Theorem, Quantum Teleportation.
Computation and algorithms.
Models of quantum computation. Quantum circuits, finite state
systems, machines and algorithms.
Quantum search.
Grover's search algorithm. Analysis and lower bounds.
Factorisation.
Shor's algorithm for factorising numbers and analysis. Quantum
Fourier transform.
Quantum complexity.
Quantum complexity classes and their relationship to classical
complexity. Comparison with probabilistic computation.
Objectives
At the end of the course students should
understand the quantum model of computation and how it relates
to quantum mechanics
be familiar with some basic quantum algorithms and their
analysis
see how the quantum model relates to classical models of
computation
Recommended books
* Nielsen, M.A. & Chuang, I.L. (2000). Quantum computation and quantum information. Cambridge University Press.
Gruska, J. (1999). Quantum computing. McGraw-Hill (now out of print, but try a library).
Kitaev, A.Y., Shen, A.H. & Vyalyi, M.N. (2002). Classical and quantum computation. AMS.
