Computer Science
Tel-Aviv University

Quantum Computing

Fall 2005
Spring 2006


Lecture notes


Ideas for Projects

Some Information


Thursday 12:00-15:00, Dan David 110

Amnon Ta-Shma | Schreiber 127 | 5364
Oded Regev | Schreiber 220 | 5379

Quantum Computation and Quantum Information, M. Nielsen, I. Chuang
Classical and Quantum Computation, A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi
Lecture notes on the web Topics in Quantum Information, by Ashwin Nayak.
Quantum Computation, by John Preskill. More lecture notes on his page.
Quantum Computation, by Umesh Vazirani.
Our course announcement
Some interesting blogs by Michael Nielsen, Dave Bacon
quant-ph, a repository for all quantum-related research papers



Class Topic
Nov 3 One qubit, two qubits, pure states, unitary matrices, X, Y, Z, CNOT, CNOT does not duplicate a qubit (2 hours)
Nov 10 Some more math (Dirac's bra/ket notation, tensors), Quantum teleporation, measurements in other bases, superdense coding
Nov 17 EPR and Bell inequalities, simulating classical circuit by quantum circuits, effects of garbage, Deutsch's algorithm
Nov 24 The Fourier transform over Z_2^n, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm, Simon's algorithm
Dec 1 More on BQP, RSA, Fourier transform over Z_N and the QFT circuit
Dec 8 Period finding, Order finding, Shor's factoring algorithm
Dec 15 Discrete Log, Phase estimation
Dec 22 Universal gates
Dec 29 The black-box model. BBBV lower bound for the OR function. Grover’s box
Jan 5 Estimating the number of solutions using phase estimation. A general lower-bound on quantum black-box computation by polynomials. Black-box computation can not provide more than a polynomial speedup for total, Boolean functions
Jan 12 A sqrt(n) quantum communication protocol for the disjointness function
Jan 19 Density matrices. Every physical test can be captured by a POVM and vice versa.
Jan 26 The trace norm is a norm. Distinguishing two density matrices. No classical (weak) coin flipping. Ambainis's protocol (proving the case where Bob cheats).
Feb 2 The singular value decomposition. Schmidt decomposition. Purifications. Fidelity.
Mar 5 Fidelity and other distance measures, relations among them. Bit commitement.
Mar 12 Ambainis's coin tossing protocol (complete proof), and tightness.
Mar 19 Weak coin flipping protocol
Mar 26 Quantum communication complexity lower bounds for Inner Product and Disjointness
Apr 2 The class QMA and amplification
Apr 23 Witness-preserving amplification (Marriott-Watrous)
Apr 30 An application of witness-preserving amplification, Group Non-Membership in QMA
May 7 QMA-complete problems
May 14 QMA-complete problems
May 21 Perfect completeness for IP[k]. Perfect completeness for QIP[k] for k >2.
May 28 MA is in AM. QIP = QIP[3]
Jun 4 Super-operators, l_1 norm for super-operators, diamond norm, characterizing the acceptance probability of QIP[3] by the diamond norm of a super-operator determined by the verifier's actions
Jun 11 Amplificiation of QIP[3], QIP is in EXP