My Quantum Information Science II Lecture Notes: The wait is over!
They’re 155 pages of awesome—for a certain extremely specific definition of “awesome”—which I’m hereby offering to the world free of charge (for noncommercial use only, of course). They cover material that I taught, for the first time, in my Introduction to Quantum Information Science II undergrad course at UT Austin in Spring 2022.
The new notes pick up exactly where my older QIS I lecture notes left off, and they presuppose familiarity with the QIS I material. So, if you’re just beginning your quantum information journey, then please start with my QIS I notes, which presuppose only linear algebra and a bit of classical algorithms (e.g., recurrence relations and big-O notation), and which self-containedly explain all the rules of QM, moving on to (e.g.) quantum circuits, density matrices, entanglement entropy, Wiesner’s quantum money, QKD, quantum teleportation, the Bell inequality, interpretations of QM, the Shor 9-qubit code, and the algorithms of Deutsch-Jozsa, Bernstein-Vazirani, Simon, Shor, and Grover. Master all that, and you’ll be close to the quantum information research frontier of circa 1996.
My new QIS II notes cover a bunch of topics, but the main theme is “perspectives on quantum computing that go beyond the bare quantum circuit model, and that became increasingly central to the field from the late 1990s onwards.” Thus, it covers:
- Hamiltonians, ground states, the adiabatic algorithm, and the universality of adiabatic QC
- The stabilizer formalism, the 1996 Gottesman-Knill Theorem on efficient classical simulation of stabilizer QC, my and Gottesman’s 2004 elaborations, boosting up to universality via “magic states,” transversal codes, and the influential 2016 concept of stabilizer rank
- Bosons and fermions: the formalism of Fock space and of creation and annihilation operators, connection to the permanents and determinants of matrices, efficient classical simulation of free fermionic systems (Valiant’s 2002 “matchcircuits”), the 2001 Knill-Laflamme-Milburn (KLM) theorem on universal optical QC, BosonSampling and its computational complexity, and the current experimental status of BosonSampling
- Cluster states, Raussendorf and Briegel’s 2000 measurement-based quantum computation (MBQC), and Gottesman and Chuang’s 1999 “gate teleportation” trick
- Matrix product states, and Vidal’s 2003 efficient classical simulation of “slightly entangled” quantum computations
Extra bonus topics include:
- The 2007 Broadbent-Fitzsimons-Kashefi (BFK) protocol for blind and authenticated QC; brief discussion of later developments including Reichardt-Unger-Vazirani 2012 and Mahadev 2018
- Basic protocols for quantum state tomography
- My 2007 work on PAC-learnability of quantum states
- The “dessert course”: the black hole information problem, and the Harlow-Hayden argument on the computational hardness of decoding Hawking radiation
Master all this, and hopefully you’ll have the conceptual vocabulary to understand a large fraction of what people in quantum computing and information care about today, how they now think about building scalable QCs, and what they post to the quant-ph arXiv.
Note that my QIS II course is complementary to my graduate course on quantum complexity theory, for which the lecture notes are here. There’s very little overlap between the two (and even less overlap between QIS II and Quantum Computing Since Democritus).
The biggest, most important topic related to the QIS II theme that I didn’t cover was topological quantum computing. I’d wanted to, but it quickly became clear that topological QC begs for a whole course of its own, and that I had neither the time nor the expertise to do it justice. In retrospect, I do wish I’d at least covered the Kitaev surface code.
Crucially, these lecture notes don’t represent my effort alone. I worked from draft scribe notes prepared by the QIS II students, who did a far better job than I had any right to expect (including creating the beautiful figures). My wonderful course TA and PhD student Daniel Liang, along with students Ethan Tan, Samuel Ziegelbein, and Steven Han, then assembled everything, fixed numerous errors, and compiled the bibliography. I’m grateful to all of them. At the last minute, we had a LaTeX issue that none of us knew how to fix—but, in response to a plea, Shtetl-Optimized reader Pablo Cingolani generously volunteered to help, completed the work by the very next day (I’d imagined it taking a month!), and earned a fruit basket from me in gratitude.
Anyway, let me know of any mistakes you find! We’ll try to fix them.
Follow
Comment #1 August 31st, 2022 at 5:21 pm
Thank you!
Comment #2 August 31st, 2022 at 7:11 pm
In the first lecture notes you barely mention the Mermin-Peres Magic Square and to my dismay not at all in the second. Can you recommend a Mermin-Peres Magic Square for dummies paper please?
Comment #3 August 31st, 2022 at 9:34 pm
Phillip Dukes #2: My personal favorite treatment is my former student Alex Arkhipov’s, which directly relates the “magic” of the Mermin-Peres game to the non-planarity of the bipartite graph K3,3.
Comment #4 September 1st, 2022 at 2:25 am
Thanks a lot to you and your students for this! We’re already making good use of your QIS I lecture notes in our introductory QI course, and I’m sure we can also make use of some of these notes for our QI Technology course.
Comment #5 September 1st, 2022 at 6:44 am
Great lecture notes. Saved to my desk and hope to use it in the future.
Comment #6 September 1st, 2022 at 10:48 am
Thank you for these lecture notes! Would you ever consider teaching the Yamakawa-Zhandry structureless NP-Search algorithm and the relation to the AA-conjecture in your undergrad course?
Comment #7 September 1st, 2022 at 11:05 am
Can you help us learn it too? These subjects are heavy! Any recordings, visuals or other resources even powerpoints idk to go along with the notes?
Comment #8 September 1st, 2022 at 11:52 am
Thank you for this!
Small nit: on page 150, there are three references to Conjecture 1, but from context they should be referring to Conjecture 33.
Comment #9 September 1st, 2022 at 1:29 pm
Mark S. #6: Well, I’ll start by teaching Yamakawa-Zhandry in my graduate course! Its analysis does require stuff that’s pretty heavy for an undergrad course (convolution, lattices, properties of special error-correcting codes, a nontrivial query complexity lower bound). But if it ever became important to how people demonstrated quantum supremacy or generated certified random bits or whatever else, then yeah, I’d consider it.
Comment #10 September 1st, 2022 at 1:33 pm
Zach #7: Alas, I didn’t use PowerPoint. There exist recordings, but not of high quality and only for some of the lectures. There are also professional recordings of me teaching QIS I, but UT Austin is restricting those to the students in our online Masters program.
For QIS II, the lecture notes (including the many beautiful figures) are what I’ve provided to help you learn!
Comment #11 September 1st, 2022 at 1:36 pm
Thomas Colthurst #8: Thanks!! We’ll fix that.
Comment #12 September 2nd, 2022 at 9:02 am
Thanks very much Scott. Even an aging Euro-functionary like me can look at these notes and actually understand something!
Comment #13 September 2nd, 2022 at 3:06 pm
Hi Scott,
It would have been awesome if the notes came with home work problems and exercises. Maybe you will not be able to share the course’s home work. If so can you please give some good recommendations that would go well with these notes?
Comment #14 September 2nd, 2022 at 10:10 pm
[…] recently within the past 15 years. A blog article that describes these lecture notes is available here. MIT offers an xPRO series consisting of two series with two courses in each series. The courses […]
Comment #15 September 3rd, 2022 at 5:17 am
[…] O prof. Scott Aaronson é uma das referências em quantum, autor do livro “Quantum Computing since Democritus”. Ele tem uma didática muito boa, e sempre tenta explicar o por quê das coisas. Ele acabou de lançar mais notas de aulas. Vide: https://scottaaronson.blog/?p=6685 […]
Comment #16 September 3rd, 2022 at 5:40 am
These are great. Thanks for releasing them.
I thought the stabilizer simulation discussion was a bit outdated, but then I suppose I’m a bit biased on that!
A notational example is that you explain stabilizer tableaus using a notation where each output is a row of bits. But this is very much focusing on the details of representing tableaus in a computer, instead of focusing on the algebraic structure you want to convey. It’s like starting linear algebra by explaining 0.1 is stored as 00111101110011001100110011001100 in IEEE single precision, and then writing all the matrices that way! I think you should write tableaus as a list of Pauli string outputs (with each output being a column to match the convention used in matrices), instead of as rows of bits.
A concept example is that stabilizer circuits can be simulated in O(1) time per gate and O(1) space per qubit if you are promised that the all-zeros sample is a valid sample (call a circuit with this property a “grounded stabilizer circuit”). Furthermore, any stabilizer circuit can be converted into a grounded stabilizer circuit by conjugating certain measurements by bit flips. This gives insight into the group structure of the samples of stabilizer circuits.
Anyways, these might come off sounding like criticisms but I intend them as suggestions. I reiterate that I really like the notes.
Comment #17 September 3rd, 2022 at 11:16 am
Thanks so much for this!
Comment #18 September 3rd, 2022 at 7:11 pm
Thanks indeed. I’m curious to read both series. I really appreciate.
Comment #19 September 4th, 2022 at 8:12 pm
all 20 articles and no mention of Shroedenger, what’s that connection? Shocking to read physicist write marketing.
Comment #20 September 4th, 2022 at 9:02 pm
Craig Hadley #19: Schrödinger did his great work in the 20s and 30s and died in 1961. The QIS II story starts around 1996. It sounds as though you should start with the QIS I notes.
Comment #21 September 6th, 2022 at 9:52 am
It’s a little disconcerting that Lecture 1 opens with “Last time, we talked about…” Maybe add a reference to where this discussion can be found?
Comment #22 September 6th, 2022 at 10:04 am
David Speyer #21: Yeah, you’re right. That should be replaced by a link to the QIS I notes. Thanks!
Comment #23 September 7th, 2022 at 6:14 pm
If you want to adapt into a blog post just take the first and last paragraph of every chapter. You could call it Quantum Computing Since Quantum Computing Since Democritus.
Comment #24 September 26th, 2022 at 3:15 am
Scott, thanks for sharing these, they’re a great resource and a fun read.
I have a question about something that doesn’t quite make sense to me – the “burning an encyclopedia” example in the black hole section. I’ll quote it for context:
> …suppose we burn an encyclopedia. In principle, through time-reversible laws of microscopic physics, all of the information from the encyclopedia is still in the smoke and ash and thus is recoverable. But in practice, we have no technology that could actually recover the information from the burned encyclopedia.
But Bennett’s principle tells us that a logically irreversible process is also physically irreversible, so wouldn’t burning an encyclopedia be irreversible on those grounds irrespective of the technology we might have access to?
Comment #25 September 26th, 2022 at 7:19 pm
Igor F #24: Sorry, I’m not sure which “Bennett’s principle” you’re referring to, nor do I know the distinction between logical and physical reversibility. If modern physics is right, then in principle, burning a book is reversible in both senses.
Comment #26 September 28th, 2022 at 2:58 am
Oops, wrong attribution, I meant to say Landauer’s principle: logically irreversible transformations (like erasing information) result in an increase in entropy.
https://www.cs.princeton.edu/courses/archive/fall06/cos576/papers/bennett03.pdf
So in this case, burning an encyclopedia erases information that results in a physically irreversible increase in entropy.
I suppose I’m assuming that this inevitable increase in entropy is physically irreversible, maybe that is true in practice but not in principle.