Computer Science

0368.4057

Fall 2005

Lectures 
Thursday 12:0015:00, Dan David 110 
Instructors 
Amnon TaShma  Schreiber 127  5364 Oded Regev  Schreiber 220  5379 
Textbooks 
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. 
Links 
Our course announcement Some interesting blogs by Michael Nielsen, Dave Bacon quantph, a repository for all quantumrelated research papers 
Date  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, DeutschJozsa algorithm, BernsteinVazirani 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 blackbox model. BBBV lower bound for the OR function. Grover’s box 
Jan 5  Estimating the number of solutions using phase estimation. A general lowerbound on quantum blackbox computation by polynomials. Blackbox 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  Witnesspreserving amplification (MarriottWatrous) 
Apr 30  An application of witnesspreserving amplification, Group NonMembership in QMA 
May 7  QMAcomplete problems 
May 14  QMAcomplete 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  Superoperators, l_1 norm for superoperators, diamond norm, characterizing the acceptance probability of QIP[3] by the diamond norm of a superoperator determined by the verifier's actions 
Jun 11  Amplificiation of QIP[3], QIP is in EXP 