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 cryptoxgraphy, and for computer scientists and
mathematicians with prior exposure to 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 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 2018)
| Announcements: | |
| – 21 Dec Enjoy the break |
Syllabus:
| Date | Lecture | Reading | |
|---|---|---|---|
| Week 1 | Thu 9/3 | 1. Intro | Began with historical overview,
see, e.g.,
chapter 1 of
Preskill notes, see also
The Feynman Lectures on Computation (Hey and Allen), and these as goals for end of course • Preskill, NISQ [1801.00862] (please read this one) • Surface code [1912.09410] (plus overview) plus some brief mention of these: • NP-completeness • "MIP*=RE" [2001.04383] On whiteboard, covered section 1.2 of Mermin's text, to be continued. For a refresher on the linear algebra and Dirac notation we'll be using, see Appendix A of that text (pp. 159-167) in advance of lecture 2. |
| Week 2 | Tue 9/8 | 2. Cbits |
Covered roughly pp 8-14 (1.3-1.4) of course text: reversible operations (inversion, swap, cNOT), Hadamard:
see lec2_wb
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 (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. • Maxwell demon video and description |
| Thu 9/10 | 3. qubits I |
2d rotation group, half-wave plates, Hadamard as reflection about π/8, discussion of entanglement (see these notes for discussion of SVD criterion for whether two subsystems are entangled), Continued discussion of swap, cNOT, Hadamard, covered Born rule and other parts of 1.5-1.8 and material from Appendices A,B for probset 1: see lec3_wb | |
| Week 3 | Tue 9/15 | 4. qubits II |
More on SU(2)/Z2 as origin of fermions and bosons, mentioned Quantum 2.0 Conf (14-17 Sep 2020), controlled-Z operator (sec 1.4, p. 14), some comments on Bell and GHZ states (for some recent experiments and circuit diagrams, see fig 4 of arXiv:1402.4848; also arXiv:1004.4324: fig 3c, arXiv:1004.4246: fig 1b), difference between superposition and classical mixture (sec 1.8, p. 27), compared entangled vs. product # d.o.f.'s; see lec4_wb |
| Thu 9/17 | 5. Born again | Discussed probset 1 rotations/permutations, showed some Rubik examples of Platonic solids (unsuccessfully trying to seed answers to later questions; for practical implications, see also icosahedral qubit benchmarking). Mentioned gate universality (see "The Solovay-Kitaev Algorithm" for technical review), covered reversible operations on Qbits (1.6, pp. 19-20), generalized Born (1.9), and state preparation (1.10); see lec5_wb | |
| Week 4 | Tue 9/22 | 6. functions |
constructing arbitrary 1- and 2-Qbit states (see again notes). Covered pp. 34-42 (1.12-2.2): Cbit vs Qbit summary, discussion of general computational process (2.1), functions, no-cloning and started Deutch's problem see lec6_wb |
| Thu 9/24 | 7. quantum speed-up | Looked at some 3d visualizations in lec7_rotations.ipynb, followed by example of Hadamard as rotation by π around (x̂+ẑ)/√2, and some discussion of ps2, problem 4d,e) Finished Deutch's problem (2.2, pp. 41-46), mentioned Two Quadrillionth Bit of π is 0, then started Bernstein-Vazirani problem (2.4, pp. 50-54) see lec7_wb | |
| Week 5 | Tue 9/29 | 8. exponential speed-up |
Finished Bernstein-Vazirani problem (2.4, pp. 50-54,
including this attempted clarification of
eq.(2.32)) Simon's problem (2.5 and appendix G) [now halfway through standard algorithms] see lec8_wb |
| Thu 10/1 | 9. √X |
Final comments on Simon's problem (see Appendix G of text) -- example of the purely mathematical postprocessing frequently necessary after the quantum algorithm returns its probabilistic results. quantum Toffoli gates (2.6, pp 58-61) see lec9_wb | |
| Week 6 | Tue 10/6 | 10. Bloch | why additional Qbits don't mess things up, (2.3, pp 46-50), Bloch sphere, see lec10_wb and started discussion of quantum tomography using these simulations |
| Thu 10/8 | 11. GHZ vs EPR, period finding | brief discussion of ps2 #4c, see visualizations 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}); began discussion of period finding and relation to breaking RSA encryption (3.1 in text). mentioned 1905.09749 ("How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits") see lec11_wb | |
| Week 7 | Tue 10/13 | 12. FLT -> RSA |
Some discussion of RSA_numbers,
specifically
768 | 232 (Feb 2010),
795 | 240 (Dec 2019),
829 | 250 (Feb 2020). Intro to group theory and modular arithmetic (App. I, sec. 3.1), number theoretic preliminaries and Fermat's little theorem (3.2), RSA (3.3), then started discussion of quantum period finding (3.4). see lec12_wb |
| Thu 10/15 | 13. RSA -> QFT |
(Started with digression on "What is the probability that 15 Oct is Thursday"?, and then mention that 400M years ago, there were closer to 400 days per year, as shown by Cornell's John Wells (1963) [surprisingly readable]) Added group theoretic proofs to last page of previous lec12_wb (for more on this and RSA, see also cs 2800 notes or pp 37-60 here) continued quantum fourier transform and period finding (parts of sections 3.5 and 3.7 of course text). see lec13_wb | |
| Week 8 | Tue 10/20 | 14. QFT and period finding | discussed similarity to diffraction grating, continued quantum fourier transform and implementation (see also 3.5), eliminate 2-qubit gates (3.6) mentioned qubit recycling(experimental implementation: arXiv:1111.4147) see lec14_wb |
| Thu 10/22 | 15. practical details | Some comments on ps3#1 (see solutions) finding the period and probability estimates (3.7, see also App. L plus quant-ph/0411184 and quant-ph/0607148), calculating the period function (3.8) 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). started discussing continued fractions (App. K), Euclidean algorithm (App. J) see lec15_wb | |
| Week 9 | Tue 10/23 | 16. = 24 = 3×5 + 1 |
Mentioned Fermat primes,
then covered how to factor N=15 (though using n=no rather than n=2no as in those notes), period finding and factoring (3.10), continued fractions and partial sums (sec 3.7, plus example from App. K), unimportance of small phase errors (3.9), mentioned again 1905.09749 in the context of error correction (chpt 5, starting next week), and brief overview of grover's algorithm (chpt 4, next lecture). see lec16_wb Also some factoring "records" mentioned: 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 |
| Thu 10/25 | 17. Grover | Grover iteration (4.1-4.2), generalization to several marked (4.4), one of four items (4.5), started construction of W (4.3) (see also pedagogical reviews: Grover's and Lavor et al.'s). see lec17_wb | |
| Week 10 | Tue 11/3 | 18. Grover cont'd + QKD |
Finished 4.3 on how to construct W, plus 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.] Comments on no-go speedup for XOR/Parity and OR Comments on quant-ph/9801041 (nonlinear QM solves NP-complete and #P problems, see also Aaronson, pp. 7-8). Then covered most of quantum key distribution (6.2, 137-141) see lec18_wb Original article by Bennett and Brassard (1984): BB84 Some older 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") ● 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 |
| Thu 11/5 | 19. QKD → QEC I |
Additional comments on QKD (6.2, 141-143),
B92 protocol,
E91 protocol More recent refs: key materials for QKD (ACS, 2017), 1200km record for bell pair (Science, 2017), secured videoconf (2018), recent satellite QKD review (1707.03613) also mentioned 2011.02152 for the "bright illumination" attack on QKD started quantum error correction, 5.1-5.3 (pp 99-113) referred to 1905.13641 for recent data on superconducting flux qubit coherence times and gate fidelities. see lec19_wb | |
| Week 11 | Tue 11/10 | 20. QEC II |
Started with discussion of
nytimes 03Dec18 article on "race to quantum encryption" (also refers to nytimes 21Oct18 on quantum computing jobs, and nytimes 13Nov18 on qc research) Introduced measurement of operators (5.4), then 5 qubit code (5.5) (pp 113-120) see lec20_wb |
| Thu 11/12 | 21. QEC III |
Some comments on course "mini"-project. Finished 5 qubit code (5.5), note that error correcting operator algebras can also be manipulated using python or matlab, e.g., this sample code. then 7-qubit code (5.6-5.8, p.121-128), 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] see lec21_wb | |
| Week 12 | Tue 11/17 | "semi-final" period | no classes |
| Thu 11/19 | |||
| Week 13 | Tue 11/24 | ||
| Thu 11/26 | Thanksgiving | ||
| Week 14 | Tue 12/1 | 22. IBMQ, teleportation |
Demo'd the IBM Quantum Experience website with a real-time construction and run of a GHZ 5-qubit state on one of their 5-qubit machines (there are tutorials linked from home page, (free) account required only to run on their hardware Showed figure from article benchmarking their 27-qubit chip. Also showed some of the qiskit (python) interface, see qiskit circuit tutorials (and other linked tutorials, including advanced circuit tutorials and quantum operations) The have a useful textbook, overlapping with this class and with additional parts worth reading (in class highlighted their Fourier transform visualization) Switched to quantum teleportation (6.5, p.149-154), note this fun historical account, and experimental implementation (from 1997). see lec22_wb |
| Thu 12/3 | 23. teleportation, surface code | Started with more comments on IBM's circuit editor gates.
In the context of IBM's current cloud machines, mentioned
this article (Sep 2020)
(regarding plans to move from the current 65 to 127 in 2021, 433 in 2022, and an 1121 qubit machine by 2023). Here also is their official roadmap (also looking towards 1 million),
and some technical challenges. Google's Cirq platform is an alternative to IBM's qiskit (though doesn't yet permit the general public to run directly on their quantum cloud). Recalled the "compiled" superconducting qubit factoring of 15 using 42=1 mod 15 (2012, see 1202.5707 fig.3), and the possibility of running that on a 5-qubit machine. Finished teleportation of entanglement (6.5) and Bell states (6.1), and discussed briefly the relation to Magic state distillation (originally Bravyi/Kitaev (2004)), and its use as a fault tolerant means of creating Phase and Toffoli gates (the 'CCZ factory' of arXiv:1208.0928). See figure 1 of 1905.06903 for problems 6A,C in ps6 [as well figs 2,3,4,16] (and see eqs. (7)-(11) on p.2 of 1210.0974 for problem 6B). Back to error correction, see 1907.04507 (2019) for recent superconducting qubit implementation of 5-qubit error-correcting code (and see NMR implementation from 2001). Then started the surface code, see arXiv:1208.0928, sections II-VI, pp.3-10. For next time, have a look at 1912.09410 (the experimental realization of the surface code mentioned in lec1) See lec23_wb | |
| Week 15 | Tue 12/8 | 24. surface → supremacy | More on surface code, 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). Began the discussion of last year's Google "quantum supremacy" experiment (see also accompanying news, plus news&views, and supplementary material). See lec24_wb |
| Thu 12/10 | 25. supremacy → hardware |
Some additional explanation of ps7 prob 6B. Quantum attacks on bitcoin: 1710.10377, and Quantum Moore's Law (things happen from 2028-2042). Continued discussion of last year's Google "quantum supremacy" experiment (and supplementary material): 20 qubit demo: 1709.06678 (Martinis et al.), comments on Porter-Thomas distribution Pr(Np)=exp(-Np), earlier proposal from overlapping group: 1608.00263, refined proposal: 1807.10749, some visualizations of their suggested random circuits, proof that random circuit sampling satisfies an average-case hardness condition: 1803.04402 (Vazirani et al.) slides from 29 Oct 20 Q&A in Gates G01 Another claimed "supremacy" (3 Dec 2020): 2012.01625 using "boson sampling", (plus 3 Dec overview, and related blog post; see also photonic chip: 2003.08919). Then overview of other quantum computing hardware, including NMR 1501.01353 (review) and trapped ions 1904.04178 (review). And moved to current top contender: superconduction transmon qubits (using "Quantum Engineer's Guide" 1904.06560, also 1905.13641). See lec25_wb | |
| Week 16 | Tue 12/15 | 26. transmons, BQP, and all that |
Started with mention of 2012.06137 on protecting qubits from gamma and cosmic rays (always fun to begin final lecture with relevant and accessible article just appeared day before). Continued with "Quantum Engineer's Guide" 1904.06560, App. H from the text, Martinis notes on CNOT (see also cond-mat/0402415 (Martinis/Osborne, 2004)) 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", Complexity Zoo, and abbreviated Petting Zoo). Mentioned "Quantum Algorithm Zoo": compendium of quantum algorithms. For a more computational complexity oriented take on the material for the semester, see Scott Aaronson's course notes (2017). See lec26_wb |
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.)