Quantum Information Theory


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


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



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
Quantum Complexity
Fault Tolerance
Lecture #2 (01/14) Randomized Algorithms
   AND-OR Tree
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


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