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

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, but they are much broader than that. One important application is the problem of “public-key quantum money” – that is, quantum states that can be authenticated by anyone, but only created or copied by a central bank – as well as related problems such as copy-protected quantum software. A second, very recent application involves the black-hole information paradox, where physicists realized that for certain conceptual puzzles in quantum gravity, they needed to know whether certain states and operations had exponential quantum circuit complexity. These two applications (quantum money and quantum gravity) even turn out to have connections to each other! A recurring theme of the course will be the quest to relate these novel problems to more traditional computational problems, so that one can say, for example, “this quantum money is hard to counterfeit if that cryptosystem is secure,” or “this state is hard to prepare if PSPACE is not in PP/poly.” Numerous open problems and research directions will be suggested, many requiring only minimal quantum background. Some previous exposure to quantum computing and information will be assumed, but a brief review will be provided.

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…

### 18 Responses to “The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes”

1. asdf Says:

Very off-topic but I can’t resist posting it here, regarding recent events in Turkey:

“as @mmeijeri obliqued, this failed coup is probably the first time in our lives we see a consensus problem among actual Byzantine generals”.

2. Scott Says:

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…

3. Jay Says:

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?

4. Daniel Seita Says:

Prof. Aaronson #2: Are you still undecided? If so you must be quite brave!

5. Scott Says:

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…

6. fred Says:

That’s where the Quantum money is going!

7. George Says:

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.

8. Raoul Ohio Says:

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

It is hard to imagine something that could trump the Republican convention!

9. BPP = NEXP Says:

Of all the lecture note collections on the internet, you certainly corralled one of the more accomplished group of scribes.

10. Scott Says:

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

11. Michele Amoretti Says:

Well, Scott.. Thank you so much for this textbook!

12. SargonTheFirst Says:

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.

13. Scott Says:

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!

14. Ryan O'Donnell Says:

For the record, Toni wrote 100% of the scribe notes that were (mistakenly) jointly attributed to me and her. Thanks Toni!

15. SargonTheFirst Says:

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

16. Scott Says:

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.

17. pseudonymous Says:

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.

18. pseudonymous Says:

Please replace “\lVert” and “\rVert” tags in my previous comment with \Vert. [Test: $$\Vert x \Vert$$