# 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):
• Linear Algebra & the Dirac Notation
• Qubits & the Framework of Quantum Mechanics
• Quantum Circuit Model
• Introductory Quantum Algorithms (Deutsch algorithm, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm, Simon's algorithm)
• Algorithms with Superpolynomial Speed-up (Shor's algorithm for factoring integers and finding discrete logarithms, Algorithm for Finite Abelian Hidden Subgroup Problem)
• Algorithms based on Amplitude Amplificaton (Grover's quantum search algorithm)
• Quantum Computational Complexity Theory & Lower Bounds (Polynomial method, Adversary methods)

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

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

• Homework 1 [pdf] out on 08/31, due on Thurs 09/13 before class
• Homework 2 [pdf] out on 09/20, due on Thurs 10/04 before class
• Homework 3 [pdf] out on 10/18, due on Tues 10/30 before class
• Homework 4 [pdf] out on 09/20, due on Mon 12/03 before meeting at 3:00pm