Computer Science

0368.4057


Lectures 
Mon 10:1013:00, Melamed 

Instructors 
Amnon TaShma  Schreiber 127  5364 

Open to 
Undergrad and grad students from CS or Physics. 

Textbooks 
Quantum Computation and Quantum Information, M. Nielsen,
I. Chuang 

Grading policy 
Homework is mandatory, Exam (mandatory for undergrad)
and/or paper presentation/ project 

Lecture
notes on the web



Links

quantph, a repository for all quantumrelated research papers 
Date 
Class Topic 
Lercture notes (in Hebrew) 
1. March 5 
One qubit, tensor products, two qubits, pure states, unitary matrices, X, Y, Z, CNOT, HAD. No cloning theorem. 

2. March 12 
Entanglement, superdense
coding, Quantum teleporation. The CHSH game (and Bell inequalities). 

3. March 19 
Tsirelson’s bound. More
on measurements. Every physical test can be captured by a POVM and vice
versa. The density matrix. 

4. March 26 
The
density matrix. Distinguishing two density matrices. Reduced density matrix.
No signaling. Safe storage principle. 

5. April 2 
No
signaling vs. local realisim. Simulating classical circuit by quantum
circuits, effects of garbage. Deutsch's algorithm,
DeutschJozsa algorithm, The blackbox model,
Simon's algorithm. 

6.
April 16 
The Fourier transform for Abelian
groups. Fourier transform over (Z_2)^n and
Z_(2^n). The Hidden subgroup problem. FFT and HSP. Discrete Log 

7. April 23 
Efficient quantum algorithm for FFT over Z_(2^n). Phase estimation. (based on [Watrous, Lectures 8 and 9]). Cayley graphs. 

8. April 30 
Efficient quantum algorithm for FFT over Z_p. Period finding, Order finding, Shor's
factoring algorithm. 

9. May 7 
Grover’s algorithm. Estimating the number of solutions
using phase estimation. 

10. May 14 
BBBV Lower bound on the OR function. A general lowerbound on quantum blackbox
computation by polynomials. Blackbox computation cannot provide more than a
polynomial speedup for total, Boolean functions. Communication complexity,
logrank lower bound. Quantum communication protocol for the DISJ problem. 

11. May 21 
Classical information theory (Shannon entropy, mutual
information, relative entropy) – Definitions, basic theorems, convexity. Quantum
information theory – relative entropy is always positive. Holevo’s
theorem. Random access codes. A 2 to 1 RAC. 

12. May 28 
RAC, a lower bound on on n>m
RAC, an application to 2local decoding of classical ECC. 

13. June 4 
Schmidt decomposition, impossibility of perfect bit
commitment, fidelity, , impossibility of imperfect
bit commitment, coin flipping. 

14. June 11 
A coin flipping protocol with maximal bias 0.75. The
quantum communication complexity of IP (via reduction to quantum information
theory). Te communication complexity when unlimited preshared PRboxes are
available. 

15. June 18 
Quantum error correcting codes. Shor’s
[9,1,1] code. CSS codes. Steane’s
[7,1,1,] code. 