| Name of the course: | Quantum Computing |
| Course number: | cs404 |
| Credits: | 6 |
| Instructor: | Jaikumar Radhakrishnan jaikumar@tifr.res.in |
| 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. |
| 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. |