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.

**Prerequisites and Desirable Previous Knowledge**

The course material should be of interest to physicists, mathematicians, computer scientists, and engineers. The interdsciplinary 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 notes will be provided giving an account of the necessary material. It would be desirable for you to look through these notes slightly before the start of the course. I should very much appreciate being told of any corrections or possible improvements and might even part with a small reward to the first finder of particular errors.

**Prerequisite notes**

- I always found it an interesting coincidence that the two basic ingredients of modern quantum theory, namely probability and complex numbers, were discovered by the same person, an extra-ordinary man of many talents, a gambling scholar by the name of Girolamo Cardano (1501–1576). Start with this essay.

Lectures 2017

- WEEK1: Basic concepts, quantum interference, “impossible” logic gates, qubits and single qubit interference (Hadamard, phase, Hadamard),

**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. It covers all the course material except two lectures on Bell inequalities and quantum cryptography. I recommend you read it all, but if you want to focus only on the examinable material (in 2017) you can skip sections 7.2–7.6 and chapters 8 and 9. - Book for the ambitious. 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. - John Preskill's lecture notes on quantum information theory, available at http://www.theory.caltech.edu/people/preskill/ph229/#lecture
- I personally like
*Quantum Computing since Democritus*by S. Aaronson; idiosyncratic, informative and fun to read (http://www.scottaaronson.com/democritus/)

**Examinable Topics (2017) **

- 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);
- definition of quantum entanglement (tensor product structure), Bell states, symmetric and antisymmetric subspaces of two qubits;
- 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;
- no-cloning theorem;
- quantum teleportation;
- quantum algorithms: Deutsch, Bernstein-Vazirani, Simon
- Quantum Fourier Transform and Phase Estimation;
- mathematical description of open quantum systems (density matrices, completely positive maps, partial trace, Born rule for density matrices);
- Bloch sphere - parametrisation, action of quantum gates on the Bloch vector;
- quantum error correction of both bit-flip and phase-flip errors;
- simple model of decoherence;
- Bell's inequality, local realism, no-signalling;
- application of Bell's inequality to quantum cryptography; quantum key distribution using entangled state.
- basic knowledge of physical implementations (e.g. qubits encoded in photon polarisation, electron spin);

Old Lecturenotes

Each lecture is summarised in no more than two pages.

- Lecture 0 Bits, gates, networks, Boolean functions, reversible and probabilistic computation
- Lecture 1 "Impossible" logic gates, amplitudes, quantum interference
- Lecture 2 One, two and many qubits
- Lecture 3 Entanglement and entangling gates
- Lecture 4 From interference to quantum algorithms
- Lecture 5 Algorithms, computational complexity and Quantum Fourier Transform
- Lecture 6 Phase estimation and quantum factoring
- Lecture 7 Non-local correlations and cryptography
- Lecture 8 Bell's inequalities
- Lecture 9 Density matrices and CP maps
- Lecture 10 Decoherence and quantum error correction

The notes are half-baked and may contain errors. Please let me know if you find any.

Problem Sheets

Supplementary Material

- Beyond the Quantum Horizon by D. Deutsch and A. Ekert, Scientific American, Sep 2012.
- Less reality more security by A. Ekert, Physics World, Sep 2009.
- The Limits of Quantum Computers, by S. Aaronson, Scientific American, Mar 2008.
- A Do-It-Yourself Quantum Eraser by R. Hillmer and P. Kwiat, Scientific American, May 2007.
- Quantum Seeing in the Dark by P. Kwiat et al, Scientific American, Nov 1996
- Physical Limits of Computation by C.H. Bennett and R. Landauer, Scientific American, Jul 1985.