## My Quantum Information Science II Lecture Notes: The wait is over!

Here they are [PDF].

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.

### 26 Responses to “My Quantum Information Science II Lecture Notes: The wait is over!”

1. Phillip Dukes Says:

Thank you!

2. Phillip Dukes Says:

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?

3. Scott Says:

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.

4. Jonas Neergaard-Nielsen Says:

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.

5. Chaoyang Lu Says:

Great lecture notes. Saved to my desk and hope to use it in the future.

6. Mark S. Says:

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?

7. Zach Says:

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?

8. Thomas Colthurst Says:

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.

9. Scott Says:

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.

10. Scott Says:

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!

11. Scott Says:

Thomas Colthurst #8: Thanks!! We’ll fix that.

12. Adam Lewis Says:

Thanks very much Scott. Even an aging Euro-functionary like me can look at these notes and actually understand something!

13. Ashley Lopez Says:

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?

14. Education in Quantum Technology - Quantum Computing Report Says:

[…] 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 […]

15. Notas de aula – Prof. Scott Aaronson – Computação e Informação Quântica Says:

[…] 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 […]

16. Craig Gidney Says:

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.

17. Marc Says:

Thanks so much for this!

18. Mihail Saslis Says:

Thanks indeed. I’m curious to read both series. I really appreciate.

19. Craig Hadley Says:

all 20 articles and no mention of Shroedenger, what’s that connection? Shocking to read physicist write marketing.

20. Scott Says:

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.

21. David Speyer Says:

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?

22. Scott Says:

David Speyer #21: Yeah, you’re right. That should be replaced by a link to the QIS I notes. Thanks!

23. Nicholas Teague Says:

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.

24. Igor F Says:

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?

25. Scott Says:

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.

26. Igor F Says:

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.

You can use rich HTML in comments! You can also use basic TeX, by enclosing it within  for displayed equations or  for inline equations.

Comment Policies:

1. All comments are placed in moderation and reviewed prior to appearing.
2. You'll also be sent a verification email to the email address you provided.
YOU MUST CLICK THE LINK IN YOUR VERIFICATION EMAIL BEFORE YOUR COMMENT CAN APPEAR. WHY IS THIS BOLD, UNDERLINED, ALL-CAPS, AND IN RED? BECAUSE PEOPLE ARE STILL FORGETTING TO DO IT.
3. This comment section is not a free speech zone. It's my, Scott Aaronson's, virtual living room. Commenters are expected not to say anything they wouldn't say in my actual living room. This means: No trolling. No ad-hominems against me or others. No presumptuous requests (e.g. to respond to a long paper or article). No conspiracy theories. No patronizing me. Comments violating these policies may be left in moderation with no explanation or apology.
4. Whenever I'm in doubt, I'll forward comments to Shtetl-Optimized Committee of Guardians, and respect SOCG's judgments on whether those comments should appear.
5. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email.