Venue: Emmy Noether Seminar Room
Class Timings: Tuesdays & Thursdays from 9:45 AM - 11:15 AM
First Meeting: 28 January 2025
Course Description: We will start by studying the circuit-based framework for classical computation, and understand how classical deterministic computation can be made reversible. We will introduce randomness in classical computation. We will define the classical complexity classes P, NP, BPP, PSPACE, etc., and understand their interdependencies. After this introduction to classical computation, we will introduce quantum information, registers, qubits, the notion of a quantum pure state, and the associated ideas of superposition and entanglement. We will describe the model of quantum circuits. Using this background, we will study various quantum algorithms: Deutsch-Jozsa, Teleportation, Superdense coding, Bernstein-Vazirani algorithm, Quantum Fourier transform, Phase estimation, Factoring, Grover's algorithm. We will study the more sophisticated framework for quantum query algorithms using quantum random walks, and see examples where they are effective.
We will study various lower bound arguments for quantum query complexity: the hybrid argument, the polynomial method, the quantum adversary method, the recording queries method, etc. We will briefly study the complexity classes BQP and QMA. We will cover more material if there is time remaining.
References:
- M. Nielsen and I. Chuang. Quantum Computation and Quantum Information
- A.Yu. Kitaev, A.H. Shen and M.N. Vyalyi. Classical and Quantum Computation
- Ronald de Wolf. Quantum Computing: Lecture Notes, https://homepages.cwi.
nl/~rdewolf/qcnotes.pdf - John Watrous. Lecture notes on Quantum Computation, https://
johnwatrous.com/lecture-notes/
Course Evaluation: Quizzes in class 10%, Problem sets 30%, Mid-term 30% & Final exam 30%
Course Outcome:
- An understanding of classical deterministic, reversible and randomized computation through circuits.
- Proficiency in building quantum circuits for standard quantum algorithms, quantum Fourier transform, phase estimation, quantum random walk using quantum circuits, query algorithms.
- An understanding of quantum lower lower bounds in the query model and quantum complexity classes.
Prerequisites:
The students are not required to have formally taken any other course in order to take this course. However, we will expect that they have the following preparation for the course.
Mathematics
Algebra (modular arithmetic, Chinese remainder theorem, Fermat's little theorem)
Linear algebra (finite-dimensional complexes inner-product spaces, linear transformations, unitary and Hermitian matrices, eigenvalues, spectral decomposition, singular value decomposition, tensor products of inner-product spaces)
Probability (discrete random variables, their expectation and variance, Markov's inequality, Chebyshev's inequality, random walk on a line)
Physics
Prior familiarity of quantum superposition and entanglement would be helpful, but is not necessary
Computer Science
Prior familiarity with classical algorithm, gates and circuits would be helpful, but is not necessary
- Teacher: Jaikumar Radhakrishnan
Credit Score: 4