Quantum algorithms

Semester: Monsoon 2007.
Lectures: Monday and Thursday, 13:30-15:00, A-212 (STCS seminar room).
Instructor: Pranab Sen.
Office hours: Just walk into A-226 any time.


This course is an introduction to quantum algorithms and computation. It is aimed at research scholars in their second year or upwards. Quantum computation is the recasting of computer science in a quantum mechanical framework, using quantum bits instead of classical bits as the basic unit of information storage. Quantum algorithms can sometimes improve on the best classical algorithms by making use of quantum phenomena like interference to quickly get rid of the "bad" computation paths in an algorithm, thereby enhancing the weights of the "good" computation paths. After Peter Shor's discovery in 1994 of efficient quantum algorithms for integer factoring and discrete logarithm, threatening current "classical" cryptography, the field has grown explosively and is now one of the most active subfields of both theoretical computer science and theoretical physics.


Students taking this course are strongly advised to attend a course on quantum information and error correction being offered concurrently by Naresh Sharma, at the same venue, same time, Wednesdays and Fridays. The first four lectures (during the week of August 6) are common to both courses. During that week, exceptionally, I shall lecture on Monday and Wednesday, and Naresh will lecture on Thursday and Friday.


No prior knowledge of quantum physics will be assumed; we shall provide the background required. Some familiarity with the classical computer science notions of algorithms and boolean circuits will be helpful. The main background required is linear algebra, more specifically, familiarity with abstract notions of vector spaces, linear operators, Hermitian and unitary operators and the spectral theorem for such operators. We shall not assume prior knowledge of the tensor product; instead, we shall learn about it during the course. The most important prerequisite for this course is the so-called mathematical maturity. We hope to see a variety of quantum algorithms during the course each using very different ideas and mathematical techniques, and students should be able to grasp a variety of mathematical concepts.


We aim to cover a good fraction of the following topics during the course:
During and after the course, you may wonder why there are still so few classes of quantum algorithms that are known even after more than ten years since Shor's breakthrough discovery. We do not have a good answer to that. Hence, we need your help in remedying this situation. If this course enthuses you to delve into current research in quantum computation, and excites you into working in this or related areas, then ... welcome aboard!


Performance will be judged based on homework assignments and a seminar at the end of the course. The plan is to have a homework assignment every few weeks. For the course-end seminar, students will have to pick a topic not covered in the course, read a couple of research papers about it, and then give a presentation. A list of suggested topics and research papers will be put up later.


  1. Out: August 27, In: September 10. Covers lectures 6-8. Problems.
  2. Out: September 10, In: October 1. Covers lectures 9-13. Problems.

Study material

For the initial part of this course, we shall use Quantum computation and quantum information by Nielsen and Chuang as the basic textbook. However, we shall study a lot of recent material on quantum algorithms which is not covered by the textbook. Also, we may do some standard topics in a different way as compared to the textbook. We shall provide links to appropriate study material to support the individual lectures. Below, the chapters refer to those in the textbook.
  1. August 6: Introduction and motivation for quantum computation and information. Recommended reading: Chapters 1 and 2. Slides.
  2. August 8: Examples of quantum algorithms and communication protocols. Recommended reading: Chapters 1 and 2. Slides.
  3. August 9: Postulates of quantum mechanics, mathematical formalism. Recommended reading: Chapters 1 and 2, John Watrous's lecture notes, Naresh's handwritten notes.
  4. August 10: Superdense coding, linear algebra background, density matrices, partial trace. Recommended reading: Chapters 1 and 2, John Watrous's lecture notes, Naresh's handwritten notes.
  5. August 13: Motivating density matrices and partial trace, embedding classical computation into quantum. Lecture notes.
  6. August 16: Exponential of matrices, Trotter formula, generalised Pauli matrices, decomposing a general unitary operator into products of unitaries with scaled generalised Pauli matrices as Hamiltonians. Recommended reading: Chapter 4 for simulating quantum systems. Lecture notes.
  7. August 20: Universal gates for quantum computation. Recommended reading: Chapter 4 for an alternate universality construction. Lecture notes.
  8. August 23: Deutsch, Deutsch-Jozsa and Simon's problems. Recommended reading: John Watrous's lecture notes on Deutsch-Jozsa and Simon's algorithms. Lecture notes.
  9. August 27: Definition of hidden subgroup problem and characters of finite abelian groups. Recommended reading: Babai's survey article on characters of finite abelian groups. Lecture notes.
  10. August 30: Efficient quantum algorithm for the abelian hidden subgroup problem using the quantum Fourier transform over the group. Lecture notes.
  11. September 6: Coppersmith's circuit for the quantum Fourier transform over cyclic groups of power of two orders, definition of the eigenvalue estimation problem, using eigenvalue estimation for computing the Fourier transform over any cyclic group. Recommended reading: Chapter 5 for Coppersmith's circuit and eigenvalue estimation, Kitaev's original paper for using eigenvalue estimation in order to compute the quantum Fourier transform over any cyclic group. Lecture notes.
  12. September 10: Efficient circuit for eigenvalue estimation, method of continued fractions. Recommended reading: Chapter 5 for eigenvalue estimation and method of continued fractions. Lecture notes.
  13. September 13: Hidden subgroup problem in integers. Recommended reading: Chapter 5 for order finding subroutine of Shor's algorithm and period finding in integers. Lecture notes.
  14. September 17: Shor's algorithms for integer factoring and discrete logarithm. Recommended reading: Chapter 5 for the two Shor's algorithms, survey article on Shor's discrete logarithm algorithm. Lecture notes.