**Next:**Topics in Concurrency

**Up:**Lent Term 2008: Part

**Previous:**Optimising Compilers

**Contents**

##

Quantum Computing

*Lecturer: Dr A. Dawar*

*No. of lectures:* 8

*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.**Quantum Computation.**Models of quantum computation. Quantum circuits, finite state systems, machines and algorithms.**Some Applications.**Applications of quantum infomation. Bell States, quantum key exchange, quantum teleportation.**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 reading**

* Nielsen, M.A. & Chuang, I.L. (2000). *Quantum computation and quantum information*. Cambridge University Press.

Mermin, N.D. (2007). *Quantum computer science*. 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.

**Next:**Topics in Concurrency

**Up:**Lent Term 2008: Part

**Previous:**Optimising Compilers

**Contents**