skip to content

Centre for Quantum Information and Foundations


Quantum Information and Computation

Lecturer: Nilanjana Datta
Lent Term 2020, 24 lectures, Monday, Wednesday, Friday at 11am in MR3


Quantum processes can provide extraordinary benefits for information processing, communication and security, offering striking novel features beyond the possibilities of standard (classical) paradigms. These include (i) remarkable new kinds of algorithms (so-called quantum algorithms) providing an exponentially faster method for some computational tasks, (ii) new modes of communication such as quantum teleportation, and (iii) the possibility of unconditionally secure communication in quantum cryptography. Most of these exciting developments have occurred in just the past few decades and they underpin transformative applications for quantum technologies that are currently being developed.

This course will provide an introduction to these topics. No previous contact with the theory of computation or information will be assumed. 1B Quantum Mechanics is essential, but only in so far as to provide prior exposure to basic ideas of quantum mechanics. This course will rest on quantum theory just in a finite dimensional setting, so the principal mathematical ingredients (from finite dimensional linear algebra) will be readily accessible. We will begin by expounding the principles of quantum mechanics in our setting (and Dirac notation) and then immediately make connections to information (quantum states viewed as information carriers, quantum teleportation) and computation (notion of qubits and quantum gates). Then we will discuss quantum cryptography (quantum key distribution), and quantum computing, culminating in an exposition of principal quantum algorithms, including the Deutsch-Jozsa algorithm, Grover's searching algorithm and an overview of Shor's quantum factoring algorithm.

The course is richly cross-disciplinary in its conceptual ingredients and its novel perspective is also finding wide application in modern theoretical physics. It will be of interest to pure and applied mathematicians alike.

Course Contents:

Contents & References

Recap-Notes 1: Inner products, outer products & tensor products

Recap-Notes 2: Tensor products of operators; Kronecker product representation

Recap-Notes 3: Refinement of an incomplete measurement to a complete measurement: an example

Recap-Notes 4: An important note on the characterization of projective measurements

Recap-Notes 5: Properties of projection operators

Recap-Notes 6: Distinguishing between a pair of orthogonal states (Solution of the Exercise given in class)

Recap-Notes 7: Distinguishing Bell states via Bell measurements (Answer to a question asked after today's lecture)

Lecture Notes

Lecture Note 1: Introduction and Mathematical Preliminaries 

Lecture Note 2: Postulates of Quantum Mechanics (QM1)-(QM3)

Lecture Note 3: Quantum Measurements (QM4)

Lecture Note 4: Quantum states as information carriers (some remarkable quantum features)

Lecture Note 5: Quantum gates and quantum teleportation; Figures 

Lecture Note 6: Quantum Cryptography: BB84 Quantum Key Distribution (a correction)

 Note: simple examples of Information Reconciliation & Privacy Amplification given in the next lecture

Lecture Note 7: Classical computation & Classical Complexity

Lecture Note 8: Circuit model of quantum computation

Lecture Note 9: The Deutsch-Jozsa algorithm

Lecture Note 10: The quantum Fourier transform and periodicities

    A note clarifying an issue raised in class: Thanks to Wilfred Salmon!

Lecture Note 11: Quantum algorithms for search problems

    Figures for the Lemma on page 6 of Lecture Note 11

Lecture Note 12: Shor's quantum factoring algorithm

    Note: N is an arbitrary integer (even or odd); it is represented in binary using n = log N digits.

Remark regarding exams: Note that only those topics which are covered in the lectures and example sheets are examinable. There are certain bits of the lecture notes which were not covered in the lectures and will not appear in the exams. Also, there are a couple things that I have covered (or will cover) in the lectures which are not there in the notes. These are examinable.




Example Sheets:

Example Sheet 1

Example Sheet 2

Example Sheet 3

Example Sheet 4