## Quantum Computing Lecture Notes 2.0

Two years ago, I posted detailed lecture notes on this blog for my Intro to Quantum Information Science undergrad course at UT Austin. Today, with enormous thanks to UT PhD student Corey Ostrove, we’ve gotten the notes into a much better shape (for starters, they’re now in LaTeX). You can see the results here (7MB)—it’s basically a 260-page introductory quantum computing textbook in beta form, covering similar material as many other introductory quantum computing textbooks, but in my style for those who like that. It’s missing exercises, as well as material on quantum supremacy experiments, recent progress in hardware, etc., but that will be added in the next version if there’s enough interest. Enjoy!

Unrelated Announcement: Bjorn Poonen at MIT pointed me to researchseminars.org, a great resource for finding out about technical talks that are being held online in the era of covid. The developers recently added CS as a category, but so far there are very few CS talks listed. Please help fix that!

### 61 Responses to “Quantum Computing Lecture Notes 2.0”

1. Clément Canonne Says:

TCS+ was on mathseminars.org, now renamed researchseminars.org: https://researchseminars.org/edit/schedule/?shortname=TCSPlus

2. Clément Canonne Says:

Also good to point out the other CS talks aggregator, created by Shachar Lovett: http://cstheory-talks.org/

3. Chris H Says:

This is great! I was just going back through QCsD and wanting to dive deeper into some details. I was contemplating Mike & Ike but this might be a better middle ground for someone who likes details but isn’t professionally involved. Any chance your workflow makes it easy enough to output an ePub? In any case thanks greatly for taking the trouble to put this out here.

4. kodlu Says:

@Chris H, I assume Mike & Ike is Nielsen & Chuang? Another middle round approach, I think, is provided by Lipton & Regan’s book.

5. Scott Says:

Clément #1: Thanks! I’m glad to see that my comment that there are “no” CS talks there is already outdated. I changed “no” to “very few.”

6. nilesh Says:

This is great! I keep saving links to all high-quality learning material on all kind of topics to LearnAwesome.org. Added this one too: https://learnawesome.org/items/dee61d27-63cc-447a-b886-328dda96e2a0-shtetl-optimized-blog-archive-quantum-computing-lecture-notes-2-0

7. Scott Says:

Chris #3: My “workflow” is basically Corey, who kindly volunteered to read this thread! If it’s easy to convert LaTeX or PDF into an ePub, then I’m sure he’ll be happy to do that. If not, you might have to make do with that worldwide standard of academic exchange, the PDF document.

8. syskill Says:

Scott, if an ePub can’t be done, then a PDF with smaller-sized pages (like you did for your P NP article) would be much appreciated.

9. Raoul Ohio Says:

The “Knot Online Seminar” is online? Sounds like something Douglas Hofstadter would organize.

10. Ashley Lopez Says:

Scott,

“will be added in the next version if there’s enough interest” – one vote for including the exercises. (Will worked out exercises be possible, for people who do self study?)

11. Notas de aula – prof. Aaronson – Computação e Informação Quântica Says:

[…] Quantum Computing Lecture Notes 2.0 […]

12. Robson Says:

Thanks, Scott! What do you think of the material at https://quantum.country?

13. Craig Gidney Says:

I was looking at section 5.1 (the coin problem) and it raised a question. Is it the case that there is still an asymptotic space advantage at this task when considering the overhead of fault tolerance (both in the classical case and the quantum case)?

In practice, if you wanted to use this coin bias checking protocol, you would need a very reliable qubit. Which implies you would need error correcting codes. Suppose you use the surface code. Every time you want to verify the coin’s unbiasedness to an epsilon that’s ten times smaller, you will need to protect the surface code qubit for a hundred times longer because you will need to apply ten times more operations to it and each operation will consist of ten times more rotations (since you must more closely approximate a smaller rotation with a series of H and T gates). This will (roughly speaking) offset the code distance upward by a constant amount. So the number of physical qubits being used to encode the single logical qubit will presumably grow like log(1/epsilon)^2 [or a little worse]. This sounds suspiciously like what it might take in the classical case using fault tolerant bits.

