Shtetl-Optimized


Someone recently wrote that my blog is “too high on nerd whining content and too low on actual compsci content to be worth checking too regularly.”  While that’s surely one of the mildest criticisms I’ve ever received, I hope that today’s post will help to even things out.

In Spring 2017, I taught a new undergraduate course at UT Austin, entitled Introduction to Quantum Information Science.  There were about 60 students, mostly CS but also with strong representation from physics, math, and electrical engineering.  One student, Ewin Tang, made a previous appearance on this blog.  But today belongs to another student, Paulo Alves, who took it upon himself to make detailed notes of all of my lectures.  Using Paulo’s notes as a starting point, and after a full year of procrastination and delays, I’m now happy to release the full lecture notes for the course.  Among other things, I’ll be using these notes when I teach the course a second time, starting … holy smokes … this Wednesday.

I don’t pretend that these notes break any new ground.  Even if we restrict to undergrad courses only (which rules out, e.g., Preskill’s legendary notes), there are already other great quantum information lecture notes available on the web, such as these from Berkeley (based on a course taught by, among others, my former adviser Umesh Vazirani and committee member Birgitta Whaley), and these from John Watrous in Waterloo.  There are also dozens of books—including Mermin’s, which we used in this course.  The only difference with these notes is that … well, they cover exactly the topics I’d cover, in exactly the order I’d cover them, and with exactly the stupid jokes and stories I’d tell in a given situation.  So if you like my lecturing style, you’ll probably like these, and if not, not (but given that you’re here, there’s hopefully some bias toward the former).

The only prerequisite for these notes is some minimal previous exposure to linear algebra and algorithms.  If you read them all, you might not be ready yet to do research in quantum information—that’s what a grad course is for—but I feel good that you’ll have an honest understanding of what quantum information is all about and where it currently stands.  (In fact, where it already stood by the late 1990s and early 2000s, but with many comments about the theoretical and experimental progress that’s been made since then.)

Also, if you’re one of the people who read Quantum Computing Since Democritus and who was disappointed by the lack of basic quantum algorithms in that book—a function of the book’s origins, as notes of lectures given to graduate students who already knew basic quantum algorithms—then consider these new notes my restitution.  If nothing else, no one can complain about a dearth of basic quantum algorithms here.

I welcome comments, bugfixes, etc.  Thanks so much, not only to Paulo for transcribing the lectures (and making the figures!), but also to Patrick Rall and Corey Ostrove for TA’ing the course, to Tom Wong and Supartha Podder for giving guest lectures, and of course, to all the students for making the course what it was.

  • Lecture 1: Course Intro, Church-Turing Thesis (3 pages)
  • Lecture 2: Probability Theory and QM (5 pages)
  • Lecture 3: Basic Rules of QM (4 pages)
  • Lecture 4: Quantum Gates and Circuits, Zeno Effect, Elitzur-Vaidman Bomb (5 pages)
  • Lecture 5: Coin Problem, Inner Products, Multi-Qubit States, Entanglement (5 pages)
  • Lecture 6: Mixed States (6 pages)
  • Lecture 7: Bloch Sphere, No-Cloning, Wiesner’s Quantum Money (6 pages)
  • Lecture 8: More on Quantum Money, BB84 Quantum Key Distribution (5 pages)
  • Lecture 9: Superdense Coding (2 pages)
  • Lecture 10: Teleportation, Entanglement Swapping, GHZ State, Monogamy (5 pages)
  • Lecture 11: Quantifying Entanglement, Mixed State Entanglement (4 pages)
  • Lecture 12: Interpretation of QM (Copenhagen, Dynamical Collapse, MWI, Decoherence) (10 pages)
  • Lecture 13: Hidden Variables, Bell’s Inequality (5 pages)
  • Lecture 14: Nonlocal Games (7 pages)
  • Lecture 15: Einstein-Certified Randomness (4 pages)
  • Lecture 16: Quantum Computing, Universal Gate Sets (8 pages)
  • Lecture 17: Quantum Query Complexity, Deutsch-Jozsa (8 pages)
  • Lecture 18: Bernstein-Vazirani, Simon (7 pages)
  • Lecture 19: RSA and Shor’s Algorithm (6 pages)
  • Lecture 20: Shor, Quantum Fourier Transform (8 pages)
  • Lecture 21: Continued Fractions, Shor Wrap-Up (4 pages)
  • Lecture 22: Grover (9 pages)
  • Lecture 23: BBBV, Applications of Grover (7 pages)
  • Lecture 24: Collision and Other Applications of Grover (6 pages)
  • Lecture 25: Adiabatic Algorithm (10 pages)
  • Lecture 26: Performance of the Adiabatic Algorithm (10 pages)
  • Lecture 27: Quantum Error Correction (8 pages)
  • Lecture 28: Stabilizer Formalism (9 pages)
  • Lecture 29: Experimental Realizations of QC (9 pages)

Notes and Updates (Aug. 27)

Here’s a 184-page combined file. Thanks so much to Robert Rand, Oscar Cunningham, Petter S, and Noon van der Silk for their help with this.

If it wasn’t explicit: these notes are copyright Scott Aaronson 2018, free for personal or academic use, but not for modification or sale.

I’ve freely moved material between lectures so that it wasn’t arbitrarily cut across lecture boundaries. This is one of the reasons why some lectures are much longer than others.

I apologize that some of the displayed equations are ugly. This is because we never found an elegant way to edit equations in Google Docs.

If you finish these notes and are still hankering for more, try my Quantum Complexity Theory or Great Ideas in Theoretical Computer Science lecture notes, or my Barbados lecture notes.  I now have links to all of them on the sidebar on the right.