Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Syllabus - Quantum Computing
Computer Laboratory > Computer Science Syllabus - Quantum Computing

Quantum Computing next up previous contents
Next: Topics in Concurrency Up: Lent Term 2006: Part Previous: Optimising Compilers   Contents


Quantum Computing

Lecturer: Dr L.M. Ioannou

No. of lectures: 8

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, $\ldots$

  • Preliminaries/linear algebra review II. $\ldots$ quantum gates and networks.

  • Cool applications. Entanglement, Bell States, Superdense Coding, No-Cloning Theorem, Quantum Teleportation.

  • Algorithms I. Models of computation, universality, relative phases, eigenvalue kick-back, Deutsch's problem.

  • Algorithms II. Phase estimation, quantum Fourier transform (QFT), eigenvalue estimation, period-finding, order-finding.

  • Algorithms III. Factoring $N=pq$, 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



next up previous contents
Next: Topics in Concurrency Up: Lent Term 2006: Part Previous: Optimising Compilers   Contents
Christine Northeast
Sun Sep 11 15:46:50 BST 2005