|Name of the course:||Quantum Computing|
|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
notes from an
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,
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||
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
Quantum key exchange protocol.
|28 Apr 03||Final examination, 2:30pm to 5:30pm.|