Computer Science

0368.4057


Span
programs and quantum query complexity: The general adversary bound is nearly
tight for every boolean
function. B. Reichardt.
Proc.
FOCS 2009, Extended abstract,
Full version: quantph/0904.2759,
2009. slides
Lectures 
Thursday, 10:1013:00, ëéúä 125 áðééï ùàôì 

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) 
Chapters in Nielsen and Chuang 
1. Oct 17 
Nature as computation. Classical computation. One qubit, X, Y, Z, HAD. Many qubits. Tensor products, two qubits, CNOT. The twoslit experiment. Projection measurements. 
1.1,
1.2, 1.3.11.3.4, 1.5.1, 2.1.7, 2.2.1, 2.2.32.2.5 

2. Oct 24 
The quantum world. Superdense coding, Quantum teleporation. Entanglement.
No cloning theorem. 
1.3.51.3.7, 2.3 

3. Oct 31 
General measurements. POVM. Every
physical test can be captured by a POVM and vice versa. The density matrix. 
2.22.6, 2.4.1, 2.4.2 

4. Nov 7 
More on density matrices.
Measurements, POVMs and observables. The
CHSH game (and Bell inequalities). A quote: Bell expressed his hope
that such work would "continue to inspire those who suspect that what is
proved by the impossibility proofs is lack of imagination." 
2.6 

5. Nov 14 
Analysis of the CHSH game with observables. Tsirelson’s bound. The trace norm. Distinguishing two density matrices. Reduced density matrix. No signaling. Safe storage principle. No signaling vs. local realism. 
2.4.3, 2.6 

6.
Nov 21 
Gonen Krak: QKD and the LoChau protocol and proof. Gonen’s
slides. Richard
Cleve’s slides. The paper itself. Part II, Quantum algorithms: The
quantum circuit model. Uniformity. The class BQP. 
12.6.3, 12.6.5,
4.1 

7. Nov 28 
No class 


8. Dec 5 
Simulating
classical circuit by quantum circuits, effects of garbage. Deutsch's
algorithm, DeutschJozsa algorithm, The blackbox
model, Simon's algorithm. 
1.4, parts of: 3.2.33.2.5, 4.14.4, 4.5.5 

9. Dec 12 
The Fourier transform for Abelian groups. Efficient Fourier transform over (Z_2)^n and Z_(2^n). The Hidden subgroup problem. FFT and HSP. Discrete Log. 
5.1, 5.2, 5.4.2, 5.4.3, Appendix 2 

10. Dec 19 
Phase estimation.Cayley graphs.
Efficient Fourier transform over Z_k for any k.
Order finding, Shor'sfactoring
algorithm. 
5, Appendix 4 

11. Dec 26 
Grover’s algorithm. Estimating the number of solutions
using phase estimation. BBBV Lower bound on the OR function. 
6.1 

12. Jan 2 
A general lowerbound on quantum blackbox computation by
polynomials. Blackbox computation cannot provide more than a polynomial
speedup for total, Boolean functions. Purification. Schmidt
decomposition, impossibility of perfect bit commitment. 
6.7,
2.5 

13. Jan 9 
Fidelity. Some facts (without proof) about it. Coin
flipping. Ambainis’ ¾protocol. 
9.2.2 

14. Jan 16 
Strong extractors. Strong extractors with a single output
bit and error correcting codes (+ a statement of list decoding and the
Johnson’s bound). Quantumproof extractors. Konigterhal
generic result for one outputbit extractors. 
12.6.1,
12.6.2 

15. ??? 
Student presentations. 
