Quantum Information theory and Computation

instructor nicolas macris
office inr 134
phone +4121 6938114
email nicolas.macris@epfl.ch
lectures tuesday 10h15 – 12h, room INR 113
exercises friday 10h15 – 12h, room INR 113

Special announcements

Do not forget to choose exam subjects among the list given in class. We have to agree on subjects before the Christmas break.

From now on notes are manuscript and may contain a greater amount of mistakes (sorry). In the pdf “chap 12” on page 16 there is at least one mistake: the true lower bound for the Euler function is \phi \geq \frac{r}{4\ln\ln r}, r\geq 19. The “r” in the numerator has to be propagated in the rest of the notes (easy exercise !).


It appears that today one is able to manipulate matter at the nanoscale, so that although the technology does not yet exist, information processing may have to take into account the laws of quantum physics. This course introduces the theoretical concepts and methods that have been developped in the last two decades to take advantage of guenuine quantum ressources. We will see how the concepts of bit and entropy, and Shannon’s theory can extended to the quantum domain. We will emphasize the role of entanglement which is a distinctly quantum feature. We will also see how useful quantum parallelism can be in the theory of quantum computation. No prerequisite in quantum mechanics is needed.

Outline: the course is divided in three parts


  1. Introduction to quantum mechanics, Qbits and quantum cryptography.
  2. Quantum information theory.
  3. Quantum computation, and quantum error correcting codes.


Part 1: QM, Qbits, Cryptography Notes, Exercices  
Experiments with light, analyzers and polarizers chap 1, ex1  
Mathematical formalism of quantum mechanics chap 2, ex2, ex3  
Quantum key distribution protocols chap 3, ex4  
Quantum entanglement chap 4, ex5, ex6  
Part 2: Quantum Information Theory Notes, Exercises  
Density matrix formalism chap 5, ex7  
Quantum entropy chap 6, ex8  
Accessible information chap 7  
Source coding theorem chap 8  
Channel capacity theorems chap 9, ex9  
Part 3: Computation and Error Correction Notes, Exercises  
Models of computation chap 10, ex10  
Deutsch-Josza problem chap 11  
Hidden subgroup, period finding and QFT chap 12  
Circuit and complexity of QFT chap 12bis  
Factoring algorithm (Shor) chap 13  
Search algorithm (Grover) chap 14  
Quantum error correction    


Course notes and homework

In principle, are posted weekly.


Oral seminar presentations by students.

Additional reading material


  • A rather complete reference Quantum Computation and Quantum Information, by Michael A. Nielsen and Isaac L. Chuang, Cambridge University Press (2004).


  • A book that covers quantum computing An introduction to quantum computing, by Phillip Kaye, Raymond Laflamme and Michele Mosca, Oxford University Press (2007).


  • A small pedagogic book written by a phycisist A short introduction to quantum information and quantum computation, by Michel Le Bellac, Cambridge University Press (2006).


  • A collection of reprinted articles can be found in Quantum computation and quantum information theory eds C. Macchiavello, G.M.Palma, A.Zeilinger world scientific (2000).


  • For an emphasis on computer science aspects Quantum computing, by Mika Hirvensalo, Springer Verlag (2001).


  • See the Feynman lectures on Physics, vol 3 by Richard P. Feynman, Robert B. Leighton, Matthew Sands (1998) Addison Wesley.


  • For those who want to seriously learn quantum physics Quantum Mechanics by Albert Messiah, ed Dover (two volumes bound as one).