Computer Science
Tel-Aviv University

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


Mon 10:10-13:00, Melamed


Amnon Ta-Shma | Schreiber 127 | 5364

Open to

Undergrad and grad students from CS or Physics.


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.


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


Classes so far


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