Computer Science
Tel-Aviv University

0368.4057
Quantum computation 1


Spring 2012

 

The class was moved to 125

Suggestions for a project (for a group of students):

1.     The (commutative) Quantum Lovasz Local Lemma. Link.

2.     The Adversary method for obtaining Black-box lower bounds:

https://www.math.uwaterloo.ca/~amchilds/teaching/w11/l18.pdf

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: quant-ph/0904.2759, 2009. slides

3.     Quantum-proof extractors.

Konig & Terhals paper: http://authors.library.caltech.edu/9660/1/KOEieeetit08.pdf

Trevisan's extractor in the presence of quantum side information, Vidick, De, Portmann, renner

 

[24/10/2013]: An old exercise on tensors, Solution .

[Out: 24/10/2013, Due:21/11/2013] Exercise set 1 Figures

[Out: 6/11/2013, Due:5/12/2013] Exercise set 2

[Out: 17/12/2013, Due:9/1/2014] Exercise set 3 Figure

[Out: 8/1/2014, Due:23/1/2014] Exercise set 4

 


Some Information

Lectures

Thursday, 10:10-13:00, 125

Instructors

Amnon Ta-Shma | Schreiber 127 | 5364

Open to

Undergrad and grad students from CS or Physics.

Textbooks

Quantum Computation and Quantum Information, M. Nielsen, I. Chuang 
Classical and Quantum Computation, A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi

Grading policy

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

Lecture notes on the web

Topics in Quantum Information, by Ashwin Nayak. 
Lecture notes, by John Preskill. More lecture notes on his page.
Quantum Computation, by Umesh Vazirani.
 

Quantum Information and Computation, by John Watrous.

Links

quant-ph, a repository for all quantum-related research papers

C

Classes so far

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 two-slit experiment. Projection measurements.

Lecture 1

1.1, 1.2, 1.3.1-1.3.4, 1.5.1, 2.1.7, 2.2.1, 2.2.3-2.2.5

2. Oct 24

The quantum world. Superdense coding, Quantum teleporation. Entanglement. No cloning theorem.

Lecture 2

1.3.5-1.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.

 

Lecture 3

2.2-2.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."

Lecture 4

2.6

5. Nov 14

Analysis of the CHSH game with observables. Tsirelsons bound. The trace norm. Distinguishing two density matrices. Reduced density matrix. No signaling. Safe storage principle. No signaling vs. local realism.

 

 

Lecture 5

2.4.3, 2.6

6. Nov 21

Gonen Krak: QKD and the Lo-Chau protocol and proof. Gonens slides. Richard Cleves slides. The paper itself.

 

Part II, Quantum algorithms: The quantum circuit model. Uniformity. The class BQP.

Gonen's ppt

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, Deutsch-Jozsa algorithm, The black-box model, Simon's algorithm.

Lecture 7

1.4, parts of: 3.2.3-3.2.5, 4.1-4.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.

Lecture 8

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.

Lecture 9

5, Appendix 4

11. Dec 26

Grovers algorithm. Estimating the number of solutions using phase estimation. BBBV Lower bound on the OR function. 

Lecture 10

Lecture 10b

6.1

12. Jan 2

A general lower-bound on quantum black-box computation by polynomials. Black-box computation cannot provide more than a polynomial speedup for total, Boolean functions. Purification. Schmidt decomposition, impossibility of perfect bit commitment.

Lecture 11

6.7, 2.5

Watrous' class on Quantum bit commitment

13. Jan 9

Fidelity. Some facts (without proof) about it. Coin flipping. Ambainis -protocol.

Lecture 12

 

9.2.2

The work of Ambainis

 

14. Jan 16

Strong extractors. Strong extractors with a single output bit and error correcting codes (+ a statement of list decoding and the Johnsons bound). Quantum-proof extractors. Konig-terhal generic result for one output-bit extractors.

Lecture 13

 

12.6.1, 12.6.2

Konig-Terhal

 

15. ???

Student presentations.