I know that there are quantum codes where the asymptotic overhead of fault tolerance is constant ( https://arxiv.org/abs/1808.03821 ) but I don’t think those bounds apply in the case where you fix the number of logical qubits to be exactly 1.

14. John Figueroa Says:

This is awesome, Scott!

Tangent, but does anyone else feel like their baseline motivation and pattern of reading stuff is weirdly dependent on the format? I’ve had a different set of quantum computing notes by you open in a tab for a while, because I’ve been “meaning to get around to reading them”, but since this one is a .pdf instead of an .html, my motivation is way higher. And it’s pretty arbitrary; I’ll usually spend more time in one sitting with a .pdf textbook than I will with a physical textbook, but for non-academic stuff I’ll take the physical thing over an ebook any day.

15. Scott Says:

Robson #12: It looks great!! (Like any pedagogical material that Michael Nielsen touches.)

16. Scott Says:

Craig Gidney #13: That’s an extremely interesting question that I hadn’t thought about! My guess would be that in the presence of tiny noise, all quantum space advantage basically vanishes. But even if so, off the top of my head I don’t know whether that’s trivial to prove or whether it would be a new paper. Does anyone else have thoughts?

Edited to add: it will all depend on the relation between two numbers, the bias ε of the coin and the noise rate η. If η<<ε, then my and Drucker’s protocol should work fine with no error correction. If η>>ε, then a quantum advantage should be pretty hopeless, though it remains to make that statement quantitative. That leaves only the intermediate regime. In any case, I guess my conjecture is that it’s essentially never worth it to combine my and Drucker’s protocol with quantum error correction.

17. Corey Ostrove Says:

@Chris H #3 and syskill#3: I spent some time looking into your question about creating an epub version of the notes and attempted the conversion process, and the short answer is that it doesn’t look like that’ll happen anytime soon. There are tools available for this, but when I try to run them they throw a few hundred unhelpful compiler errors which I don’t have the time to trace at the moment. There are also fundamental compatibility issues with typesetting math in the epub format itself which would more or less limit the files to being viewed on PC/Mac and Android/IOS devices. Handheld e-readers don’t seem to support the necessary features.

Creating a version with smaller page sizes should be doable though with just a handful of modifications.

18. Greg McLellan Says:

I should probably finally get around to learning quantum information theory properly, and this coming out is probably as good a driver to make a start on it as I’m going to get, so thanks to Corey for putting in the work!

Seconding Ashley #10, exercises would be welcome. 🙂

I’d be interested in any (brief, I don’t want to eat up your time!) thoughts you might have on the kinds of further study, alongside or beyond this course, that’d round out an ideal knowledge base if one were looking to get to the research frontier in quantum complexity.

19. John Figueroa Says:

Am I misunderstanding, or are there a few typos on page 16? It says the output vector is:

[q/2    ]
[p+q/2]

But I think it’s supposed to be:

[p/2+q]
[p/2   &nbsp]

For the probability of an output of heads: It can either land on heads, and then the fair flip lands on heads (p*(1/2)), or (+) it can land on tails, in which case it gets turned over to heads (q). So p/2+q. For the probability of an output of tails: It must land on heads first, then the fair flip takes it to tails: p/2.

The discussion mostly seems to corroborate this; it says that P(heads|heads) = P(tails|heads) = 1/2, giving us the first column, and that P(tails|tails) = 0. (There’s a second typo where it should say P(heads|tails) = 1 but actually says P(tails|heads) = 1.) So the fixed description should imply the matrix:

[1/2    1]
[1/2    0]

[0    1/2]
[1    1/2]

Was there a rewrite of the example and the numbers didn’t get changed to match or something?

____________

Also, maybe this is on me, but: It took me a bit to understand what the example was saying. As I understand it now, there are three stages:

[_]    ->    [p]    ->    [? = p/2+q]
[_]    ->    [q]    ->    [? = q/2    ]

The first transition is some not-necessarily-fair flip that just scrambled the coin to being in the state <p,q>. And the second transition is the thing that’s either a fair flip or turning it over (depending on the state in the second stage). The question is to work out what the question marks are and what the transition matrix is from the second stage to the third stage.

Do I have all of that right? Because when I first read “Let’s say we flip the coin, and if we get heads we flip again, but if we get tails we turn it to heads”, I thought that the idea was that both flips were fair:

[p]    ->    [1/2]    ->    [? = 3/4]
[q]    ->    [1/2]    ->    [? = 1/4]

And that the question was to figure out the question marks and what the transition was from the first stage to the third stage. I couldn’t figure out why the p and q were still relevant!

I think the example should read more like “Say the coin is in the state <p,q> (e.g., as the result of a not-necessaarily-fair flip). Then we do the following transformation: if the coin is heads we do a fair flip, but if it’s tails we turn it to heads.”

20. Scott Says:

Greg #18: The “research frontier” is such a jagged surface that in some places, my undergraduate course will already take you there (as it did for Ewin Tang, to take one example). In other places, you need a followup grad quantum complexity course plus some other courses to get there. In general, though, I could point you to Mike & Ike, Quantum Computing Since Democritus, my own graduate quantum complexity theory lecture notes, the notes of Umesh Vazirani and John Watrous and John Preskill and Andris Ambainis…

21. Craig Gidney Says:

Thinking more about the coin problem, it occurred to me that in order to run it you need to know which step of the process you are on (e.g. how many flips you have already performed), which presumably requires takes log(n) bits where n is the number of steps (assuming tricks akin to HyperLogLog can’t reduce the information needed to store the step count). This implies the space reduction in the noiseless case is not from log(n) bits to 1 qubit but rather 2*log(n) bits to 1 qubit + log(n) bits.

Another possible source of polylogarithmic bits in the quantum case is the encoding of the rotation angle into the program you are running to perform the protocol.

I’m leaning towards the asymptotic space advantage being more of a feature of the cost model rather than something that could be realized in practice, even for sufficiently noiseless quantum computers.

22. Scott Says:

Craig #21: No, that’s incorrect. As my paper with Drucker points out, you can simply halt at each time step with independent probability ~ε2, which removes the need for a timer with logarithmically many bits.

23. Futureseek Daily Link Review; 22 May 2020 | Futureseek Link Digest Says:

[…] technology in the service of the customer >> * Quantum Computing Lecture Notes 2.0 >> * Will online summer camp work? […]

24. Craig Gidney Says:

Scott #22: Good point.

I want to push on this a bit more. I think that the problem has gotten smaller, but has moved into the implementation of the “halt with probability ε^2” subroutine. Is it possible to implement that subroutine using a constant number of bits?

Suppose the Turing machine executing the procedure has a “write unbiased random bit” instruction and that this is the only source of randomness. In order to represent probabilities as small as 1/ε^2 I think it is necessary to execute this instruction at least log(1/ε^2) times. This implies there must be a program counter of some sort with at least log(log(1/ε^2)) bits, to track how many random bits have been written.

The representation of 1/ε^2 itself may also cause problems. If it is an arbitrary incompressible value then this implies must be 2 log(1/ε) bits stored on the tape (assuming the same Turing machine must be used for all sizes). The actual values of ε^2 that are needed should follow useful patterns that allow compression, but to my eye it looks like at least log(log(1/ε)) bits would be needed.

So perhaps instead of a log(1/ε) to 1 reduction it’s a log(1/ε) to log(log(1/ε)) reduction?

25. Peter Morgan Says:

Congratulations to Corey Ostrove for a job very well done. As always, I confine myself to comments on the interpretation of QM.

The “recent result by Prof. Aaronson” about Schrodinger’s cat, mentioned on page 86, which I see elsewhere is with Yosi Atia and that you gave a paper at Perimeter on the subject, doubtless will be presented in a QC formalism, but otherwise seems to be similar to the argument I present informally in Section 7.3 of “An algebraic approach to Koopman classical mechanics,” in Annals of Physics a few months ago (arXiv:1901.00526v5, and DOI there). The difference of perspective might be of interest for some. I look forward to your paper turning up: will it be soon, given how things are?

For the suggestions given about dynamical collapse on page 87,
• Collapse happens when some number of atoms get involved.
• Collapse happens after a certain total mass is reached.
• Collapse happens when a system reaches a certain level of “complexity.”
… to these /could/ be added,
• Collapse happening after measurement A is equivalent to compelling subsequent measurements to commute with A, with no collapse.
This I show to be the case in Section 7.1 of “An algebraic approach to Koopman classical mechanics.” This formulation removes any /necessity/ for dynamical or any other collapse. Instead, we can discuss a collapse picture and/or a no-collapse picture and easily transform between them, which lessens and clarifies the differences you mention on Page 83 between the different founders’ versions of the Copenhagen Interpretation.

26. Scott Says:

Craig #24: Drucker and I weren’t working in the Turing machine model, but in the model of quantum finite automata. In other words, the only resource we cared about was the number of qubits used to store information about the history of the coin flips up to the present.

Having said that, our protocol corresponds to an extremely small quantum Turing machine, as long as you let the QTM contain things like “now halt with probability ε2” as primitives (i.e., as long as ε itself can be hardwired into the QTM’s transition table). It’s true that, if ε were only supplied on an input tape and you needed a uniform algorithm, that would add some complexity.

27. barbara Says:

Thanks so much to both Scott and Corey for publishing these nice lecture notes :). I’m going to give an “Introduction to Quantum Computing” lecture next summer and am very happy about another great reference. Plus beautfifully typeset, thanks!

