Introduction to Quantum Information (aka C 7.4)
The classical theory of computation usually does not refer to physics. Pioneers such as Turing, Church, Post and Goedel managed to capture the correct classical theory by intuition alone and, as a result, it is often falsely assumed that its foundations are self-evident and purely abstract. They are not! Computers are physical objects and computation is a physical process. Hence when we improve our knowledge about physical reality, we may also gain new means of improving our knowledge of computation. From this perspective it should not be very surprising that the discovery of quantum mechanics has changed our understanding of the nature of computation. In this series of lectures you will learn how inherently quantum phenomena, such as quantum interference and quantum entanglement, can make information processing more efficient and more secure, even in the presence of noise.
The course material should be of interest to physicists, mathematicians, computer scientists, and engineers. The interdisciplinary nature of this course and your diverse backgrounds means that some of you may find some lectures easy while others find them difficult. The following will be assumed as prerequisites for this course: elementary probability, complex numbers, vectors and matrices, Dirac bra-ket notation, a basic knowledge of quantum mechanics especially in the simple context of finite dimensional state spaces (state vectors, composite systems, unitary matrices, Born rule for quantum measurements), basic ideas of classical theoretical computer science (complexity theory) would be helpful but are not essential.
Prerequisite Material (updated 15 Jan 2019) Linear algebra in Dirac notation plus various trivia you should really know about. It would be desirable for you to look through these notes slightly before the start of the course, or early into the course, and attempt all the exercises. But hey, I am not here to tell you how to live your life, use the notes as you see fit. Just don’t look puzzled when I talk about bras and tensor products.
The notes (here) are half-baked and may contain errors. Please do let me know if you find any. Exercises in the lecture notes may overlap with some of the problems in the problem sheets but they are there just for your own "entertainment".
Examinable Topics (2020)
- fundamentals of quantum theory: addition of probability amplitudes, quantum interference, mathematical description of states and evolution of closed quantum systems (Hilbert space, unitary evolution), measurements (projectors, Born rule), Pauli matrices;
- Distinguishability of quantum states
- Bloch sphere - parametrisation, action of quantum gates on the Bloch vector;
- definition of quantum entanglement (tensor product structure)
- no-cloning theorem, quantum teleportation;
- quantum gates e.g. phase gate, Hadamard, controlled-not, SWAP, the Hadamard-phase-Hadamard network, phase “kick-back” induced by controlled-U, phase “kick-back” induced by quantum Boolean function evaluation;
- quantum algorithms: Deutsch, Bernstein-Vazirani, Simon
- quantum correlations, CHSH inequality,
- density matrices, partial trace, statistical mixture of pure states, Born rule for density matrices,
- quantum entanglement in terms of density matrices
- completely positive maps, Kraus operators, the Choi matrix, positive versus completely positive maps, partial-transpose
- simple model of decoherence, quantum error correction of bit-flip and phase-flip errors
Textbooks and reading to complement course material
- P. Kaye, R. Laflamme and M. Mosca, An Introduction to Quantum Computing. OUP, 2007. This is probably the best textbook for this particular course.
- M. Nielsen and I. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000. It is considered the standard textbook in the field. The book was published around 2000, so its treatment of some topics is dated, but there is still no better overview of the whole field.
- Check John Preskill's excellent lecture notes on quantum information theory.
- For something more idiosyncratic, informative and fun to read try Quantum Computing since Democritus by Scott Aaronson.