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, and some standard group theory is required. A prior course in quantum mechanics (such as PHYS 3316 or AEP 3610 ) is useful (though not required for the fall '21 version of the course).
(If this seems too vague, please peruse the above Aaronson lecture notes to assess their accessibility.
The most recent previous syllabus is here: Fall 2020; but
with the dropped Quantum Mechanics prereq this fall's course will focus instead on a combination of the first two resources above.)
| Announcements: |
Syllabus:
| Date | Lecture | Reading | |
|---|---|---|---|
| Week 1 | Thu 8/26 | 1. Intro | Whiteboards are here: lec1_wb Began with historical overview (including 'qubit' origin story), mentioned NISQ (Preskill: 1801.00862 -- please read this one, still relevant), and recent "MIP*=RE" (2001.04383 -- somewhat beyond the purview of this class) Had planed to cover Aaronson notes lec1 (very short) and parts of lec2, but now aiming for at least all of lecs 1-3 next week (wouldn't hurt for everyone to browse through them in advance). |
| Week 2 | Tue 8/31 | 2. Probabilities and Amplitudes | Whiteboards are here: lec2_wb Covered roughly Aaronson Lecs 1,2, and section 3.1 (See also Mermin appendix A for "Vector spaces: basic properties and Dirac notation"). On Thu, should be able to cover rest of Lec 3, sections 4.1, 4.2, and a Jupyter notebook to set up ps1 (to be issued Thu or Fri). |
| Thu 9/2 | 3. Operators |
Whiteboards are here: lec3_wb Comments about ps0, covered Aaronson Lec 3, plus some comments about half-wave plates, Hadamard as reflection about π / 8, and the Brougham/Broome bridge. ps1 will be out tomorrow (Fri) | |
| Week 3 | Tue 9/7 | 4. multi-qubit spaces |
Whiteboards are here: lec4_wb Discussed ps1, covered Aaronson notes roughly sections 4.2, 5.3.1, first part of 5.3.2. Finished with notebooks ps0_supp.ipynb and ps1_supp.ipynb A couple of popular refs I 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) Some other popular expositions: • reversible and quantum computing. • Relation between info, heat, and work: Maxwell demon video and description |
| Thu 9/9 | 5. measurements |
Whiteboards are here: lec5_wb Started with review of 2d rotation/reflections (for ps1#4), global phase (Aaronson 3.3.1), 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), brief discussion of Google's 2019 "quantum supremacy" experiment (for non-technical overview see accompanying news and news&views; for more technical details see supplementary material), measuring in another basis (A 4.1.1), operator table (A table 4.1), generalized Born rule (A 5.3) | |
| Week 4 | Tue 9/14 | 6. general properties, QKD |
Whiteboards are here: lec6_wb more examples of generalized born rule, then entanglement (A 5.3.2), no-cloning (A 7.2), general properties (A 4.1.2), quantum key distribution (A 8.2) |
| Thu 9/16 | 7. SU(2)/QKD/GKZ |
Whiteboards are here: lec7_wb Covered SU(2) rotations (problem 3 of ps1) with in-class demo, remarks on Hedy Lamarr Quantum Communication Telescope, finished QKD, then started GHZ game (see related parts of A 13, 14 on the CHSH game) | |
| Week 5 | Tue 9/21 | 8. GHZ/IBM/functions |
Whiteboards are here: lec8_wb finish GHZ game, and comments on hidden variables / local reality (see notes added to lec7_wb), then demoed IBM composer, and submitted 5 and 7 qubit GHZ states, see whiteboard screengrabs and lec8_ibmq.ipynb, then started functions (A 17.1) |
| Thu 9/23 | 9. circuits/functions |
Whiteboards are here: lec9_wb GHZ symmetry, current GHZ27 record (arXiv:2101.08946), circuit identities, more on functions (A 17.1), many-worlds meets no-cloning (see notes added to lec8_wb), started Bernstein-Vazirani problem (A 18.1) | |
| Week 6 | Tue 9/28 | 10. Deutsch-Jozsa, Bernstein-Vazirani |
Whiteboards are here: lec10_wb Covered Deutsch's problem (1 bit to 1 bit functions) and its Deutsch-Jozsa generalization, Bernstein-Vazirani problem (n bit to 1 bit function of the form f(x)=a·x). See Aaronson notes 17.1, 17.3, 17.4, 18.1; also Qiskit: Phase Kickback, Deutsch-Jozsa Algorithm, Bernstein-Vazirani Algorithm |
| Thu 9/30 | 11. Simon's problem |
Whiteboards are here: lec11_wb Comments on phase kickback and ZN Fourier transform, then Simon's problem f(x) = f(x⊕a) (A 18.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 | |
| Week 7 | Tue 10/5 | 12. periods/factoring/RSA |
Whiteboards are here: lec12_wb Discussed relation between periods and factoring, and started discussion of RSA encryption (A 19.1). Finished with mention of RSA_numbers, specifically 768 | 232 (Feb 2010), 795 | 240 (Dec 2019), 829 | 250 (Feb 2020), mentioned 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) |
| Thu 10/7 | 13. q-garbage, ctrl-H, Fermat |
Whiteboards are here: lec13_wb why additional Qbits don't mess things up (A 17.2), construction of controlled-H, Intro to group theory and modular arithmetic, number theoretic preliminaries and Fermat's little theorem, RSA (A 19.2), finished with illustrative notebook lec13_RSA.ipynb Note: Added group theoretic appendix to last three pages of lec13_wb, with one-line proofs of results (for more on this and RSA, see also cs 2800 notes or pp 37-60 here) | |
| Week 8 | Tue 10/12 | Fall Break | |
| Thu 10/14 | 14. period finding and QFT | Whiteboards are here: lec14_wb mentioned added material in lec13_RSA.ipynb (randprime() and continued_fractions()), RSA wrap-up, using mod r instead of mod(p-1)(q-1) to decrypt, period finding (A 19.2), Quantum Fourier Transform (A 20), Bloch sphere (A 7.1), Fourier basis (qiskit) | |
| Week 9 | Tue 10/19 | 15. QFT circuit |
Whiteboards are here: lec15_wb Expectation values of Hermitian operators, and the Bloch sphere as spherical coords, Returned to explanation of Fourier Basis, then the Quantum Fourier Transform (see also A 20.1.1), implementation, and circuit diagram with quadratic growth in number of gates |
| Thu 10/21 | 16. streamlined QFT, phase estimation | Whiteboards are here: lec16_wb mentioned modular exponent is O(n3), discussed similarity to diffraction grating, mentione fractions and partial sums (A 21), continued quantum fourier transform: eliminate 2-qubit gates, unimportance of small phase errors, 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) introduced phase estimation, for ps4 problem 1, see also lec16_PhaseEstimation.ipynb Added notes on Euclidean algorithm (continuing from lec13), for ps4 | |
| Week 10 | Tue 10/26 | 17. Shor's algorithm details |
Whiteboards are here: lec17_wb Gave an overview of lec16_PhaseEstimation.ipynb, Discussed efficient circuit for modular exponent Uf, explained why using twice the number of input registers as output registers permits extracting j/r from y/2n using continued fractions, and gives a > 40% probablity of measuring an integer close enough to the peak for this, Covered Euclidean and extended Euclidean algorithm examples from the notes added to end of lec16_wb. |
| Thu 10/28 | 18. final factoring: fifteen, Grover |
Whiteboards are here: lec18_wb Started with brief comments on on post-quantum cryptography, e.g., lattice-based (see A 21.2), mentioned Fermat primes, then covered how to factor N=15 (though using n=no rather than n=2no as in those notes), unimportance of small phase errors, 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) (20000 bits = 6021 decimal digits, using compiled/recycled qubits), see Table 1 therein Then Grover's Algorithm (A 22.1.1-22.1.4, qiskit 3.8, see also pedagogical reviews: Grover's and Lavor et al.'s). | |
| Week 11 | Tue 11/2 | 19. Grover cont'd |
Whiteboards are here: lec19_wb generalization to several marked items, special case of one of four items, construction of W (A 22.1.1-22.1.4) [Now finished the basic basic quantum algorithms.] |
| Thu 11/4 | 20. Zeno, Pots, Bombs, and teleportation |
Whiteboards are here: lec20_wb 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) Comments on quant-ph/9801041 (nonlinear QM solves NP-complete and #P problems, see also Aaronson, pp. 7-8). Quantum Zeno, Watched Pot, Elitzur-Vaidman bomb (A 4.3, 4.4) Started quantum teleportation (A 10.1) | |
| Week 12 | Tue 11/9 | 21. teleportation -> QEC |
Whiteboards are here: lec21_wb quantum teleportation, teleportation of entanglement (A 10.1), note this fun historical account, and experimental implementation (from 1997). Discussed decoherence, mentioned again 1905.09749 in the context of error correction, referred to 1905.13641 for recent data on superconducting flux qubit coherence times and gate fidelities. Started quantum error correction (A 27.1-27.2), 3-qubit bit-flip code. |
| Thu 11/11 | 22. QEC I: stabilizers -> 5-qubit code |
Whiteboards are here: lec22_wb Stabilizer interpretation of 3 qubit bitflip correction code, then general form of single qubit errors (A 27.2, see also qiskit) Introduced measurement of operators, then started the 5-qubit error correction code | |
| Week 13 | Tue 11/16 | 23. QEC II: 5-qubit -> 7-qubit code |
Whiteboards are here: lec23_wb Some comments on course "mini"-project. Finished 5 qubit code, note that error correcting operator algebras can also be manipulated using python or matlab, e.g., this sample code. then 7-qubit code, and comments on fault tolerance, difficulties realizing 5- and 7-qubit codes with current qubit fidelities, universal gates. 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] |
| Thu 11/18 | 24. QEC III: 7-qubit -> surface code |
Whiteboards are here: lec24_wb Forgot to mention earlier: see 1907.04507 (2019) for recent superconducting qubit implementation of 5-qubit error-correcting code (and see NMR implementation from 2001). Completed verification of composite Hadamard and cNOT operators in 7-qubit code Then started the surface code, see arXiv:1208.0928, sections II-VI, pp.3-10, and mentioned 1912.09410 (experimental realization of a small section of surface code) | |
| Week 14 | Tue 11/23 | 25. QC Hardware |
Slides are here: pmc_lec25.pdf 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/25 | Thanksgiving | break | |
| Week 15 | Tue 11/30 | 26. surface → complexity | Whiteboards are here: lec26_wb 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 the recent experimental realization of truncated 7-qubit surface code in 1912.09410 (extending the coherence time of a logical qubit). Mentioned fault tolerance (A 27.2.2) and stabilizer codes (A 28), and began discussion of computational complexity (A 23) |
| Thu 12/2 | 27. BQP et al. |
Whiteboards are here: lec27_wb Recalled how # physical/logical qubits is determined, and relation to Quantum Moore's Law (things happen from 2028-2042, specifically quantum attacks on bitcoin: 1710.10377) Then continued discussion of 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. | |
| Week 16 | Tue 12/7 | 28. BQP ⊆ PSPACE, Adiabatic Algorithm |
Whiteboards are here: lec28_wb Started by flashing through parts of refs linked from lec27 [P, NP, et al. | BQP et al. | P vs. NP | 3-SAT | Preskill chpt 6 | Complexity Zoo | Petting Zoo) | Quantum Algorithm Zoo] Completed discussion of where BQP fits within computational complexity classes (A24.3, see fig 24.1, p.206), recalled CT and ECT from lec2, Finished with Hamiltonians (A 25) and Adiabatic Algorithm (A26) |
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.)