28. Job Says:

The coin problem reminds me of something I was thinking about.

Have you considered a computer where bit values are relative to the computer’s orientation? 🙂

With a rotate(rad) operation that physically rotates the computer it would allow a program to implicitly change bit values.

It sounds strictly more powerful than a conventional computer because:
– You can just not rotate it, if you want a normal CPU.
– It’s better at penetrating blackbox problems because it can affect the blackbox’s execution using rotations, and leak additional information.

And it can also solve the coin problem with a single bit, right?

Sure, it only works because it’s sneaking the required log(1/e^2) bits outside the computer where they’re not explicitly considered (they’re stored as a physical orientation), but the QC is doing something conceptually similar, it just has more dimensions?

29. Scott Says:

Job #28: A QC built out of spin-1/2 particles is literally what you said, except with qubits rather than classical bits. With classical bits, how exactly would it work? If I rotate a bit but only partially, then does it flip between 0 and 1 or not?

30. Job Says:

A QC built out of spin-1/2 particles is literally what you said, except with qubits rather than classical bits. With classical bits, how exactly would it work? If I rotate a bit but only partially, then does it flip between 0 and 1 or not?

OK, I guess your point is that, for the coin problem, this might as well be a classical simulator for a single-qubit QC.

So it’s not surprising that it works, it’s just a very simple problem.

