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.

- Mathematical formlisms of quantum states and quantum operations

- Classical versus quantum computation
- Universal gates for quantum computation
- Quantum Fourier transform based algorithms

- Amplitude amplification based algorithms

- Quantum walk based algorithms
- Knot theory based algorithms

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

- August 6: Introduction and motivation for quantum computation and information. Recommended reading: Chapters 1 and 2. Slides.
- August 8: Examples of quantum algorithms and communication protocols. Recommended reading: Chapters 1 and 2. Slides.
- August 9: Postulates of quantum mechanics, mathematical formalism. Recommended reading: Chapters 1 and 2, John Watrous's lecture notes, Naresh's handwritten notes.
- 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.
- August 13: Motivating density matrices and partial trace, embedding classical computation into quantum. Lecture notes.
- 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.
- August 20: Universal gates for quantum computation. Recommended reading: Chapter 4 for an alternate universality construction. Lecture notes.
- 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.

- 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.
- August 30: Efficient quantum algorithm for the abelian hidden subgroup problem using the quantum Fourier transform over the group. Lecture notes.
- 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.
- 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.
- 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.
- 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.