Quantum Information Theory

COT6602

Term: Spring 2010
Time: Tue Thu 10:30am - 11:45am
Location: ENGR 383 		Instructor: Pawel Wocjan
Office : HEC 341
Office hours:TBA

Syllabus

Required Text:
There is no required textbook. We will focus on most active research areas in quantum algorithms.

Course Objectives:

Grading Policy:
The final grade will be determined as follows: Homework Assignments 50%; Project & Presentation: 50%

Grades A, B, C, D, and F are based on the straight-percentage scale (that is, 90% or above is A, 80% to 89.99% is B, etc.)

To enhance your learning experience and to help you solve the homework problems, you are encouraged to work in study groups of two to four people. However, you are required to turn in the solutions on your own, and you must never copy the solutions of other students.

No late homework will be accepted except for exceptional situations (handeled individually).

Please read and understand student rights and responsibilities including conduct rules clearly stated in UCF’s golden rules, at http://www.goldenrule.sdes.ucf.edu/2e_Rules.html

Announcements

Lectures

The following is a list of topics covered in each lecture, together with pointers to the corresponding portions of current papers and, where appropriate, additional lecture notes.

  Topic Readings
Lecture #1 (01/12) Quantum Data
Universal Gate Sets
Quantum Circuits
Reversible Computation 		Uniformity
Quantum Complexity
Fault Tolerance
Lecture #2 (01/14) Randomized Algorithms
   AND-OR Tree
   2-SAT 		Classical Randomized Algorithms for 2-SAT and 3-SAT
Lecture #3 (01/19) Randomized Algorithm for 2-SAT
Continuous-Time Walk
Lecture #4 (01/21) Solution of the Differential Equation of the "Discrete" Diffusion Equation
Definition of Matrix Functions
Lecture #5 (01/26) Continous-Time Quantum Walk - Revisited
  Schrödinger Equation and Laplacian Matrix
Random and Quantum Walks on a Line
Lecture #6 (01/28) Random and Quantum Walks on the Hypercube
Tuesday (02/02) No Class (Cancelled)
Lecture #7 (02/04) Simulating Hamiltonian Dynamics
   Efficient Simulation
   Adding Hamiltonians
Lecture #8 (02/09) Simulating Hamiltonian Dynamics
   Vizing's Theorem
   Sparse Hamiltonians
Lecture #9 (02/11) Exponential Algorithmic Speedup by Quantum Walk
   Blackbox Graph Traversal
   Quantum Walk Algorithm to Traverse the Glued Trees Graph
Lecture #10 (02/16) Exponential Algorithmic Speedup by Quantum Walk
   Classical and Quantum Mixing (to be continued)
Lecture #11 (02/18) Exponential Algorithmic Speedup by Quantum Walk
   Classical and Quantum Mixing (continued)
Lecture #12 (02/23) Discrete-Time Quantum Walk
   Stochastic Matrix
   Hitting Times
Lecture #13 (02/25) Discrete-Time Quantum Walk
   Hitting Times (continued)
Lecture #14 (03/02) Discrete-Time Quantum Walk
   Quantizing a Markov Chain
Lecture #15 (03/04) Discrete-Time Quantum Walk
   Quantizing a Markov Chain (continued)
   Spectrum Theorem
   Detecting Marked Elements and Its Complexity
03/08 - 03/12 Spring Break
03/15 - 03/19 Student Presentations
03/22 - 03/26 No Class
03/30 Student Presentations
Lecture #16 (04/01) Unstructured Search and Spatial Search
   Unstructured Search
   Discrete-time and Continuous-time Quantum Walk Algorithms
Lecture #17 (04/06) Quantum Key Exchange
   BB84 Protocol

Presentations

Date Student Topic
03/16 Paul and Stephen Lower Bound for Classical Algorithms to Traverse Glued Binary Trees
03/18 Fu and Hamed Simulating Sparse Hamiltonians with Star Decompositions
03/30 Michael and Nazar Classical Parallel Algorithms for Sparse Network
04/13 Fu and Hamed Quantum Phase Estimation and Approximated QFT
04/15 Michael and Nazar Quantum Walk Algorithm for Element Distinctness
04/20 Paul and Stephen Quantum Walk Algorithm for Formula Evaluation

Assignments