Department of Computer Science and Technology

Course pages 2020–21 (these pages are still being updated)

Quantum Computing

Principal lecturer: Dr Steven Herbert
Taken by: Part II CST 50%, Part II CST 75%
Past exam questions

No. of lectures: 16
Suggested hours of supervisions: 4
Prerequisite courses: Foundations of Data Science, Computation Theory

Aims

The principal aim of the course is to introduce students to the basics of the quantum model of computation. The model will be used to study algorithms for searching, factorisation and quantum chemistry as well as other important topics in quantum information such as cryptography and super-dense coding. Issues in the complexity of computation will also be explored. A second aim of the course is to introduce student to near-term quantum computing. To this end, error-correction and adiabatic quantum computing are studied.

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, the tensor product.

  • The postulates of quantum mechanics. Postulates of quantum mechanics, incl. evolution and measurement.

  • Important concepts in quantum mechanics. Entanglement, distinguishing orthogonal and non-orthogonal quantum states, no-cloning and no signalling.

  • The quantum circuit model. The circuit model of quantum computation. Quantum gates and circuits. Universality of the quantum circuit model, and efficient simulation of arbitrary two-qubit gates with a standard universal set of gates.

  • Some applications of quantum information. Applications of quantum information (other than quantum computation): quantum key distribution, superdense coding and quantum teleportation.

  • Deutsch-Jozsa algorithm. Introducing Deutsch’s problem and Deutsch’s algorithm leading onto its generalisation, the Deutsch-Jozsa algorithm.

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

  • Quantum Fourier Transform & Quantum Phase Estimation. Definition of the Quantum Fourier Transform (QFT), and efficient representation thereof as a quantum circuit. Application of the QFT to enable Quantum Phase Estimation (QPE).

  • Application 1 of QFT / QPE: Factoring. Shor’s algorithm: reduction of factoring to period finding and then using the QFT for period finding.

  • Application 2 of QFT / QPE: Quantum Chemistry. Efficient simulation of quantum systems, and applications to real-world problems in quantum chemistry.

  • Quantum complexity. Quantum complexity classes and their relationship to classical complexity. Comparison with probabilistic computation.

  • Quantum error correction. Introducing the concept of quantum error correction required for the following lecture on fault-tolerance.

  • Fault tolerant quantum computing. Elements of fault tolerant computing; the threshold theorem for efficient suppression of errors.

  • Adiabatic quantum computing. The quantum adiabatic theorem, and adiabatic optimisation. Quantum annealing and D-Wave.

  • Case studies in near-term quantum computation. Examples of state-of-the-art quantum algorithms and computers, including superconducting and networked quantum computers.

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.

  • appreciate the importance of efficient error-suppression if quantum computation is to yield an advantage over classical computation.

  • gain a general understanding of the important topics in near-term quantum computing, including adiabatic quantum computing.

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.
McGeoch, C. (2014). Adiabatic Quantum Computation and Quantum Annealing Theory and Practice. Morgan & Claypool. https://ieeexplore.ieee.org/document/7055969

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]
Albash T., Adiabatic Quantum Computing https://arxiv.org/pdf/1611.04471.pdf
McCardle S. et al, Quantum computational chemistry https://arxiv.org/abs/1808.10402

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/