## 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!

Comment #1 May 20th, 2020 at 4:56 pm

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

Comment #2 May 20th, 2020 at 4:58 pm

Working link for TCS+ (doesn’t require login): https://researchseminars.org/seminar/TCSPlus

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

Comment #3 May 20th, 2020 at 4:58 pm

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.

Comment #4 May 20th, 2020 at 5:59 pm

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

Comment #5 May 20th, 2020 at 6:10 pm

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.”

Comment #6 May 20th, 2020 at 6:14 pm

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

Comment #7 May 20th, 2020 at 6:16 pm

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.

Comment #8 May 20th, 2020 at 7:21 pm

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.

Comment #9 May 20th, 2020 at 10:17 pm

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

Comment #10 May 20th, 2020 at 10:35 pm

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?)

Comment #11 May 20th, 2020 at 11:48 pm

[…] Quantum Computing Lecture Notes 2.0 […]

Comment #12 May 21st, 2020 at 1:09 am

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

Comment #13 May 21st, 2020 at 2:19 am

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.

Comment #14 May 21st, 2020 at 9:59 am

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.

Comment #15 May 21st, 2020 at 10:09 am

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

Comment #16 May 21st, 2020 at 10:14 am

Craig Gidney #13: That’s an

extremelyinteresting question that I hadn’t thought about! Myguesswould 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

neverworth it to combine my and Drucker’s protocol with quantum error correction.Comment #17 May 21st, 2020 at 10:47 am

@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.

Comment #18 May 21st, 2020 at 1:46 pm

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.

Comment #19 May 21st, 2020 at 1:50 pm

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  ]

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 thatP(tails|tails) = 0. (There’s a second typo where it should sayP(heads|tails) = 1 but actually saysP(tails|heads) = 1.) So the fixed description should imply the matrix:[1/2 1]

[1/2 0]

Instead of the text’s:

[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-fairflip that just scrambled the coin to being in the state <p,q>. And the second transition is the thing that’s eithera fair fliporturning 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 thesecondstage 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

firststage to the third stage. I couldn’t figure out why thepandqwere 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.”Comment #20 May 21st, 2020 at 2:12 pm

Greg #18: The “research frontier” is such a jagged surface that in some places, my undergraduate course will

alreadytake you there (as it did for Ewin Tang, to take one example). In other places, you need a followup grad quantum complexity courseplussome 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…Comment #21 May 21st, 2020 at 3:25 pm

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.

Comment #22 May 21st, 2020 at 3:35 pm

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.Comment #23 May 21st, 2020 at 3:51 pm

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

Comment #24 May 21st, 2020 at 4:13 pm

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?

Comment #25 May 21st, 2020 at 5:03 pm

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.

Comment #26 May 21st, 2020 at 8:24 pm

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 asyou 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.Comment #27 May 22nd, 2020 at 1:57 am

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!

Comment #28 May 22nd, 2020 at 5:48 pm

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?

Comment #29 May 22nd, 2020 at 5:53 pm

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?Comment #30 May 22nd, 2020 at 6:16 pm

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.

Comment #31 May 22nd, 2020 at 8:01 pm

Job #30: No, you misunderstood. I was really, non-rhetorically asking

how it worksto 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.Comment #32 May 22nd, 2020 at 10:46 pm

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.

Comment #33 May 22nd, 2020 at 11:26 pm

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.

Comment #34 May 23rd, 2020 at 7:39 am

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.

Comment #35 May 23rd, 2020 at 9:08 am

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

Comment #36 May 23rd, 2020 at 6:54 pm

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?

Comment #37 May 24th, 2020 at 7:36 am

@Scott

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

Comment #38 May 24th, 2020 at 10:14 am

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).

Comment #39 May 24th, 2020 at 10:23 am

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.

Comment #40 May 24th, 2020 at 9:21 pm

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.

Comment #41 May 25th, 2020 at 12:35 am

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?)

Comment #42 May 25th, 2020 at 3:45 am

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.

Comment #43 May 25th, 2020 at 11:35 am

@ 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.

Comment #44 May 25th, 2020 at 12:30 pm

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.

Comment #45 May 25th, 2020 at 3:08 pm

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.

Comment #46 May 26th, 2020 at 12:40 am

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.”

Comment #47 May 26th, 2020 at 4:39 pm

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!

Comment #48 May 26th, 2020 at 6:03 pm

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

Comment #49 May 26th, 2020 at 6:07 pm

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.

Comment #50 May 27th, 2020 at 3:09 am

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.

Comment #51 May 28th, 2020 at 3:03 pm

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.

Comment #52 June 6th, 2020 at 1:50 am

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

Comment #53 June 6th, 2020 at 7:19 am

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.

Comment #54 June 9th, 2020 at 6:48 am

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!

Comment #55 June 9th, 2020 at 10:51 am

Abdallah #54: I did a Google search and

immediatelyfound 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).Comment #56 June 10th, 2020 at 3:14 am

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!

Comment #57 July 2nd, 2020 at 10:05 pm

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.

Comment #58 July 3rd, 2020 at 12:17 am

Justin #57: Thanks!! Fixed.