Quantum Computing

COT6600


Term: Fall 2007
Time: Tue Thur 4:30pm - 5:45pm
Location: HEC 302

Instructor: Pawel Wocjan
Office hours: Tues Thurs 3:00pm - 4:15pm, HEC 339

Syllabus

Required Text:
The required text is An Introduction to Quantum Computing, by Phillip Kaye, Raymond Laflamme and Michele Mosca, Oxford University Press.
If you are waiting to buy this book, you might want to print out its first chapter, which is available for free.
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 (Chapters 1-9 of the KLM book):
Grading Policy:
The final grade will be determined as follows: Homework Assignments 1/3; Midterm Exam 1/3; Final Exam 1/3

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 and make-up tests will be accepted except for exceptional situations (handeled individually). All exams are closed books, closed notes, and no calculators.

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

Sample Exam; look carefully at this exam as preparation for the midterm exam on Tuesday 11/06

There will be no class on Tues 10/02. To make up for this, the classes on Tues 09/25 and Thurs 09/27 will be longer by 30min.
There will be no class on Tues 09/11. To make up for this, the classes on Tues 09/04 and Thurs 09/06 will be longer by 30min.

Lectures

The following is a list of topics covered in each lecture, together with pointers to the corresponding portions of the Kaye/Laflamme/Mosca text and, where appropriate, additional lecture notes.

  Topic Readings
Lecture #1 (08/21) Introduction & Background
  Overview
  Computers & the Strong Church-Turing Thesis
  The Circuit Model of Computation 		KLM Sections 1.1-1.3
Lecture #2 (08/23)   A Linear Algebra Formulation of the Circuit Model
  Reversible Computation 		KLM Sections 1.4-1.5
Lecture #3 (08/28) Linear Algebra and the Dirac Notation
  Kets & Bras
  Inner Product & Euclidean Norm
  Orthonormal Bases
  Tensor Product of Kets & Bras 		KLM Sections 2.1-2.2
Lecture #4 (08/30)   Kets & Bras
  Inner Product & Euclidean Norm
  Orthonormal Bases
  Tensor Product of Kets & Bras 		KLM Sections 2.1-2.2
Lecture #5 (09/04)  Linear operators, matrices
 Adjoints of kets, bras, and matrices
 Unitary operators
 Orthogonal Projectors 		KLM Section 2.3
Lecture #6 (09/06)  Representations of operators with respect to different bases
 Formal Definition of Tensor Products
 Some Comments on the Dirac Notation 		KLM Sections 2.6, 2.8
Lecture #7 (09/13) Presentation of Solutions for Homework #1  
Lecture #8 (09/18) The Framework of Quantum Mechanics
 The State of a Quantum System
 The Time Evolution of a Closed System
 Measurement
 KLM Sections 3.1 - 3.4
Lecture #9 (09/20) The Quantum Circuit Model
  Examples of simple quatum circuits
  Swap-Test 		KLM Sections 4.1 and 4.2
Lecture #10 (09/25)  Swap-Test
 Phase Kick-Back
 KLM Section 6.2
Lecture #11 (09/27) Introductory Quantum Algorithms
 Classical and Quantum Black-Boxes
 Deutsch Algorithm 		KLM Section 6.3
Lecture #12 (10/04)  Presentation of Solutions for Homework #2  
Lecture #13 (10/09)  Deutsch-Jozsa Algorithm KLM Section 6.4
Lecture #14 (10/11)  Simon's Problem
 Recall: Evaluation of Functions in Superposition
 Recall: Quantum Measurements 		KLM Section 6.5
Lecture #15 (10/16)  Simon's Algorithm KLM Section 6.5
Lecture #16 (10/18)  Zero-Error Algorithm for Simon's Problem
 Generalized Simon's Problem 		KLM Section 6.5
Lecture #17 (10/23) Shor's Algorithm
 RSA
 Integer factorization
 Order finding
 Reduction of integer factorization to order finding
  
Lecture #18 (10/25)  Modular Exponentiation; Square-and-Multiply
 Order-finding as determining the period of a black-box function
 First step of Shor's algorithm 		 
Lecture #19 (10/30) Presentation of Solutions for Homework 3  
Lecture #20 (11/01) Review of Topics as Preparation for Midterm Exam
Periodic Quantum States
Quantum Fourier Transform 		 
Lecture #21 (11/06) Midterm Exam  

Homeworks