Quantum Computing


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


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



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
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
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


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