Computer Science Tel-Aviv University

0368.4057 Quantum computation 1

Spring 2012

[11/03/12]: An old exercise on tensors, Solution .

[12/03/2012] Exercise set 1 Figures Solution

[26/03/2012] Exercise set 2 Solution

[21/05/2012] Exercise set 3 Solution

[04/06/2012] Exercise set 4

[13/06/2012] Exercise set 5

[12/06/2012] Suggested projects

[19/07/2012] HW grades are available

Exam for example

---

Some Information

Lectures	Mon 10:10-13:00, Melamed
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)
1. March 5	One qubit, tensor products, two qubits, pure states, unitary matrices, X, Y, Z, CNOT, HAD. No cloning theorem.	Lecture 1
2. March 12	Entanglement, superdense coding, Quantum teleporation. The CHSH game (and Bell inequalities).	Lecture 2
3. March 19	Tsirelson’s bound. More on measurements. Every physical test can be captured by a POVM and vice versa. The density matrix.	Lecture 3
4. March 26	The density matrix. Distinguishing two density matrices. Reduced density matrix. No signaling. Safe storage principle.	Lecture 4
5. April 2	No signaling vs. local realisim. Simulating classical circuit by quantum circuits, effects of garbage. Deutsch's algorithm, Deutsch-Jozsa algorithm, The black-box model, Simon's algorithm.	Lecture 5
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	Lecture 6
7. April 23	Efficient quantum algorithm for FFT over Z_(2^n). Phase estimation. (based on [Watrous, Lectures 8 and 9]). Cayley graphs.	Lecture 7
8. April 30	Efficient quantum algorithm for FFT over Z_p. Period finding, Order finding, Shor's factoring algorithm.	Lecture 8
9. May 7	Grover’s algorithm. Estimating the number of solutions using phase estimation.	Lecture 9
10. May 14	BBBV Lower bound on the OR function. 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. Communication complexity, log-rank lower bound. Quantum communication protocol for the DISJ problem.	Lecture 10
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.	Lecture 11
12. May 28	RAC, a lower bound on on n->m RAC, an application to 2-local decoding of classical ECC.	Lecture 12
13. June 4	Schmidt decomposition, impossibility of perfect bit commitment, fidelity, , impossibility of imperfect bit commitment, coin flipping.	Lecture 13
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 pre-shared PR-boxes are available.	Lecture 14
15. June 18	Quantum error correcting codes. Shor’s [9,1,1] code. CSS codes. Steane’s [7,1,1,] code.	Lecture 15