Computer Science
|
0368.4057
|
|
Span
programs and quantum query complexity: The general adversary bound is nearly
tight for every boolean
function. B. Reichardt.
Proc.
FOCS 2009, Extended abstract,
Full version: quant-ph/0904.2759,
2009. slides
|
Lectures |
Thursday, 10:10-13:00, ëéúä 125 áðééï ùàôì |
||
|
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 |
||
|
Grading policy |
Homework is mandatory, Exam (mandatory for undergrad)
and/or paper presentation/ project |
||
Lecture
notes on the web
|
|
||
Links
|
quant-ph, a repository for all quantum-related research papers |
|
Date |
Class Topic |
Lercture notes (in Hebrew) |
Chapters in Nielsen and Chuang |
|
1. Oct 17 |
Nature as computation. Classical computation. One qubit, X, Y, Z, HAD. Many qubits. Tensor products, two qubits, CNOT. The two-slit experiment. Projection measurements. |
1.1,
1.2, 1.3.1-1.3.4, 1.5.1, 2.1.7, 2.2.1, 2.2.3-2.2.5 |
|
|
2. Oct 24 |
The quantum world. Superdense coding, Quantum teleporation. Entanglement.
No cloning theorem. |
1.3.5-1.3.7, 2.3 |
|
|
3. Oct 31 |
General measurements. POVM. Every
physical test can be captured by a POVM and vice versa. The density matrix. |
2.2-2.6, 2.4.1, 2.4.2 |
|
|
4. Nov 7 |
More on density matrices.
Measurements, POVMs and observables. The
CHSH game (and Bell inequalities). A quote: Bell expressed his hope
that such work would "continue to inspire those who suspect that what is
proved by the impossibility proofs is lack of imagination." |
2.6 |
|
|
5. Nov 14 |
Analysis of the CHSH game with observables. Tsirelson’s bound. The trace norm. Distinguishing two density matrices. Reduced density matrix. No signaling. Safe storage principle. No signaling vs. local realism. |
2.4.3, 2.6 |
|
|
6.
Nov 21 |
Gonen Krak: QKD and the Lo-Chau protocol and proof. Gonen’s
slides. Richard
Cleve’s slides. The paper itself. Part II, Quantum algorithms: The
quantum circuit model. Uniformity. The class BQP. |
12.6.3, 12.6.5,
4.1 |
|
|
7. Nov 28 |
No class |
|
|
|
8. Dec 5 |
Simulating
classical circuit by quantum circuits, effects of garbage. Deutsch's
algorithm, Deutsch-Jozsa algorithm, The black-box
model, Simon's algorithm. |
1.4, parts of: 3.2.3-3.2.5, 4.1-4.4, 4.5.5 |
|
|
9. Dec 12 |
The Fourier transform for Abelian groups. Efficient Fourier transform over (Z_2)^n and Z_(2^n). The Hidden subgroup problem. FFT and HSP. Discrete Log. |
5.1, 5.2, 5.4.2, 5.4.3, Appendix 2 |
|
|
10. Dec 19 |
Phase estimation.Cayley graphs.
Efficient Fourier transform over Z_k for any k.
Order finding, Shor'sfactoring
algorithm. |
5, Appendix 4 |
|
|
11. Dec 26 |
Grover’s algorithm. Estimating the number of solutions
using phase estimation. BBBV Lower bound on the OR function. |
6.1 |
|
|
12. Jan 2 |
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. Purification. Schmidt
decomposition, impossibility of perfect bit commitment. |
6.7,
2.5 |
|
|
13. Jan 9 |
Fidelity. Some facts (without proof) about it. Coin
flipping. Ambainis’ ¾-protocol. |
9.2.2 |
|
|
14. Jan 16 |
Strong extractors. Strong extractors with a single output
bit and error correcting codes (+ a statement of list decoding and the
Johnson’s bound). Quantum-proof extractors. Konig-terhal
generic result for one output-bit extractors. |
12.6.1,
12.6.2 |
|
|
15. ??? |
Student presentations. |
|