Quantum Computation

Lecturer: Richard Jozsa
Michaelmas Term 2016, 16 lectures, Tuesdays and Thursdays at 9am in MR9

Quantum mechanical processes can be exploited to provide new modes of information processing that are beyond the capabilities of any classical computer. This leads to remarkable new kinds of algorithms (so-called quantum algorithms) that can offer a dramatically increased efficiency for the execution of some computational tasks. Notable examples include integer factorisation (and consequent efficient breaking of commonly used public key cryptosystems) and database searching. Apart from such practical benefits the study of quantum computation has great theoretical interest, combining concepts from computational complexity theory and quantum physics to provide striking fundamental insights into the nature of both disciplines.

The course will cover the following topics:

Notion of qubits, quantum logic gates, circuit model of quantum computation.
Basic notions of quantum computational complexity, oracles, query complexity.

Exposition of principal quantum algorithms including:
the quantum Fourier transform, the Deutsch-Jozsa algorithm,
Shor's factoring algorithm, the hidden subgroup problem,
Grover's searching algorithm, amplitude amplification.

Then a selection from the following further topics (or others):
Quantum teleportation and the measurement-based model of quantum computation;
Lower bounds on quantum query complexity;
Applications of phase estimation in quantum algorithms;
Local hamiltonians and quantum simulation.

Prerequisites and Desirable Previous Knowledge
The following will be assumed as prerequisites for this course:

a basic knowledge of linear algebra and Dirac bra-ket notation;
a basic knowledge of the postulates of quantum mechanics especially in the simple context of finite dimensional state spaces (state vectors, composite systems, unitary matrices, Born rule for quantum measurements).

Prerequisite notes are provided in the course materials below, giving an account of the necessary material.
It would be desirable for you to look through these prerequisite notes at (or slightly before) the start of the course.

Any encounter with basic ideas of classical theoretical computer science (complexity theory) would be helpful but is not essential.

Reading to complement course material

Nielsen, M. and Chuang, I., Quantum Computation and Quantum Information.
Cambridge University Press, 2000.

John Preskill's lecture notes on quantum information theory (especially chapter 6), available at

Kaye, P., Laflamme, R. and Mosca, M. An Introduction to Quantum Computing. OUP, 2007.

Example classes:
Instructor: Richard Jozsa

First example sheet class: Wednesday 2 November, 4pm in MR9
Second example sheet class: Wednesday 23 November, 2pm in MR9
Third example sheet class: Friday 27 January 2017, 2pm in MR9
Easter term revision class: tba

Course materials:
All course materials for 2016 are downloadable from the links below.

Updates diary:

Tues 18 Oct 2016:
Exercise Sheet 1 has been replaced with an updated 2016 version. It contains two new questions at the start. Also two questions on Shor's algorithm (from near the end) have been moved on to Sheet 2. All else remains the same.
Exercise Sheet 2 has been replaced with an updated 2016 version, containing the two Shor algorithm questions (from previous Sheet 1) and all else remains the same.

Mon 21 Nov 2016:
Uploaded updated version of Exercise Sheet 3 (same as previously with some minor rewording and omissions).

Saturday 26 Nov 2016:
Uploaded guide to examinable material for the exam in June 2017.

QCPrerequisites.pdf203.39 KB
QCLectures_1to10.pdf401.76 KB
HiddenSubGp1.pdf173.81 KB
HiddenSubGp2.pdf475.57 KB
AmplAmpl.pdf798.57 KB
MmtQC_Part1.pdf1.96 MB
MmtQC_Part2.pdf1.85 MB
PhaseEst.pdf1.39 MB
HamSim.pdf1.43 MB
QC ExSheet1_2016.pdf173.59 KB
QC ExSheet2_2016.pdf174.99 KB
QC ExSheet3_2016.pdf166.02 KB
AMsuppnotes.pdf431.56 KB
QCexamguide 2016.pdf69.82 KB