Quantum Computing

COT6600


Term: Fall 2009
Time: Mon wed 1:30pm - 2:45pm
Location: ENGR 383

Instructor: Pawel Wocjan
Office hours: Mon Wed 2:45pm - 4:00pm, HEC 339
TA: Chen-Fu Chiang
Office hours:TBA

Syllabus

Required Text:
The required text is Quantum Computation and Quantum Information, by Michael A. Nielsen and Isaac L. Chuang, Oxford University Press.
It is essential that all students have access to this book. Pointers to the relevant sections of the book will be provided as we go along.

Course Objectives:
Introduction to quantum computing with an emphasis on the computer science part of the field. Topics that will be covered (from the NC book and research articles):
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 the Nielsen/Chuang text and, where appropriate, additional lecture notes.

  Topic Readings
Lecture #1 (08/24) Turing Machine
Strong Church-Turing Thesis
Circuit Model 		Section 3.1.2 Circuits
Lecture #2 (08/26) Circuit Complexity of Boolean Functions
Uniform Families of Circuits
Lecture #3 (08/31) Fredkin Gate
Computing Functions Reversibly 		Section 3.2.5
Lecture #4 (09/02) Euler Formula
Dirac Notation
Quantum Bits
Blochsphere
 Section 1.2
Monday (09/07) No Class (Labor Day Holiday)
Lecture #5 (09/09) Euler Formula Applications
Multiple Qubits
Single Qubit Gates
Multiple Qubits Gates
 Section 1.2.1-1.3.2
Lecture #6 (09/14) Change of Basis
No-Cloning Theorem
 Section 1.3.3-1.3.5
Lecture #7 (09/16) Bell States
Teleportation
Quantum Parallelism
Deutsch Algorithm
 Section 1.3.6-1.4.3
Lecture #8 (09/21) Deutsch Algorithm
 Section 1.4.3
Lecture #9 (09/23) Deutsch-Jozsa Algorithm
 Section 1.4.4
Lecture #10 (09/28) Bernstein-Vazirani Algorithm
Lecture #11 (09/30) Measurement
(Probabilities, Post-measurement States)
Lecture #12 (10/05) Vector Spaces over Finite Fields
Linear Error Correcting Codes
Simon's Algorithm
Lecture #13 (10/07)

Lecture #14 (10/12)

Lecture #15 (10/14) Examples of Reduction of Factoring to Order Finding
Lecture #16 (10/19) Chinese Remainder Theorem
Group of Units, Modular Inverses
Euclid's Algorithm
Proof of Reduction of Factoring to Order Finding
Lecture #17 (10/21) Proof of Reduction of Factoring to Order Finding
Lecture #18 (10/26) Shor's Algorithm for Period Finding
Definition of Fourier Transform
Lecture #19 (10/28) Properties of Fourier Transform (Unitarity, Shift Invariance)
Fourier Transform of Comb Functions
Visualization of Disturbances Due to Non-periodic Cutoff
 DFT Simulation Code (Matlab)
Lecture #20 (11/02) Quantum Fourier Transform
 Section 5.1
Lecture #21 (11/04) Grover's Algorithm
 Section 6.1.1
Lecture #22 (11/09) Grover's Algorithm - Known Number of Solutions
 Section 6.1.2
Wednesday (11/11) No Class (Veterans Day)
Lecture #23 (11/16) Discussion of Topics for Class Presentations
Lecture #24 (11/18) Grover's algorithm - Known Number of Solutions
 Section 6.1.2
Lecture #25 (11/23) Grover's algorithm - Unknown Number of Solutions
Section 6.1.3
Lecture #26 (11/25) Quantum Amplitude Amplification
Section 6.1.4
Lecture #27 (11/30) Quantum Phase Estimation
Section 5.2

Reading Assignments

Homeworks


Final Presentations

Time: 1:00PM-3:00PM (Dec.11)
Location: Conference room ENGR288
Topic Material
1. Simulation of Quantum Circuits  
2. Shor's Approach to Period Finding KLM book, pages 139 - 142
3. Quantum Circuits for Implementing Fourier Transforms of Arbitrary Length The article
4. Quantum Algorithm for Solving the Discrete Logarithm Problem (Visualization of 2D Fourier Transform)  
5. Quantum Algorithms for Solving Abelian Hidden Subgroup Problems & Determining the Structure of Abelian Black-Box Groups KLM book, pages 146 - 151; The article
6. Eigenvalue Estimation Approach to Order Finding KLM book, pages 134 - 139
7. Quantum Counting KLM book, pages 170 - 175