Computer Science
|
0368.4057
|
Fall 2005
|
| Lectures |
Thursday 12:00-15:00, Dan David 110 |
| Instructors |
Amnon Ta-Shma | 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 quant-ph, a repository for all quantum-related 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, 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 |