A course on quantum computing (Spring 2003)

Name of the course: Quantum Computing
Course number: cs404
Credits: 6
Instructor: Jaikumar Radhakrishnan
Lecture timings: Wendesdays 11:35am to 1:00pm
Thursdays 10:35am to 12:00noon
Text book: M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information, Cambridge.


Quantum computing is a new area in Computer Science. It is based on basic postulates of quantum mechanics, a revolutionary contribution of 20th century physics. The goal of this course is to introduce the audience to the elegant mathematical foundations and basic results of this field. Many important aspects of this field, where ideas from Physics, Mathematics and Computer Science intermingle, are still to be properly understood. Through this course we hope to provide an elementary background to these and make the important questions in this area accessible to a wide audience.


31 Dec 02, 2 Jan 03 Classical computation: strings, languages, complexity classes: P, NP. P has polynomial size circuits. You can find material on this in the first chapter of the notes from an earlier course.
Circuits complexity, randomized computation: BPP has polynomial size circuits. Look at the notes (pages 24--28 and pages 40--42).
8, 9 Jan 03 Circuit complexity, Hastad's lower bound for parity: decision trees, switching lemma. See Paul Beame's A switching lemma primer (pages 1 to 8).
Homework 1 [Clarifications]
15, 16 Jan 03 Classical determinisitic and randomized computation using matrices, tensor products of matrices, composition of circuits, parallel execution of circuits, qubits, Deutsch's algorithm.
Linear algebra background: vector spaces over complex numbers, inner products, adjoints, tensor products of vector spaces.
22, 23 Jan 03 Linear transformations in tensor product spaces, Deutsch's algorithm revisited, the Hadamard transform.
Homework 2. (due 5 Feb 03)
The Deutsch-Jozsa algorithm, reversibe computation.
29, 30 Jan 03 Classical reversible computation. Reversible realization of Boolean functions: the Toffoli, the CNOT gate. Any unitary operation is a product of two qubit unitary operations. Miracles: Quantum teleportation and superdense coding.
5, 6 Feb 03 Every two qubit controlled unitary operation can be written as a product of CNOT gates and single qubit operations. Pauli matrices, operator functions, Block sphere, functions on operators.
Grover's quantum search algorithms when there is a unique solution. Implementation of inversion about the average. Grover iteration. Motivation using histograms, analysis using rotations.
13 Feb 03 Grover's quantum search algorithms when there are multiple solutions. Optimality of Grover's algorthm. The polynomial method for showing lower bounds.
Homework 3 (due 5 Mar 03)
17 Feb 03 Midterm
26, 27 Feb 03 Optimality of Grover's algorthm---proof using a different potential function. Simon's algorithm.
Quantum Fourier Transform using O(n^2) gates. Phase estimation when the phase has a small binary representation.
5, 6 Mar 03 Phase estimation to arbitrary accuracy. Counting the number of solutions in Grover's algorithm.
Overview of Shor's factoring algorithm.
Homework 4 (due 26 Mar 03) [We were not able to cover continued fractions in the class, so Problem 10 will be considered part of the next homework.] [Optimality of Grover's algorithm: solution to Problem 4.3.]
12, 13 Mar 03 Shor's factoring algorithm by sampling the Fourier transform. We used Preskill's notes. Factoring reduces to order finding. [The proof sketched in class appears in Chapter 6 of KR Parthasarathy's notes.]
Kitaev's factoring algorithm using phase estimation. Euclid's algorithm.
19 Mar 03 Comparison based searching and sorting. (This lecture was given by Pranab Sen. There was no lecture on 20 Mar 03.)
26, 27 Mar 03 Extended Euclid's algorithm. Convergents in continued fraction expansions. Quantum probability. Projective measurements. The state of the system after a projective measurment. Examples.
3 Apr 03 Mixed states. The density operator. Spectral decomposition of the density operator. (2 Apr 03 was a holiday for Gudi Padwa.)
9, 10 Apr 03 The state of the subsytem. The reduced density operation. The partial trace operation: why partial trace?
Schmidt decomosition. Purification of mixed states.
16, 17 Apr 03 Quantum error correcting codes. The 3-bit repetion code for bit-flip errors. The 3-bit repetition code for phase flip-errors. The 9-bit Shor code.
Quantum key exchange protocol.
28 Apr 03 Final examination, 2:30pm to 5:30pm.

Jaikumar Radhakrishnan
Last modified: Tue Apr 22 16:17:54 IST 2003