But in general, aren’t classical rotations already an improvement for dealing with black-box problems?

That’s what i’m trying to understand.

31. Scott Says:

Job #30: No, you misunderstood. I was really, non-rhetorically asking how it works to have an angle-dependent classical bit: at what angle does the bit flip from 0 to 1? With a qubit, the way it works is obvious.

32. Job Says:

No, you misunderstood. I was really, non-rhetorically asking how it works to have an angle-dependent classical bit: at what angle does the bit flip from 0 to 1? With a qubit, the way it works is obvious.

Why wouldn’t it just be probabilistic?

I think the angle would determine the probability of 0 or 1, then rotate by π to flip.

That seems alot more interesting, especially for black boxes.

For example, you could distinguish between an empty two-bit circuit and one that applies the same CNOT twice by guessing a control bit and setting it to “50% one”.

It seems that you could use this to leak information from a black box, even classically, which could provide an advantage for one classical model vs another for specific problems.

The part that i find confusing, and it’s really subtle, is whether it actually matters.

In theory, you can’t convert a blackbox to a different architecture (e.g. one that can be simulated) because it’s a blackbox and you can’t look inside.

But in practice, you usually can.

33. Scott Says:

Job #32: If it’s probabilistic, how exactly do the probabilities work? I.e., what’s the Markov chain governing the transitions between 0 and 1? Is there a stationary distribution associated to each direction? If so, then why can’t we use those distributions to pick out distinguished directions (say, “the directions in which the bits are most likely to assume definite values”), and thereby break rotational symmetry?

I’ll be deeply impressed if you can write down any concrete model for probabilistic, angle-dependent bits in 2- or 3-dimensional space, even just a toy model, that isn’t tantamount to qubits.

34. Gerard Says:

Job #28

