Physics
|
| Physics |
Hardware that exploits quantum phenomena can dramatically alter the nature of computation. Though constructing a working quantum computer remains a formidable technological challenge, there has been much recent experimental progress.
In addition, the theory of quantum computation is of interest in itself, offering new perspectives on the nature of computation and information, as well as providing novel insights into the conceptual puzzles posed by quantum theory.
The course is intended for physicists, unfamiliar with computational complexity theory or cryptography, and for computer scientists and mathematicians with some prior exposure to quantum mechanics. The prerequisites are an intro quantum mechanics course, familiarity (and comfort) with finite dimensional vector spaces over the complex numbers, and some standard group theory.
(If this seems too vague, please peruse a copy of the course text in the library to assess its accessibility. Notes on which the text was based are still available here.
The most recent previous syllabus is here: Fall 2014)
| Announcements: | |
| – 15 Nov | Let me know if you're interested in TA'ing for Info 2950 "Intro to Data Science" (Spr '17). Uses elementary probability and statistics, plus python programming. |
| – 17 Nov | Updated suggestions for course project, due anytime 8-15 Dec, preferably on the early side (under office door PSB 452, or via course upload site) |
Syllabus:
| Date | Lecture | Reading | |
|---|---|---|---|
| Week 1 | Tue 8/23 | 1. Intro | Begin with historical overview,
see, e.g.,
chapter 1 of Preskill notes, see also
The Feynman Lectures on Computation (Hey and Allen), and described topics in these (Aaronson) notes as goals for end of course. Some other popular expositions of reversible and quantum computing. A couple other popular refs mentioned (access from within Cornell network): The Fundamental Physical Limits of Computation (Bennett and Landauer, SciAm Jul 1985); Demons, Engines and the Second Law (Bennett, SciAm Nov 1987) Maxwell demon video and description |
| Thu 8/25 | 2. Cbits | Cover roughly pp 1-4 (1.1-1.2) of course text: intro, Cbits vs Qbits (For background on vector spaces and notation, see Appendix A of course text.) and pp 4-16 (1.2-1.4) of course text: reversible operations (inversion, swap, Cnot), Hadamard started coverage of Appendix B (to be completed next lecture) | |
| Week 2 | Tue 8/30 | 3. qubits I |
Discussion of direct (Kronecker) products, material from appendices A,B of text Covered pp 17-19 (1.5) states of Qbits, entanglement |
| Thu 9/1 | 4. qubits II |
More on SU(2)/Z2 as origin of fermions and bosons, 2d rotation group, half-wave plates, Hadamard as reflection about π/8,
continued entanglement discussion, then reversible operations on Qbits (1.6, pp. 19-20) Mentioned gate universality (see "The Solovay-Kitaev Algorithm" for technical review) | |
| Week 3 | Tue 9/6 | 5. Born again |
Covered pp 21-34 (1.7-1.11) of the course text: circuit diagrams,
measurement gates, Born rule, generalized Born rule, state preparation,
constructing arbitrary 1- and 2-Qbit states Started discussion of general computational process (2.1) |
| Thu 9/8 | 6. functions |
Discussed prob set 1 solutions (permutations, rotations, icosahedral qubit benchmarking, and the 120-cell) Covered pp. 34-42 (1.12-2.2): Cbit vs Qbit summary, functions, no-cloning and started Deutch's problem Problem Set 2 (due in class Tue 20 Sep 2016) | |
| Week 4 | Tue 9/13 | 7. quantum speed-up | Finished Deutch's problem (2.2, pp. 41-46),
mentioned Two Quadrillionth Bit of π is 0, then covered Bernstein-Vazirani problem (2.4, pp. 50-54, clarification of eq.(2.32) is here) See "pre-review" of algorithms to come (Deutsch -> Deutsch-Jozsa -> Bernstein-Vazirani -> Simon -> Shor; then Grover) |
| Thu 9/15 | 8. exponential speed-up | some comments on "Bell states" and maximal entanglement Simon's problem (2.5 and appendix G) [now halfway through standard algorithms] why additional Qbits don't mess things up, (2.3, pp 46-50) | |
| Week 5 | Tue 9/20 | 9. √X | Final comments on Simon's problem (see Appendix G of text) quantum Toffoli gates (2.6, pp 58-61) [stray comments on the Wason selection task], then quantum cakes (see also Appendix D on the Hardy state) |
| Thu 9/22 | 10. GHZ etc | appendix H, see fig 4 of arXiv:1402.4848 (also arXiv:1004.4324: fig 3c, arXiv:1004.4246: fig 1b), w-states, universal gate sets | |
| Week 6 | Tue 9/27 | 11. GHZ vs EPR | comments on measuring operators, quantum tomography, ipython notebook, discussion of GHZ states (6.5 in text) and how their measurement excludes "local reality", plus game theoretic version (a ⊕ b ⊕ c = r ∨ s ∨ t, where r,s,t ∈ {000, 011, 101, 110}); intro to group theory and modular arithmetic (App. I, then sec. 3.1) |
| Thu 9/29 | 12. FLT -> RSA | finish number theoretic preliminaries and Fermat's little theorem (3.2), RSA (3.3), then discussion of quantum period finding (3.4) (also mentioned "Wilson's Theorem", and "What is the probability that 29 Sep is Thursday"?) | |
| Week 7 | Tue 10/4 | 13. RSA -> QFT | Recalled Euclid's algorithm (appendix J, see also cs 2800 notes or pp 39-60 here), factoring (3.10), breaking RSA without factoring (3.3), continued quantum fourier transform (start of 3.5) |
| Thu 10/6 | 14. QFT and period finding | implementation (see also 3.5), eliminate 2-qubit gates (3.6), then finding the period (3.7) | |
| Week 8 | Tue 10/11 | fall break | |
| Thu 10/13 | 15. =3×5 | Some comments on RSA numbers (largest factored RSA number has 232 decimal digits, factored in late 2009), (google, the book, googol), how to factor N=15 (mentioned in probset 4 #6), finished (3.7) | |
| Week 9 | Tue 10/18 | 16. Other factors | See review of algorithms for Simon/Shor comparison,
finished finding factors (3.7-3.9), continued fractions (App. K), described adiabatic quantum computing and
qubit recycling. Also some factoring "records" discussed: Shor factoring: 3×5 ('01) (NMR), 3×5 ('07a) and 3×5 ('07b) (both photonic), 3×5 ('09) (photonic chip), 3×7 ('11) (photonic, with qubit recycling), 3×5 ('12) (superconducting) Adiabatic "factoring": 11×13 ('13), 233×241 ('14), (same 4 qubit experiment as 11×13), 499×401 ('16, D-wave) Pretend "factoring": N20000 ('13) (20000 bits = 6021 decimal digits, using compiled/recycled qubits), see Table 1 therein |
| Thu 10/20 | 17. Grover Search | Additional comments on N20000 and N==p*q Comments on D-Wave and quantum annealing (see most recent, and comments here; also this related overview) Finished comments on phases (3.9), modular exponent is O(n3), then Grover iteration (4.1-4.2) | |
| Week 10 | Tue 10/25 | 18. Grover Redux | Comments on recent 50 qubit "quantum supremacy": see 1608.00263 and popular related "Google's plan revealed" Finished Grover chpt 4, pp. 94-98 (4.3-4.5), generalization to several marked, one of four items, construction of W; see also pedagogical reviews: Grover's and Lavor et al.'s. Some comments on N1/2 optimality of Grover, and the N1/3 quantum collision algorithm. The optimality of Grover's algorithm is shown here, and implications here [Now finished the basic basic quantum algorithms.] |
| Thu 10/27 | 19. QKD | Comments on qudits and d-fold Toffoli, and experimental use of qutrit to speed up creation of a GHZ entangled state. Comments on quant-ph/9801041 (nonlinear QM solves NP-complete and #P problems, see also Aaronson, pp. 7-8) Covered quantum key distribution (6.2, 137-141) Some articles on quantum key distribution: ● Jul 2016 Chinese satellite (see also this news item) ● 2008 Quantum channel between Earth and Space (2 x 1485km, "boffins bounce photons", and this description) ● satellite quantum communications and 7000 km (2015, using satellite mirror) ● 2008 quantum repeater (and news article "Quantum cryptography can go the distance") ● 2011 quantum key distribution in Tokyo metropolitan area: 1103.3566, ● Entanglement based quantum communication over 144 km optical free-space link: quant-ph/0607182 (2006), 0902.2015 (2009) ● quantum key distribution over 184km optical fibre (2008), over 144km (2007) and 300km (2010) ● quant-ph/0607177: 1 Mbit/sec for 20km | |
| Week 11 | Tue 11/1 | 20. QEC I | Comments on no-go speedup for XOR/Parity
and OR 107 Bell pairs/sec for 10 photon entanglement (May '16); (unrelated) encoding 10 bits per photon (Sep '16) started quantum error correction, 5.1-5.3 (pp 99-113) |
| Thu 11/3 | 21. QEC II, teleportation | 5 qubit codes, 5.4-5.5 (pp 113-120) Noted that error correcting operator algebras can also be manipulated using python or matlab, e.g., this sample code. mentioned the 29:28--29:43 section in this video (J. Martinis talk at Google LA, Oct '13), with claim that "if you can be at a .1% error here, and make a few thousand qubits, you can hold a qubit state, this fragile quantum state, for the lifetime of the universe." [note that entire video is worth watching] Bell states (6.1), quantum teleportation (6.5, p.149-150) | |
| Week 12 | Tue 11/8 | 22. QEC III | Comments on course project, finished teleportation (6.5, p.151-154), 7-qubit code (5.6-5.7, p.121-126) Also mentioned this recent experimental review (See also Sympy Physics Module, specifically quantum computation). |
| Thu 11/10 | 23. QEC IV | discussed prob 7 of problem set 6, finished 5.7 (CNOT in 7-qubit code), then surface code (see arXiv:1208.0928, sections II-VI, pp.3-10) | |
| Week 13 | Tue 11/15 | 24. surface codes, hidden variables | B92 protocol more on surface code (arXiv:1208.0928 sections VIII, XIII, XIV, see especially pp 29-30, XIV C,D for CNOT), Quantum dense coding (6.4), last words for hidden variables, see fig. 3 (Mermin, 1993) |
| Thu 11/17 | 25. Occult pentagon, experimental overview | Finished Mermin (1993) argument (fig 4). See Aspect overview (Dec '15) of three experiments closing all the loopholes simultaneously: 1508.05949, 1511.03189, 1511.03190 (plus this year's 1611.04604) Discussed quantum computing with trapped ions (see Nielsen/Chuang section 7.6, pp. 309-324, or more recent reviews: here or 0809.4368). For recent progress, see viewpoint on 1403.1524; or 1602.02840; or this overview of 1603.04512, or this popularization: Monroe/Wineland (Sci. Am., 2008). | |
| Week 14 | Tue 11/22 | 26. Trapped ions, nmr | more discussion of E91 protocol in probset7 #7, lower limit on "speed" of spooky influence [0808.3316] (and info can't be transmitted, same argument as App.P p.216 in course text), monogamy of entanglement and firewall paradox (see pp. 49-54 in Aaaronson notes). Continued discussion of CNOT gates for trapped ions, then started NMR (see Nielsen/Chuang section 7.7, pp. 324-342, or this recent review: 1501.01353) |
| Thu 11/24 | Thanksgiving | ||
| Week 15 | Mon 11/28 | Zeilinger Lecture, 4p.m. | "Quantum Communication with Entangled Photons", Schwartz Auditorium, Rockefeller Hall (some refs) |
| Tue 11/29 | Zeilinger Lecture, 4p.m. [no class] | "Quantum Entanglement in Higher Dimensions", 700 Clark Hall (some refs) | |
| Wed 11/30 | Zeilinger Public Lecture, 7:30p.m. | "From Quantum Puzzles to Quantum Information Technology", Schwartz Auditorium, Rockefeller Hall (some refs) | |
| Thu 12/1 | 27. transmons, BQP, and all that | Comments on "Verschränkung" vs. spaghetti, and "Spukhafte Fernwirkung" (from Zeilinger). From here: latest microsoft hires, possible polynomial time algorithm for variant of CVP (alas already withdrawn). Mentioned "Quantum Algorithm Zoo": compendium of quantum algorithms. Clarified some remaining aspects of NMR quantum computing from lec. 26. Then superconducting qubits: overview, Martinis notes on CNOT (see also recent comprehensive review, and references therein). Complexity Zoo: Some parting comments on P, NP, et al. and BQP et al., also P vs. NP, and 3-SAT (see also Preskill notes chpt 6, pp. 5-10, 22-24, 26-28, chapts 6-10 of "Quantum Computing since Democritus", and the abbreviated Petting Zoo). |
Course Topics:
1. A quick review of quantum mechanics, simplified by focus on relevant applications (i.e., measurement, not dynamics)
2. Some simple, if artificial, quantum algorithms that are surprisingly more efficient than their classical counterparts
3. Shor's super-efficient period finding (factoring) algorithm and and its threat to cryptographic security
4. Grover's efficient search algorithm
5. Quantum error correction
6. Other forms of quantum information processing and conundra: quantum cryptography; superdense coding; teleportation; applications of Bell's theorem; firewalls; AdS/cft
7. Experimental realizations (xmons, ions, vacancies, annealers, ...)
Academic integrity policy:
You are expected to abide by the
Cornell University Code of Academic Integrity.
(In particular, the work you submit for course assignments must be your own.
You may discuss homework assignments with other students at a high
level, by for example discussing general methods or strategies to
solve a problem, but you must cite the other student in your submission.
Any work you submit must be your own understanding of the solution,
the details of which you personally and individually worked out, and
written in your own words.)