Announcements:
| 07/21/05: |
Homework 5 posted. |
| 07/02/05: |
Homework 4 posted. |
| 06/23/05: |
You should have received the midterm. It is due on June 30. |
| 06/20/05: |
Homework 3 posted. |
| 06/07/05: |
Homework 2 posted. |
| 05/24/05: |
Homework 1 posted. |
| 05/23/05: |
New website for summer course. |
Description:
This course is an introduction to the exciting new area of quantum computing. The lectures will be based in part on the text"Quantum Computation and Quantum Information" by M. Nielsen and I. Chuang, Cambridge University Press, 2000, and on handouts.
The algorithms of Shor for factorization, Grover for database search, and Brassard, Hoyer, Mosca and Tapp for summation of Boolean and real functions will be covered. The emphasis will be on upper and lower bounds on the number of qubits and quantum queries needed to solve these problems. The quantum and classical complexity of a number of problems will be discussed. Exponential and polynomial speedups for quantum computing will illustrate the potential power of quantum computers.
Prior knowledge of quantum mechanics is not required, although would be helpful. Prerequisite is knowledge of linear algebra.
This course will be offered as a CVN class.
Grading
Your grade will consist out of three parts:- Biweekly homework assigments (50 percent of the final grade),
- Midterm (15 percent of the final grade),
- Final (35 percent of the final grade).
Staff:
Original Instructor: Henryk Wozniakowski, henryk@cs.columbia.edu.CVN administrator: Arvid Bessen, bessen@cs.columbia.edu.
Please direct all your questions to the CVN administrator!
Homeworks:
There will be 5 homeworks. Homeworks will be given on a roughly biweekly schedule.
Homeworks will include a programming assignment, which can be done in Java, C, Matlab, Mathematica, or any other previously agreed on programming language.
Homework 1, due June 2
Homework 2, due June 16
Homework 3, due June 30
Homework 4, due July 14
Homework 5, due July 28
Class schedule:
| Class |
Topics
covered |
Reading |
Viewing |
| May 24 |
Overview of the course. Introduction to quantum computing. Linear algebra, Dirac notation. |
NC Ch. 1 (skim over) NC Ch. 2-2.1.6 |
Session 1 |
| May 26 |
Single qubit operations Multiple qubits - tensor products Multiple qubit operations |
NC Ch. 2.1.7 NC Ch. 4-4.2 |
Session 2 |
| May 31 |
Tensor products Inner products Operator functions |
NC Ch. 2.1.7-2.1.8 | Session 3 |
| June 7 |
Operator functions and their properties Controlled operations |
NC Ch. 4.3 | Session 4 |
| June 9 |
Controlled operations Measurement |
NC Ch. 2.2.3-2.2.5 NC Ch. 4.4 |
Session 5 |
| June 14 |
Bell/EPR states Quantum teleportation Quantum queries |
NC Ch. 2.6 | Session 6 |
| June 21 |
Quantum queries The Deutsch-Josza algorithm Review session |
NC Ch. 1.4 | Session 7 |
| June 23 | Midterm | ||
| June 28 |
The Quantum Fourier Transform Phase Estimation |
NC 5-5.2 | Session 8 |
| July 5 | Phase Estimation | NC 5.2 | Session 9 |
| July 12 |
Order Finding Factorization |
NC 5.3 | Session 10 |
| July 19 |
Applications of Order Finding Grover's Quantum Search Algorithm |
NC 5.4, 6.1 | Session 11 |
| July 26 |
Quantum Search Mean Computation Quantum Counting |
NC 6.3 |
Session 12 |
| Aug 2 |
Integration Review |
Session 13 | |
| Aug 9 | Final exam |
NC = Nielsen, Chuang, "Quantum Computation and Quantum Information"