If you’re talking about classical bits how is that different from just making logic gates continuous functions of their inputs (which are allowed to take any value in the range [0,1].

> It’s better at penetrating blackbox problems because it can affect the blackbox’s execution using rotations, and leak additional information.

I thought the point of blackbox problems is that you aren’t allowed to use any information from the function’s implementation (which your proposal surely does) otherwise it’s not a blackbox.

35. Rohit Says:

I’ve been brushing up on quantum info lately — this is great, thanks!

36. Job Says:

I thought the point of blackbox problems is that you aren’t allowed to use any information from the function’s implementation (which your proposal surely does) otherwise it’s not a blackbox.

As long as it can solve a problem like period-finding…

If a classical computer were able to extract a period or secret value from a black-box by relying on a new low-cost operation, as sketchy as it might be, it’s just as good.

And adding a rotation function doesn’t even sound that sketchy, depending on how it’s implemented.

A QC is good with black-box problems in some cases because it’s jamming quantum input in and seeing what comes out the other side. 🙂

Why can’t we try something similar with a probabilistic computer?

37. Gerard Says:

@Scott

If tomorrow someone proved that BQP is in P do you think that would have any implications for quantum mechanics itself ?

38. Scott Says:

Gerard #37: I guess it depends on what you mean by “quantum mechanics itself.” The theory would still have the same empirical content, but the way we understood and worked with it might become completely different (possibly more or less, depending on the details of how P=BQP was proved).

39. Gerard Says:

Scott #37

Suppose it was proved by proving that #P is in P (ie. P = P^#P) purely classically with no reference to quantum mechanics.

Would the fact that quantum circuits (and maybe general quantum systems ?) could be simulated efficiently in and of itself have any kind of implication for how we think about QM ? For example would it increase the likelihood of some kind of hidden variables theory (obviously non-local) being true ?

I mean it seems like knowing that QM provides no additional computational power over a classical universe when theory leads us to believe that it should (ie. via the multi-worlds interpretation for example) would have some kind of implications.

40. Craig Gidney Says:

Gerard #37: I think if it was proven that BQP=P it would spawn a niche quantum interpretation: that what Nature was “really doing” was somehow analogous to what the polynomial time algorithm for simulating BQP was doing. It certainly wouldn’t be the first time that an effective calculation technique spawned an interpretation.

41. yme Says:

In the new lecture notes, the gray asides are a bit hard to read. Could they be made black instead, like the rest of the text, or at least a darker shade of gray? (Or maybe it’s just my monitor?)

42. yme Says:

On page 16 of the lecture notes, equation 2.8 has two equals signs. I think it should have only the second one, like equation 2.9.

43. Corey Ostrove Says:

@ yme #41,42: We can definitely bump up the contrast on the asides. I like having the text a slightly different color to differentiate the asides from the main text, but we can probably split the difference while still doing that. Thanks for pointing out the typo in equation 2.8. We’ll be sure to correct that in the next revision.

44. John Says:

Hey Scott, off-topic but since you liked Devs, you should check out Dark on Netflix if you haven’t done so. It’s a mind-bending masterpiece. The best time-travel / deterministic retro-causality thriller ever created imo. The third and last season should come out soon and connect all the dots, I hope they don’t screw up the ending.

45. Andrew Says:

Thanks a lot for the lecture notes, Prof. Aaronson. Quantum Computing Since Democritus is what piqued my interest in Quantum Computation and led to me to pursue a PhD in it in the first place. You have a beautiful, very intuitive style of writing and I really think that you should write a full fledged textbook in QC.

46. Rainer Says:

thank you gor this very nice looking update.
One suggestion for page 9.

“Church-Turing Thesis: The Church-Turing Thesis states that every physical process can be simulated _modulo mind interaction_ by a Turing machine to any desired precision.”

47. Anom Says:

Scott would you say that this is more or less detailed than QCsD? Which would be a better starting point for somebody who wants to understand the math behind the concepts? (or maybe another option altogether actually?) Thanks!

48. Scott Says:

Rainer #46: No, the thesis has no such proviso. 😉

49. Scott Says:

Anom #47: They’re of incomparable difficulty. Basically, these lecture notes are a straightforward undergrad course in quantum computing and information (with a smattering of quantum foundations), whereas QCSD is trying to do all sorts of stuff above, below, and around quantum computing. So it’s easier than the notes in some places and harder in others. Personally, I’d start with the notes and then move on to QCSD.

50. Anom Says:

Thanks Scott, very useful response. If anybody else is in a similar position than I am (trying to get the math from an amateur perspective), I would also recommend them Leo Susskind’s “Quantum Mechanics” from his “The Theretical Minimum” series, very very good imho.

51. yme Says:

John Figueroa #19: I agree. That section of the lecture notes could use some cleaning up. Besides the typos you mention, it also uses the same word “flip” to mean, sometimes, deterministically turning the coin upside down, and, other times, tossing it randomly.

52. Abdallah Says:

Scott, thank you so much for posting these notes, I couldn’t help but binge read them and they are probably the most interesting and best written intro to QC that I came across.

I have a small question. On page 125, it says:

“In fact, a little algebraic geometry (which we won’t go into here) is enough to show that exponentially many gates are needed to approximate most n-qubit unitaries as well, or even most n-qubit diagonal unitary transformations.”

Are you referring to the result proven in [Knill 95]? If yes, on the surface the proof given is not algebraic geometric. Are you refering to another result or is there a nicer proof of the same result elsewhere?

[Knill 95] https://arxiv.org/abs/quant-ph/9508006

53. Scott Says:

Abdallah #52: Hey, that long-ago paper by Knill is very nice and I hadn’t seen it; thanks! The proof that I knew applies Waring’s Theorem from algebraic geometry (see eg Theorem 5.2 in this survey by Alon). It won’t necessarily give a tight bound, but will work even if the gates can be non-unitary. It looks like Knill exploits unitarity to avoid the need for Waring’s theorem.

54. Abdallah Says:

Scott #53: Thank you for your response!

I am very interested in finding that proof. I am guessing the link you posted is for the theorem not the proof (the text makes no mention of unitaries, the theorem is used for lower bounds on algebraic decision trees).

I tried googling “waring” with a bunch of keywords (unitary, approximate, quantum, gates, ..etc.) to no avail. Do you, by any chance, recall some resource that has that proof (or some non-obvious keywords, like the author that would help me find it)?

Thanks again!

55. Scott Says:

Abdallah #54: I did a Google search and immediately found lots of relevant links, to papers and talks applying Waring’s theorem to circuit lower bounds. You could also try my own Multilinear Formulas and Skepticism of Quantum Computing paper, which makes at least incidental use of Waring’s theorem (as part of a counting argument, iirc).

56. Abdallah Says:

Scott #55: thanks for the pointers!

I think I misunderstood you earlier and was looking for inapproximability of *unitaries* using arbitrary gates. It seems you meant approximability of some bigger class of operators with arbitrary gates. I was excluding results that don’t have “unitary” or “quantum”. I also suspect that you meant Warren’s theorem. (Replacing Waring with Warren gives better results).

Your paper is what I am looking for, thanks for the pointer!

57. Justin Says:

Scott, you might want to update the sidebar of your blog to link to these Lecture Notes 2.0. It still links to the post from two years ago.

58. Scott Says:

Justin #57: Thanks!! Fixed.

59. Jue Says:

If I didn’t misunderstand, there might be some typos in the circuits of quantum error correction. In Figure 27.4 on Page 242, there are two extra “traget gate”s on the wires of sixth and nineth qubits. The gates for error correction in Figure 27.6 should be Z gates instead of X gates.

60. RoadMap — Quantum Computing | Plato Data Intelligence, Plato Vertical Search Says:

[…] He also has class notes, with the advantage of being always up to date: https://www.scottaaronson.com/blog/?p=4805 […]

61. RoadMap — Quantum Computing. Quantum computing is a hot subject, and… | by Arnaldo Gunzi | Sep, 2020 | New York Chat Says:

[…] He additionally has class notes, with the benefit of being all the time updated: https://www.scottaaronson.com/weblog/?p=4805 […]

Comment Policy: All comments are placed in moderation and reviewed prior to appearing. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, or snide and patronizing tone. Also: comments that link to a paper or article and, in effect, challenge me to respond to it are at severe risk of being left in moderation, as such comments place demands on my time that I can no longer meet. You'll have a much better chance of a response from me if you formulate your own argument here, rather than outsourcing the job to someone else. 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.

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