Term: Spring 2010 Time: Tue Thu 10:30am  11:45am Location: ENGR 383 
Instructor: Pawel Wocjan Office : HEC 341 Office hours:TBA 
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 ANDOR Tree 2SAT 
Classical Randomized Algorithms for 2SAT and 3SAT 
Lecture #3 (01/19)  Randomized Algorithm for 2SAT ContinuousTime Walk 

Lecture #4 (01/21)  Solution of the Differential Equation of the "Discrete" Diffusion Equation Definition of Matrix Functions 

Lecture #5 (01/26)  ContinousTime 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)  DiscreteTime Quantum Walk Stochastic Matrix Hitting Times 

Lecture #13 (02/25)  DiscreteTime Quantum Walk Hitting Times (continued) 

Lecture #14 (03/02)  DiscreteTime Quantum Walk Quantizing a Markov Chain 

Lecture #15 (03/04)  DiscreteTime 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 Discretetime and Continuoustime 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 