CS294-2
Quantum Computation
Fall 2004
Instructor
Umesh Vazirani
Office: 671 Soda, 642-0572
Lectures:
TuTh 10:30-12 (405 Soda)
Office Hours: M 1-2 (671 Soda)
Quantum computation is an exciting area that at the intersection of computer
science, mathematics and physics. It touches on fundamental questions in
computer science as well as quantum physics. This course will provide a comprehensive
introduction to this area including:
1. An introduction to quantum physics from a quantum information viewpoint.
2. Quantum algorithms for factoring, discrete log and search.
3. Limits on the power of quantum computers.
3. Quantum error-correcting codes and fault-tolerant quantum computation.
4. Quantum information and cryptography.
5. Survey of proposals for implementation of quantum computers.
Prior coursework in quantum mechanics is not essential. This interdisciplinary
subject draws on techniques from theoretical computer science, mathematics,
and quantum physics. Students with a strong background in any one of these
areas are welcome to attend.
Announcements
A list of papers for projects is now available at
project-list
There will be no lecture on Tuesday 9/21 and Thursday 9/23. Please use
the opportunity to digest the concepts already introduced and to work on
the new assignment. I will announce makeup lectures later in the semester.
Homework
Homework 1 [ps pdf] due Tuesday 9/14.
Homework 2 [ps pdf] due Tuesday 9/28.
Homework 3 [ps pdf] due Tuesday 10/26.
Lecture notes
Topic
Notes (modified)
1
8/31
Intro, Qubits, Measurements, Bell Inequalities.
[
pdf,
ps] (9/5)
2
9/2
Two qubit states, Unitary Evolution, Quantum gates, Superdense
coding
[
ps] (9/13)
3
9/7
Hilbert Spaces, Tensor Products, No Cloning Theorem, Teleportation
(preliminary version)
[
ps] (9/8)
4
9/9
Universal Gate Sets, Solovay-Kitaev theorem, BQP, Reversible
Computation.
[
pdf,
ps] (9/20)
5
9/14
Reversible computation, BPP in BQP, accuracy.
[
pdf,
ps] (10/5)
7
9/28
Simon's Algorithm
[
pdf,
ps] (10/2)
8
9/30
Quantum Fourier Transform
[
pdf,
ps] (10/15)
9
10/5
Shor's Factoring Algorithm
[
pdf,
ps] (10/15)
10
10/7
NP-complete problems - quantum lower bounds + Grover's algorithm.
[
pdf,
ps] (10/7)
11
10/12
Grover contd. + Quantum zeno effect + Vaidman Bomb.
[
pdf,
ps] (10/15)
12
10/14
Hidden Subgroup Problem + discrete log.
[
pdf,
ps] (10/17)
13&14
10/19 and 10/21
Quantum Walks, Hitting Time, Element Distinctness
[
pdf,
ps] (10/30)
15
10/26
Hamiltonians, Schrodinger's Equation, Uncertainty Relations.
[
pdf,
ps] (11/7)
16
10/28
Dirac Equation, Entropic Uncertainty Relation.
[
pdf,
ps] (11/12)
17-19
11/2, 11/4, 11/9
Quantum simulation, Quantum NP.
[
pdf,
ps] (11/15)
20
11/16
Density Matrices, trace norm, von Neumann entropy.
[
pdf,
ps] (11/20)
21
11/18 and 11/23
Quantum Error-correcting codes.
[
pdf,
ps] (11/20)
Useful Links:
- Los Alamos archive of papers and preprints on Quantum Mechanics and Quantum
Computation: link
- John Preskill's Quantum Computation course at Caltech: link
Recommended reading
On quantum computation
- Nielsen and Chuang, Quantum Computation and Quantum Information
An encyclopedic reference for quantum information theory.
Weaker coverage of computational issues.
- Kitaev, Shen and Vyalyi, Classical and Quantum Computation
Interesting but idiosyncratic.
Mathematical background
- Strang, Gilbert. Linear Algebra and Its Applications
Good review of matrix theory and applications.
- Jordan, Thomas F. Linear operators for Quantum Mechanics
Thorough presentation of operators and mathematical structure.
On quantum mechanics in general
- Feynman, Richard P. The Feynman Lectures on Physics, volume
3
A famous introduction to undergraduate physics. Good
section on 2-state systems.
- Griffiths, David J. Quantum Mechanics
clear explanations, doesn't cover everything.
- Liboff, Richard L. Introductory Quantum Mechanics
Good coverage, explanations medium. See Ch. 16 in the
new (4th) edition for intro. to Quantum Computing.
- Baym, Gordon. Lectures on Quantum Mechanics
Graduate level textbook. clear exposition of the
physics.
- Feynman, Richard. QED
Highly recommended non-technical exposition.