Algorithmic Aspects of Quantum Computing
CPSC 489/689, Course Information, Spring 2003
Instructor: Dr. Andreas Klappenecker
This course gives an introduction to quantum algorithms, one of
the most exciting recent developments in computer science. We do not
expect any background knowledge in quantum computing, nor in quantum
physics. You need to know how to multiply matrices to understand the
basic operations of a quantum computer. Quantum computing is not
difficult, but simply different!
General Information
- The class meets MW 11:20am-12:30pm, and occassionally on Fridays.
- Office hours: MW 10:15am-11:15am, HRBB 509B.
- Syllabus
- Project topics
- You need to submit all three culture assignments until Wednesday, before class.
- You can review
Quantum walk as a subsitute for one culture assignement.
- You can review
Communication complexity as a subsitute for one culture assignment.
Lecture Notes
Homework
Challenge Problems
- Challenge Problem 1 [ps][pdf]
- Challenge Problem 2 [ps][pdf]
Lectures
- M 13 Jan Introduction, qubits, quantum key exchange.
- W 15 Jan Operations on a single qubit.
- F 17 Jan Operations on multiple qubits I.
- M 20 Jan Operations on multiple qubits II.
- W 22 Jan Measurements, simple quantum circuits.
- Review: Lecture notes, Chapter 2; pages 1-28 in Nielsen, Chuang.
- F 24 Jan Teleportation of a single qubit.
- M 27 Jan Teleportation of multiple qubits, Deutsch's problem.
- W 29 Jan Hidden subgroup problem, a small quantum search algorithm.
- Review: Lecture notes, Chapter 3.
- M 03 Feb Controlled Gates
- W 05 Feb Multiply controlled gates.
- M 10 Feb Universality.
- W 12 Feb Alfred - the simulator.
- Review: Nielsen, Chuang: Sections 4.1-4.3, 4.5.b
- M 17 Feb Divide-and-conquer, fast Fourier transforms
- M 19 Feb Dirac notations, quantum search
- M 24 Feb Quantum search
- W 26 Feb Lower bound for quantum search
- Review: Nielsen, Chuang: Chapter 6.
- M 03 Mar Factorization
- W 05 Mar Shor's algorithm
- Review: Shor's paper
- Spring Break
- M 17 Mar Review for exam
- W 19 Mar Complexity classes: P, NP, BPP, BQP, PSPACE
- F 21 Mar Midterm exam
- M 24 Mar Complexity classes: MA, QMA
- Review: Kitaev, Chapter 14
- W 26 Mar Quantum error control codes, Shor's code
- M 31 Mar CSS codes
- W 02 Apr Stabilizer codes
- M 07 Apr Fault-tolerant quantum computing
- W 09 Apr Fault-tolerant operations
- Review: Nielson, Chuang: Chapter 10
- M 14 Apr Pell's equation
- W 16 Apr Pell's equation
- Review: Papers by Lenstra and Hallgren
- M 21 Apr Physical Realizations of a Quantum Computer
- W 23 Apr Physical Realizations. Outlook.
- Review: Nielsen, Chuang: Chapter 7
- M 28 Apr Project presentations, usual class meeting time
- T 29 Apr Project presentations, usual class meeting time
- W 30 Apr Project presentations, 11:00am-4:00pm.
Copyright 2002 by Andreas Klappenecker, Texas A&M University.
Back to Andreas
Klappenecker's home page. 
