The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
On February 21-25, I taught a weeklong mini-course at the Bellairs Research Institute in Barbados, where I tried to tell an integrated story about everything from quantum proof and advice complexity classes to quantum money to AdS/CFT and the firewall problem—all through the unifying lens of quantum circuit complexity. After a long effort—on the part of me, the scribes, the guest lecturers, and the organizers—the 111-page lecture notes are finally available, right here.
Here’s the summary:
If you still haven’t decided whether to tackle this thing: it’s basically a quantum complexity theory textbook (well, a textbook for certain themes within quantum complexity theory) that I’ve written and put on the Internet for free. It has explanations of lots of published results both old and new, but also some results of mine (e.g., about private-key quantum money, firewalls, and AdS/CFT) that I shamefully haven’t yet written up as papers, and that therefore aren’t currently available anywhere else. If you’re interested in certain specific topics—for example, only quantum money, or only firewalls—you should be able to skip around in the notes without too much difficulty.
Thanks so much to Denis Therien for organizing the mini-course, Anil Ada for managing the scribe notes effort, my PhD students Adam Bouland and Luke Schaeffer for their special guest lecture (the last one), and finally, the course attendees for their constant questions and interruptions, and (of course) for scribing.
And in case you were wondering: yes, I’ll do absolutely anything for science, even if it means teaching a weeklong course in Barbados! Lest you consider this a pure island boondoggle, please know that I spent probably 12-14 hours per day either lecturing (in two 3-hour installments) or preparing for the lectures, with little sleep and just occasional dips in the ocean.
And now I’m headed to the Perimeter Institute for their It from Qubit summer school, not at all unrelated to my Barbados lectures. This time, though, it’s thankfully other people’s turns to lecture…
Follow
Comment #1 July 18th, 2016 at 12:06 pm
Very off-topic but I can’t resist posting it here, regarding recent events in Turkey:
https://twitter.com/kragen/status/754244653621321729
“as @mmeijeri obliqued, this failed coup is probably the first time in our lives we see a consensus problem among actual Byzantine generals”.
Comment #2 July 18th, 2016 at 12:39 pm
asdf #1: LOL!
As it happens, I was scheduled to visit Turkey (specifically Istanbul) for the first time this December. The failed coup happened just a few days after I reassured my mom, with great exasperation in my voice, that Turkey is totally safe to visit (even for someone whose passport is full of Israeli stamps), and she’s just being paranoid about nothing like usual. 🙂 I guess I should check the state of the Byzantine consensus in a few months before deciding whether to go…
Comment #3 July 18th, 2016 at 1:07 pm
Extremely interesting thanks!
On black holes and computation, two questions:
1) Is there any work from complexity theory that could shade light on Cauchy horizon?
2) one harder to state so please forgive the multiple lines question:
-small enough black holes are conjectured to radiate a lot. Assuming there exists a maximal temperature, then some black holes are just too luminous and nothing can get in. Call m1 the mass of the largest microscopic black hole that nothing can enter in.
-Given time exponential in the size of a black hole, HH argument don’t apply. Assuming cosmological horizons limit the computation time to some large but fixed size, then some black holes are too large to escape HH argument. Call m2 the mass the smalest macroscopic black hole that escape HH argument.
Would you be tempted to bet that m1=m2?
Comment #4 July 18th, 2016 at 2:01 pm
Prof. Aaronson #2: Are you still undecided? If so you must be quite brave!
Comment #5 July 18th, 2016 at 3:01 pm
Daniel #4: I went to Israel at the height of the Second Intifada, and also as the Iraq War was starting in 2003 and most people assumed (wrongly, as it turned out) that Saddam would attack Israel. Both visits were great.
Obviously going to Turkey is very different, but Turkey is also one of the only Middle Eastern countries besides Israel that would even let me in, thereby increasing my desire to visit it. It does seem likely that political conditions in Turkey will remain such as to make visiting a bad idea, but I still hold out hope…
Comment #6 July 18th, 2016 at 4:14 pm
Barbados in February?
That’s where the Quantum money is going!
Comment #7 July 19th, 2016 at 10:33 am
Daniel #4: I’m lined up to go in December too. Pretty confident it will have cooled off by then – I certainly hope so, for Turkey’s sake.
Comment #8 July 19th, 2016 at 11:01 am
asdf et al.
About technology and the Turkish Coup:
http://arstechnica.com/information-technology/2016/07/turkish-plotters-used-whatsapp-to-coordinate-coup/
Was it a fake coup?:
https://www.washingtonpost.com/news/monkey-cage/wp/2016/07/19/why-there-are-so-many-conspiracy-theories-about-the-turkish-coup/
It is hard to imagine something that could trump the Republican convention!
Comment #9 July 19th, 2016 at 11:29 pm
Of all the lecture note collections on the internet, you certainly corralled one of the more accomplished group of scribes.
Comment #10 July 20th, 2016 at 10:47 am
BPP=NEXP: Yup. The truth is, I couldn’t pass up the opportunity to use Sasha Razborov, Ryan O’Donnell, Toni Pitassi et al as “scribes.”
But maybe I should add, since it’s not really reflected in the polished notes — there were CONSTANT questions, interruptions, discoveries of errors in what I was saying, and the string theorists explaining unclear points to the computer scientists in the audience (and vice versa) to help me out. It made it challenging for me at the time, but in retrospect, it was absolutely essential to making the course what it was, and I owe an enormous debt to my not-the-slightest-bit-passive “scribes”!
Comment #11 July 20th, 2016 at 12:18 pm
Well, Scott.. Thank you so much for this textbook!
Comment #12 July 20th, 2016 at 8:12 pm
I’ll download and check it out. As a mere goy I admire your amazing and insightful jewish intellect on all matters physics-related Scott.
Comment #13 July 20th, 2016 at 11:02 pm
Sargon #12: Err … thanks, I guess. But discounting the likelihood that you’re simply trolling me: Newton was a goy, Dirac was a goy, “many of my best friends are goys,” 🙂 lots of the wonderful results in these lecture notes were proved by goys. At this frightening time for the US and the world, when we see a recrudescence of attitudes that seemed to belong to humanity’s past, and when what never needed to be said in my lifetime suddenly does need to be said, I think it’s important that we take clear stands against white supremacy, Jewish supremacy, Muslim supremacy, and every other kind of ethnic or religious supremacy. The only brand of supremacy I endorse is Quantum Supremacy!
Comment #14 July 21st, 2016 at 9:53 pm
For the record, Toni wrote 100% of the scribe notes that were (mistakenly) jointly attributed to me and her. Thanks Toni!
Comment #15 July 21st, 2016 at 11:43 pm
Haha, yeah I was trolling you a little there. I really like your blog though, but I don’t think it’s “supremacy” to acknowledge the high Ashkenazi IQ. It’s often rewarding and challenging to hang and learn from people more skilled than oneself.
http://immortallife.info/articles/entry/why-is-the-iq-of-ashkenazi-jews-so-high
Comment #16 July 22nd, 2016 at 1:29 am
Ryan #14: OK, thanks for the clarification—fixed! (I’ve also continued fixing other minor errors in the notes as I catch them.) In any case, your questions and comments during lecture certainly improved the finished product.
Comment #17 November 5th, 2016 at 3:41 am
Hi Scott,
In the lecture notes, lemma 1.3.2 and the notes after Lemma 1.3.3 both sound wrong. For lemma 1.2, consider \( \rho = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \) and \( \Lambda = \frac{1}{2} \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \).
Then we get \( \varepsilon = \frac{1}{2} \) but \( \lVert \rho – \tilde{\rho} \rVert_{Tr} = \frac{1}{\sqrt{2}} = \sqrt{\varepsilon} > \varepsilon \). This would, in fact, be the case with every pure state and projective matrix.
For lemma 1.3, the bound of \( O(k\varepsilon)\) sounds obviously incorrect because even for \(k=1\), it implies a stronger version of the “Almost as good as new lemma”, which isn’t true.
Comment #18 November 5th, 2016 at 3:42 am
Please replace “\lVert” and “\rVert” tags in my previous comment with \Vert. [Test: \(\Vert x \Vert\)