Physics
|
| Physics |
Hardware that exploits quantum phenomena can dramatically alter the
nature of computation. Though constructing a general purpose 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.
This course is intended for physicists, unfamiliar with computational
complexity theory or cryptography, and for computer scientists and
mathematicians less familiar with quantum mechanics.
Topics
include: simple quantum algorithms, error correction, cryptography,
teleportation, and uses of quantum computing devices either currently
available or to be available in the near future.
The prerequisites are a prior course in linear algebra conveying familiarity (and comfort) with finite dimensional vector spaces over the complex numbers, python programming, some standard group theory is required, and a prior course in quantum mechanics (such as PHYS 3316 or AEP 3610 ) is useful.
(If this seems too vague, please peruse the above Aaronson lecture notes to assess their accessibility.
The most recent previous syllabus is here: Fall 2021; but
with the new intro course AEP 3100 in the spring this course will probably operate at a hgher level and cover more material than in the past.)
| Announcements: |
Syllabus:
| Date | Lecture | Reading | ||
|---|---|---|---|---|
| Week 1 | Tue 8/23 | 1. Intro | lec1_slides Began with historical overview of past 100 years (including 'qubit' origin story), mentioned NISQ (Preskill: 1801.00862), and updated 2208.08064 ("Physics of Quantum Information" -- please read), as well as 7 qubit and 25 qubit surface codes, and recent possible progress in topological quantum computing (see also excess hype?). Will continue next time with some combination of Mermin chpt1 and Aaronson lectures 1,2 | |
| Thu 8/25 | 2. Cbits |
Mentioned 2208.09964 (P. Shor on "The Early Days ..."), Covered roughly pp 8-14 (1.3-1.4) from Chpt1 of Mermin text: reversible operations (inversion, swap, cNOT), Hadamard (See also Mermin appendix A for "Vector spaces: basic properties and Dirac notation") Elective material: Recent refs describing experimental verification of Landauer principle: • Viewpoint (May 2018) describing pure quantum verification (M.Feng et al, 2018, [1803.10424]); also mentions recent classical tests (Y. Jun et al (2014), [1408.5089]; and E. Lutz et al (2012)), plus contemporaneous News and Views re the latter A couple of popular refs I mentioned: • The Fundamental Physical Limits of Computation (Bennett and Landauer, SciAm Jul 1985); • Demons, Engines and the Second Law (Bennett, SciAm Nov 1987) Some other popular expositions: • reversible and quantum computing. • Maxwell demon video and description | ||
| Week 2 | Tue 8/30 | 3. gates | Continued Mermin sec 1.4: recalled cNOT, introduced Z, CZ, Y, and the Hadamard H. plus some comments about half-wave plates, Hadamard as reflection about π / 8, and the Brougham/Broome bridge. Started Mermin appendix B on Pauli σ algebra and SO(3)=SU(2)/Z2 (See also Mermin appendix A for "Vector spaces: basic properties and Dirac notation"). | |
| Thu 9/1 | 4. qubits and states |
Continued discussion of Mermin app.B, plus some discussion of fermions/bosons (to be continued lec5). Additional discussion of cNOT, Hadamard, then covered Born rule (Mermin 1.8), and direct product vs entangled states (mermin 1.5), including parameter counting (two real parameters for each of 2n complex parameters, reduced by one due to the normalization constraint, and another by the unmeasurable global phase), plus further discussion of entanglement (see these notes for discussion of SVD criterion for whether two subsystems are entangled). concluded with comments on Bell states (also to be continued lec5) | ||
| Week 3 | Tue 9/6 | 5. Born rule |
Mentioned ps0 comments Discussed dual vectors, bras and kets, matrix elements, measuring gates, properties of SU(2), then Born and generalized Born rules (continuing chpt1 of mermin) Here are some relevant zoom era whiteboards written in real-time on a tablet. See the Ed discussion site for significant additional posted resources | |
| Thu 9/8 | 6. Born again |
Began with more examples of 2d unitaries and 3d rotations, discussed √X in terms of the S operator, Mentioned universal gate sets (Aaronson 16.2, and see "The Solovay-Kitaev Algorithm" for technical review), difference between superposition and classical mixture (Mermin sec 1.8, p. 27) generalized Born Rule (Mermin 1.9) More on Bell states (See Aaronson 5.3.2) | ||
| Week 4 | Tue 9/13 | 7. QKD |
demo'd Ry(-π/2)Rx(-π/2) = Rn(-2π/3) with n=(1,1,1)/√3 more on H,T universality from standpoint of platonic solids (for practical implications, see also icosahedral qubit benchmarking) no-cloning (A 7.2; M2.1[p.39-40]), quantum key distribution (A 8.2; M 6.2) | |
| Thu 9/15 | 8. Computation |
Began with extended discussion of ps2#5 and Bloch Sphere (see also interactive demo). remarks on Hedy Lamarr Quantum Communication Telescope, finished QKD (Mermin 6.2, and the QKD wikipedia entry has an overview of experimental implementations, including over 144km in the Canary Islands (2007), 307km optical fiber (2015), 1203km via satellite (2017), and a list of existing distribution networks) Started general computational process (M 2.1) | ||
| Week 5 | Tue 9/20 | 9. n-bit → 1-bit |
mentioned 2209.06930 (Aaronson: "How Much Structure Is Needed for Huge Quantum Speedups?") more on functions (M2.1, A17.1) covered Deutsch's problem (1 bit to 1 bit functions, M2.2, A17.3) and its Deutsch-Jozsa generalization (A17.4) started Bernstein-Vazirani problem (n bit to 1 bit function of the form f(x)=a·x, M2.4; A18.1) see also Qiskit: Phase Kickback, Deutsch-Jozsa Algorithm, Bernstein-Vazirani Algorithm | |
| Thu 9/22 | 10. B-V→Simons |
finished Bernstein-Vazarani f(x)=a·x (M2.4; A18.1) then Simon's problem f(x) = f(x⊕a) (M2.5, A18.2, and qiskit Simon's algorithm) Mentioned this video Straight From the Source (Peter Shor) describing how Simon's algorithm led to Shor's (See also comments from Daniel Simon) and did (misleading?) demo of "birthday paradox" | ||
| Week 6 | Tue 9/27 | 11. Simons→Toffoli |
Simon's problem (M2.5 and appendix G) [now halfway through standard algorithms] [see M app.G for "example of the purely mathematical postprocessing frequently necessary after the quantum algorithm returns its probabilistic results"] why additional Qbits don't mess things up (M2.3, pp 46-50); quantum garbage collection (A17.2) quantum Toffoli gates (M2.6, pp 58-61) | |
| Thu 9/29 | 12. Toffoli→Bell |
Completed construction of quantum Toffoli gates (M2.6) Discussed the CHSH game (A13.2, A14.1, though feel encouraged to read all of A13,A14), then started the GHZ game (M6.6) | ||
| Week 7 | Tue 10/4 | 13. Bell→GHZ |
Mentioned Aspect/Clauser/Zeilinger Nobel Prize ("for Work Exploring Quantum Weirdness" discussed in part Lecs 12,13), and current GHZ27 record (arXiv:2101.08946) Reprised CHSH game (A13.2, A14.1), measurements in different bases, and these videos comparing a few different 1-qubit strategies using measurements along any axis (i.e., not just X,Y,Z; and with different strategies for choosing them) Completed discussion of the "GHZ game" and implications (M6.6), see also lec13_notes | |
| Thu 10/6 | 14. RSA→QFT |
Set up the period finding problem (M 3.1, 3.4) Discussed relation between periods and factoring (M 3.10), started discussion of RSA encryption (M 3.2, 3.3; A 19.1), mentioned of RSA_numbers, specifically 768 | 232 (Feb 2010), 795 | 240 (Dec 2019), 829 | 250 (Feb 2020), and the Die Hard 3 Water Jug problem More next time on 1905.09749 ("How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits") and Quantum Moore's Law (things happen from 2028-2042, derived from 1710.10377) | ||
| Week 8 | Tue 10/11 | Fall Break | ||
| Thu 10/13 | 15. IBM,QFT |
Demoed the qiskit circuit composer (GHZ states, Xθ operators, etc), see this notebook for examples of extracting data. mentioned 1612.00858 ("Efficient Z-Gates for Quantum Computing") further explained these videos continued quantum fourier transform and period finding (parts of sections M 3.4, 3.5, 3.7; see also A19.2, A20, Bloch sphere (A 7.1), and visualizations in Fourier basis (qiskit)) | ||
| Week 9 | Tue 10/18 | 16. QFT intuition |
Recalled derivation of p(y) (M 3.7), and relation to diffraction grating (where d/λ ~ r/2n) Returned to explanation of Fourier Basis, then the Quantum Fourier Transform (see also A 20.1.1). started implementation | |
| Thu 10/20 | 17. O(n2) |
continued QFT implementation, showing
circuit diagram with quadratic growth in number of gates, and additional simplifications: eliminate 2-qubit gates (M 3.6), unimportance of small phase errors (M 3.9), and qubit recycling
(experimental implementation: arXiv:1111.4147;
for more on "recycling qubits", see e.g.,
quant-ph/9903071,
quant-ph/0001066,
quant-ph/0601097,
1301.7007) mentioned modular exponent is O(n3) finished with lec17_RSA.ipynb notebook | ||
| Week 10 | Tue 10/25 | 18. Shor's algorithm details |
Discussed efficient circuit for modular exponent Uf (M 3.8), explained why using twice the number of input registers as output registers permits extracting j/r from y/2n using continued fractions (M 3.7), and gives a > 40% probablity of measuring an integer close enough to the peak for this, mentioned Fermat primes, then covered how to factor N=15 (though using n=no rather than n=2no as in those notes), mentioned fractions and partial sums (A 21, M app_K), unimportance of small phase errors (M 3.9), Recalled 1905.09749 ("How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits") from lec14 Some factoring "records" (with some exaggerated...): ● 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) ● Variational Quantum Factoring: 1,099,551,473,989=1,048,589×1,048,601 ● Pretend "factoring": N20000 ('13) (arXiv:1301.7007, 20000 bits = 6021 decimal digits, using compiled/recycled qubits), see Table 1 therein Started Grover's algorithm (M 4.1, A 22.1.1, qiskit 3.8) | |
| Thu 10/27 | 19. Grover |
Some comments on P vs NP (A 22.0, 24.3) Continued Grover's Algorithm (M chp4, A 22.1.1-22.1.4, qiskit 3.8, see also pedagogical reviews: Grover's and Lavor et al.'s), including multiple marked states, and special case one of four items. | ||
| Week 11 | Tue 11/1 | 20. Grover → teleportation |
Construction of W (M 4.3; A 22.1.1-22.1.4) Some comments on N1/2 optimality of Grover (A 23.1), and the N1/3 quantum collision algorithm (A 24.1) (The optimality of Grover's algorithm is shown here, and implications here) Comments on no-go speedup for XOR/Parity (A 24.2) and OR (see also A 23.2) [Now finished the basic basic quantum algorithms.] Started quantum teleportation (M 6.5; A 10.1; qiskit 3.11) -- note this fun historical account, and experimental implementation (from 1997). | |
| Thu 11/3 | 21. teleportation -> QEC |
Circuit diagram interpretation of teleportation (M 6.5), teleportation of entanglement (A 10.1, see fig 10.3), Discussed decoherence due to environment (M 5.1), referred to fig. 2 and table 1 of 1905.13641 for recent data on superconducting flux qubit coherence times and gate fidelities. Started quantum error correction (A 27.1-27.2), qiskit 5.1, 3-qubit bit-flip code (M 5.1-5.2) | ||
| Week 12 | Tue 11/8 | 22. QEC I: stabilizers -> 5-qubit code |
Continued discussion of decoherence, mentioned again 1905.09749 in the context of error correction Stabilizer interpretation of 3-qubit bitflip correction code (M 5.2), then general form of single qubit errors (M 5.3, A 27.2, qiskit 5.1) Introduced measurement of operators (M 5.4), then started the 5-qubit error correction code (M 5.5) see 1907.04507 (2019) for recent superconducting qubit implementation of 5-qubit error-correcting code (and see NMR implementation from 2001) | |
| Thu 11/10 | 23. QEC II: 5-qubit code |
Mentioned (intentionally outdated) vendor roadmaps and difficulties realizing error correcting codes with current qubit fidelities Commuting operator measurements (M 5.4), then Finished 5 qubit code (M 5.5), note that error correcting operator algebras can also be manipulated using python or matlab, e.g., this sample code. See Gottesman (2009) for a (slightly, but not extremely, technical) review of stabilizer formalism and fault tolerance. | ||
| Week 13 | Tue 11/15 | 24. QEC III: 7-qubit → surface |
Mentioned Quantum Zeno, Watched Pot, Elitzur-Vaidman bomb (A 4.3, 4.4) then 7-qubit code (M 5.6-5.8, p.121-127), including verification of composite Hadamard 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] Then started the surface code, see arXiv:1208.0928, sections II-VI, pp.3-10, and mentioned 1912.09410 (experimental realization of small section of surface code: 4 data qubits and 3 measure qubits), and more recently 2207.06431 (25 data qubits and 24 measure qubits) | |
| Thu 11/17 | 25. surface → experiment |
Finished multiqubit errors (M 5.6) and composite cNOT operators (M 5.7) in 7-qubit code More on surface code: data/measure/logical qubits and operators -- see arXiv:1208.0928, then discussed the recent experimental realization of truncated 7-qubit surface code in 1912.09410 (extending the coherence time of a logical qubit). see notes | ||
| Week 14 | Tue 11/22 | 26. QC Hardware |
Guest lecture from Peter McMahon (AEP) on Hardware state of the art Discussed practical challenges, metrics of "goodness" (e.g. quantum volume), hardware players and comparisons, vendor roadmaps, connectivities. then example application of VQE (= variational quantum eigensolver), see, e.g., review See also: sampling (2019) (53 qubit), sampling (2021) (60 qubit), VQE (12 qubit Hartree-Fock for H12), dynamics (16 qubit), dynamics (18 qubit), QAOA (23 qubit), scrambling (53 qubit), time crystals (20 qubit) See Appendix A for tables in this review of NISQ algorithms | |
| Thu 11/24 | Thanksgiving | break | ||
| Week 15 | Tue 11/29 | 27. surface → adiabatic | More on surface code: operators, more qubits -- see arXiv:1208.0928,
also sections VIII, XIII, XIV therein, see especially pp 29-30, XIV C,D for CNOT; then covered more of the recent experimental realization of truncated 7-qubit surface code in 1912.09410 (extending the coherence time of a logical qubit). Finished with Hamiltonians (A 25) and Adiabatic Algorithm (A26) | |
| Thu 12/1 | 28. BQP et al. |
Continued discussion of computational complexity (A 23), see also P, NP, et al. and
BQP et al.; then
P vs. NP, and
3-SAT (as well as Preskill notes chpt 6, pp. 5-10, 22-24, 26-28, chapts 6-10 of "Quantum Computing since Democritus", Complexity Zoo, and abbreviated Petting Zoo). Mentioned "Quantum Algorithm Zoo": compendium of quantum algorithms. |
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, ...)
8. Use of available on-line quantum cloud resources
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.)