Quantum computing seminar lectures
Here are the notes, in several formats. The 2up versions place two slides on a page for easier printing.
Formats Available  Other information  
Sept 18 2003 


PDF PDF 2Up 
DVI DVI 2Up 
PS PS 2Up 
Overview of quantum computing, classical computing, history, etc. 
Sept 25 2003 


PDF PDF 2Up 
DVI DVI 2Up 
PS PS 2Up 
An introduction to quantum mechanics as it applies to quantum computing. Also contains some linear algebra, and notation used by physicists. 
Oct 2 2003



Continuation of quantum mechanics, the No Cloning theorem, Bell's Inequalities, start of classical computation theory.  
Oct 9 2003



Classical computation theory, starting with the definition of a Turing Machine, followed by an a brief introduction to classical circuits. The standard complexity classes P and NP will be explained, as well as some others, most notable BPP. These topics are selected to illustrate the quantum analogs later.  
Oct 16 2003



I will cover Grover's database search that searches an unsorted list of N items in O(\sqrt(N)) time, compared to the required O(N) classical computing complexity. Here is the original paper.  
Oct 23 2003



I will cover Peter Shor's integer factoring algorithm, the most famous application of quantum computing to date. His algorithm gives an exponential speedup to the best classical algorithms for factoring and the Discrete Log Problem, with applications to cryptography. Here is the original paper.  
Oct 30 2003



This will be the last lecture until December, since I will be gone for November. The HSP is a framework for quantum algorithms, and is a very active area of research. Solving the HSP for the permutation groups, for example, would result in an efficient quantum algorithm for solving Graph Isomorphism, a hard classical problem.  