Computer Laboratory

Course pages 2017–18

Quantum Computing

Principal lecturer: Prof Anuj Dawar
Taken by: Part II
Past exam questions

No. of lectures: 8
Suggested hours of supervisions: 2
Prerequisite courses: Mathematical Methods for Computer Science, 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 and measurements with motivating examples. Comparison with discrete classical states.

  • Linear algebra. Review of linear algebra: vector spaces, linear operators, Dirac notation, tensor product.

  • Quantum mechanics. Postulates of quantum mechanics. Evolution and measurement. Entanglement.

  • Quantum computation. The model of quantum computation. Quantum gates and circuits. Deutsch-Jozsa algorithm.

  • Some applications. Applications of quantum information: quantum key distribution, superdense coding and quantum teleportation.

  • Quantum search. Grover’s search algorithm: analysis and lower bounds.

  • Factoring. Shor’s algorithm for factoring, its 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 the basic principles of quantum mechanics;

  • be familiar with basic quantum algorithms and their analysis;

  • be familiar with basic quantum protocols such as teleportation and superdense coding;

  • see how the quantum model relates to classical models of deterministic and probabilistic computation.

Recommended reading

Books:

Kaye P., Laflamme R., Mosca M. (2007). An Introduction to Quantum Computing. Oxford University Press.
Nielsen M.A., Chuang I.L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
Mermin N.D. (2007). Quantum Computer Science: An Introduction. Cambridge University Press.
Hirvensalo M. (2001). Quantum Computing. Springer.

Papers:

Braunstein S.L. (2003). Quantum computation tutorial. Available at: https://www-users.cs.york.ac.uk/~schmuel/comp/comp_best.pdf
Aharonov D., Quantum computation [arXiv:quant-ph/9812037]
Steane A., Quantum computing [arXiv:quant-ph/9708022]

Other lecture notes:

Umesh Vazirani (UC Berkeley): http://www-inst.eecs.berkeley.edu/~cs191/sp12/
John Preskill (Caltech): http://www.theory.caltech.edu/people/preskill/ph229/
Andrew Childs (University of Maryland): http://cs.umd.edu/~amchilds/qa/
John Watrous (University of Waterloo): https://cs.uwaterloo.ca/~watrous/TQI/